Intro to Algorithms: Crash Course Computer Science #13
ฝัง
- เผยแพร่เมื่อ 2 ต.ค. 2024
- Algorithms are the sets of steps necessary to complete computation - they are at the heart of what our devices actually do. And this isn’t a new concept. Since the development of math itself algorithms have been needed to help us complete tasks more efficiently, but today we’re going to take a look a couple modern computing problems like sorting and graph search, and show how we’ve made them more efficient so you can more easily find cheap airfare or map directions to Winterfell... or like a restaurant or something.
Ps. Have you had the chance to play the Grace Hopper game we made in episode 12. Check it out here! thoughtcafe.ca/...
CORRECTION:
In the pseudocode for selection sort at 3:09, this line:
swap array items at index and smallest
should be:
swap array items at i and smallest
Produced in collaboration with PBS Digital Studios: / pbsdigitalstudios
Want to know more about Carrie Anne?
about.me/carri...
The Latest from PBS Digital Studios: www.youtube.co....
Want to find Crash Course elsewhere on the internet?
Facebook - / youtubecrash. .
Twitter - / thecrashcourse
Tumblr - / thecrashcourse
Support Crash Course on Patreon: / crashcourse
CC Kids: / crashcoursekids
3:53 "N Squared is not particularly efficient."
There's no need to get personal...
Snerk....
It's hip to be square ;)
Hey, still beats N!
Haha that's ur real name that's so funny
At least it's not O((N+1)!)
this stuff is so damn interesting to me...
but it makes me want to smash my face through a brick wall.
Tickleshits go for it 🔥
The pinnacle of interest.
This is my homework 😔
There's always a more fundamental lesson or simpler idea somewhere out there to help you understand! If this were my very first video (not assuming that it's yours) on coding, It would be a little frustrating to absorb... I've actually been binge-watching courses and documentaries on computer science all weekend, and it's just been enlightening.
The good thing about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do.
~Ted Nelson
Odds of a developer being asked to write an algorithm as part of a coding interview - 75%. Odds of same develop ever writing an algorithm in their job as opposed to reusing a system library - 10%.
Only if by "write an algorithm" you mean "write code that implements a named algorithm". Any code is (an expression of) an algorithm...
I think he meant to re-write
Usually researchers and people in academia are tasked to write (author) algorithms. The rest of us programmers build on top of the generally published and existing knowledge of algorithms, which mostly is already implemented in an open-sourced lib. However, it is necessary to understand the underlying steps in those libs to be able to make a good judgement on how to use them
Odds of the developer writing accidentally quadratic code: 1 - epsilon
Academia is Lonely. Ignored by everyone.
Watching in 0.75x speed !
Omg y wish you luck
thanks for the save man :)
@@brokeperson7103 welcome 😃
You've got a great point but try 2x speed, much more entertaining 😆
me too, she talk way too fast and I cant keep up
I can't believe this is free online to watch and learn you guys are doing great things. I deafinetly want to be a computer scientist now
Have you checked out the Coursera class on algorithms hosted by Princeton?
A lot of people are out there that want to help people learn or just give people stuff for free. That't the entire open source community.
Yup they are certainly giving all this knowledge for free.
Thank you!
Don't!
In school I had to write a bubble sort in 16bit intel ASM. It worked, was efficient and was well documented. It got me an A+. Even like 15 years later, I am so damn proud of that piece of code. :-D
Holy crap, homegirls an algorithm herself. Slow down
Girl you are good but please take a breath, you are going fast, being English my second language, I would love to understand you. keep up the good work ;)
"I laugh at your puny algorithms!" says Littlefinger as he transports instantly from Highgarden to Winterfell.
Did you just say "I'll CPU later?" GET OUT.
Just kidding terrible jokes are the mark of great computer scientists.
I expect an outtake with giggling from it.
Jeff Bond For a chemist, all the chem jokes are gone.
Guys, there are 11 types of programmers in the world. The ones that get it, the ones that don't, and the ones that google it.
There's 10 types of peope in the world.
Those who understand binary jokes, those who don't, and those who didn't expect this to be a ternary joke.
When does she say this
"I'll CPU Later"
Now I think science _has_ gone too far.
ill CuP later
Eli Smith oh no
@@planewire2153 I'll pucc u later
*brain.exe stopped responding*
Damn...mine crashed at the 1st quarter 😂
Mine too 😂
Fire Nation Files same here, man this coding stuff is way too tough for me
@@goofball9292 Mind you that this course doesn't expect you to understand the details of the algorithm used, just the big picture. We have to look for a more detailed course to understand it more clearly. By then, you can only decide if coding is too tough for you or not.
@@goofball9292 I'm starting out and I just keep reminding myself to learn a bit every day. I've been disheartened so many times but turns out everyone is the same.
This series is a great addition to learning computer science, i.e. learning syntax, logic, algorithms.
It gives context to everything, besides, it's fascinating.
I learn much more in 7 minutes here than 3 hours at university.
Small bug in pseudo code for selection sort at 3.11: third from bottom line should say "swap array items at i and smallest".
(Currently it says to swap items at index and smallest. Since index would be at the end of the array whenever that line is executed as it is after the inner for-loop, this would swap the last and smallest elements rather than putting the smallest element in its correct position)
Wow CaryAnne. I dont think a better explanation at the speed that you delivered exist anywhere. Thank you.
Blah. Reminds me of all the interviews for Amazon and Microsoft I had to do. Not as much fun to do when you're nervous and have someone watching.
How did your interviews go?
@@troyh8461 he invented an algorithm to teleport
Well, I guess I'm going to have to learn maths now.
@@jonathanjrod yeah not really lol.
That is when you are programming simple stuff.
Once you get to a level that is required in big company a decent maths level is almost required. Especially discrete math.
Then also if you wanna make AIs, that takes quite a lot of maths
This episode brings back memories of university classes/lectures, wish my professors were this good though :P
greater series .
one small remark about Dykstra 's algorithm.
it does NOT end like shown.
the algorithm continues until the destination is the node that gets checked (so it is the smallest not checked node)
that this is needed can easily be shown with a little modifications.
the last step shown was starting at a 12 and had length 10. the next node that needs to be tested is distance 13 from the start. so if the length here is less than 9 we have a new shortest path.
Right. To prove this, consider the case where the path from Pyke to Winterfall had a cost of less than 9. It would have resulted in a final route of length less than 22, and therefore been faster.
Funny enough, when I saw an other video about Dijkstra's algorithm they made the same mistake. It seems to be common amogst computer scientist.
the one by computerphile?
It's a little nitpicky, but there was also another problem with this explanation:
Since this graph is undirected, when you check a node you must also check it's "predecessor".
So the method should be (from "King's Landing"):
- Check edge of weight 5
- New best found to "The Trident": (? vs 13)
- Check edge of weight 8
- Current weight of "Highgarden" lower (0 vs 8)
- Check edge of weight 25
- Current weight of "Riverrun" lower (10 vs 25)
To be fair, they do mention that going via Pyke would take longer - they just don't show it with animation. It might have been better to have explained it more clearly rather than going through every intermediate step in detail, but they did at least bring it up...
If you're interested in algorithms, you might like the channel Computerphile too.
If you want to learn how to code some algorithms, I would recommend Tushar Roy
*Computerphile
and if you are a programmer and you want to get better, codingame.com is a good site, even if you thing you are an expert
Check Out Treask Codie.....JUst Started!
Big Up Nottingham UNI for computerphile!
Not sure if it's been pointed out, but the Pyke-Riverrun-Highgarden creates an impossible triangle. No side can be larger than the sum of the other two sides of a triangle...🤔
Yeah you're right !! But that's in Maths/"Trigonometry" the "InEqaulity Theorem" here she is just demonstrating an example to make understanding the algorithm easier. Triangles have nothing to do with the algorithm in these case. Even though you might need the theorem in a case where you are writing an algorithms which concerns triangles.
We need Crash Curse for Math!
i agree
2 + 2 = 4, goddammit!!
Cursed
Yeah that sounds good
This is technically math. Except you're mostly just reorganizing or shuffling numbers to make a clear statement
is there any videos or books about algorithms somewhat as good as this one? I'll be happy to know about them
Just a few things to note about the "big-oh" notation discussed in this episode:
In industry, "big-oh" notation alone is what is seen when discussing algorithms. However, in academia, it is a bit more in depth. O(n) is instead used to represent an upperbound (in the WORST CASE, what is this problem or algorithm). Ω(n) (pronounced "big-omega") is used to represent the lowerbound (in the BEST CASE, what is this problem or algorithm). Θ(n), prounounced "theta" (without the "big") is used to represent the tightbound (used when the big-oh is equal to the big-omega, which is the exact running time). There is also small omega and small o, but those are rarely used.
Also, we only care about the biggest polynomial when we use this notation. So if a problem takes 5n^4 + 3n^2 + 1 to do, we just say it is Θ(n^4). We drop the coefficient and smaller terms because we only care about what happens when n is really really big.
You may notice that earlier I mentioned algorithm or problem when describing the notation. This is because the it is often used in academia to denote all of the algorithms that exist for a problem. For example, for matrix multiplication of an n x n matrix, we have Ω(n^2), since we know that we at least need to read in n^2 values. This problem currently has O(n^2.3728639) which is the running time of an algorithm created by Francois Le Gall in 2014.
Just a little remark: Θ is called "the_t_a".
Thanks flatfoot! Fixed!
i used to watch the video about computer programming languages of yours. that was very interesting and educational. this video also really good!
This video was incredibly well done! This lady is really great at teaching material in a clear, easy-to-follow manner.
There is something I don't understand. I'd be very grateful if anyone could explain it to me.
3:14 "With this sort algorithm, we loop through each position in the array, from top to bottom, and then for each of those positions, we have to loop through the array to find the smallest number to swap. You can see this in the code, where one FOR loop is nested inside of another FOR loop. - This means, very roughly, that if we want to sort N items, we have to loop N times inside of which, we loop N times, for a grand total of roughly N times N loops ... or N squared."
I would have thought that this algorithm would not need roughly N² runs in total, but roughly (N²)/2 runs.
I'll try to demonstrate what I mean with an example. Say we have 4 values (2, 4, 6 and 8), and so 4 positions (A, B, C, D) for values.
___
Before first run:
_Start:
A - 8
B - 4
C - 2
D - 6
___
First run:
It needs 4 checks to find the smallest number.
[8 goes from A to C, 2 goes from C to A]
- total: 4 checks -
A - 2
B - 4
C - 8
D - 6
___
Second run:
Now the algorithm starts at position B. It needs 3 checks to find the smallest number.
[4 checks + 3 checks = 7 checks]
- total 7 checks -
A - 2
B - 4
C - 8
D - 6
___
Third run:
Now the algorithm starts at position C. It needs 2 checks to find the smallest number.
[7 checks + 2 checks = 9 checks]
- total 9 checks -
A - 2
B - 4
C - 6
D - 8
___
Fourth run:
The FOR circle is finished, because 4 is the end of the array.
______
In total there were 9 checks.
To use the quote from the beginning: "This means, very roughly, that if we want to sort N items, we have to loop N times inside of which, we loop N times, for a grand total of roughly N times N loops ... or N squared."
N is in this example 4. And 4² is16. But in reality it took just 9 checks.
❗️16 isn't roughly 9, it's about twice the amount.
I could imagine, that this is just some kind of writing standard, that doesn't necessarily reflect the reality.
Or maybe, there is something I don't understand here. I don't like this doubt. Therefore, I would be very grateful to anyone who can tell me where my mistake lies.
ive always loved the math behind a* for gaming as opposed to dijkstra's
She'll likely cover this, but a big part of designing a good algorithm is thinking about how you will lay out the data. That was how djikstra's algorithm got improved from n^2 to n*log(n).
"data structures" is your google keyword for the curious.
Andrew Farrell I'm sure she will cover data structures since the start of this episode before taking about arrays she said we will get into how things are stored next week. And since we went over big O notation it would make sense to talk about arrays, trees and associative containers next week
Good call.
Best one in the series so far. . .imo
I like the way you named nodes.I will do the same.
The solution in this example is obscenely overly complicated. The mark of an entry-level design.
I thought algorithms were invented by Al Gore.
It's Al Gore's pace. Al Gore Rhythm (I'll kms now)
Still better than "I'll CPU later."
Pipe2DevNull damn man lol everyone replying to you has has some deep senses of humor. 👍
Invented is a big word,
al gore invented just the ManBearPig
Al Gore only invented the global warming
I'm amazed how much ground you're able to cover in less than 12 minutes.
To be fair, if you haven't heard most of this before you would probably need the video to be twice as long to get anything from it, but even then I would be impressed with how much was stuffed in there.
Keep up the good work!
Watching at 0.75x, and still pausing many times to see the frame, take in and process the information
I always found algorithms to be the most interesting part of computer science.
This video was great, but it of course only scratches the surface.
Next up: Data Structures???
Yah! I got it right!
Your tutorial so bright to me, thank you so much 😊
My favorite algorithm is hybrid sort, it's literally a hybrid of counting sort and quick sort
I like just subscribed to the channel and I feel like a new, smart person
Nice video.
Quick question about the Dijkstra example. If the weight of the road between Pyke and Winterfell was 8 instead of 18 then Highgarden->Riverrun->Pyke->Winterfell would be the better route. Would Dijkstra's algorithm continue looping to find this pathway?
So interesting but now I'm getting a headache trying to do the math D: lol
When I was youger(in elementary school) is would sometimes sort all couple hundred of my Pokémon cards or Yugioh cards, this episode talked about sorting and it out into perspective that sorting cards in less time should require a balance of swapping cards and thinking when sorting other things are very different(I was weird, I think)
Computation is the basic of all the science.
It bothered me that the lengths of those triangles are impossible but then I remembered it's a map and the longer lengths can be explained with mountains. I can sleep in peace now.
You finished Dijkstra's algorithm once you found the first path to Winterfell, but in reality you should wait until Winterfell is the node with the lowest cost which has yet not been searched from. In the example, if the cost of the road from Pyke to Winterfell was 1, the shortest path would actually be through Pyke to Winterfell in 14 weeks, which you would find if you ran Dijkstra one more time from the cheapest unexplored node which was Pyke.
High quality content.. but why the rush? (almost all the videos from this channel sounds like eminem rapping) let the brain soak the info.
play the vid @ 0.75 then.....
I'm so glad I found this channel. You explain everything so well! Thank you! :)
Am I correct in thinking that Dijkstre's algorithm doesn't guarantee it finds the best path? In their example, they never checked the connection between Pyke and Winterfell, which could conceivably have resulted in a faster route than Riverrun->Trident->Winterfell.
Thank you for mentioning alkhawarzimi because allot of us don't know him but we admire him
episodes 7-12 I was totaly lost, finally i start to understand again a little
Great video! Made me catch up the class I almost understood! ^___^
*_"AL-OW-WRIT-TIMMYS"_*
Me is good at grammar of english
well letting an AI spell this way, requires very high *ALGORITHMS*
0:51 nah that's just handsome squidward
Easily the best explanation of Big O I've seen... better than my professor explained it last semester.
With a lot of maths (and closely related subjects like the abstract end of computer science) there are two explanations for most concepts - the carefully worked out formal definition [ f(x) = O(g(x)) if there exist values w and c such that for all x>w, f(x)
read some art of computer programming by Knuth. Great explanation there.
Peter Short nice
@@rmsgrey I don't know why people even bother teaching with the "formal" definitions and whatnot. It all just goes over my head. I guess people are just snobs looking for clout.
@@Scarabola The formal definitions are also important - they're how you tell that something doesn't just seem like a reasonable idea, but actually works - so they do need to be taught at some point (and they're what generally gets tested in exams since it's easier to test whether someone can perform the formal symbol manipulation correctly than whether they understand what the symbol manipulation really means) - it's just that the other side - what the symbols mean and why things have the definition they do - is also important in the long run, and should be taught too.
Who's still haunted with debugging Algorithms?
outsourced it to chinese
lol drogon flyin 7:34 was so cool...
7:30 It's very strange to see The Trident put on a map as if it's a city. The Trident is a river.
Great Game of Thrones reference
AlterDieg8 vv
When?
Now the really important question: does Carrie Anne actually own a ceramic cat collection? :P
I watched the first 24 seconds and I said "Gosh, I love you".
i want to study game development and i know, in order to make a game you need algorithms, but i am not particularly good at math and sometimes when it gets too confusing, my mind gets lost. though, i am positive that i understood 65% of this video. Will i make it XD???
Always feeling a bit smarter after watching Crash Course, thank you :)
Finally I really like programming
Check Out Treask Codie.....JUst Started!
I can't believe I only found this channel just now. XD
In the pseudocode for selection sort at 3:09, shouldn't the swap be ...
swap array items at i and smallest
instead of
swap array items at index and smallest
?
Michael Gainey I is universal for index
The pseudocode uses both i and index as variables. They are both indexes -- i for the outer loop and index for the inner loop. Unless I'm wrong, the swap statement uses index when it should use i.
Nice catch. You are indeed correct.
and the total number of loops should be (n^2 - n)/2 , not n^2 as after each iteration of the outer for loop one element is already sorted and the total number of comparisions decreases by 1.
No Name this was bugging me too.
Best series on crash course
I would love to promo your page
Not only do more people need this kind of information. It’s vital for the future. Let me know if I could help out and maybe we can trade for skills
I love your videos, keep it up!
Fascinating. Thanks!
0:46 Props to her!
First English person who pronounces "Voilà" quite correctly :)
I invented a sorting algorithm. I call it ice sort. There are n² comparisons and zero swaps, so it's great for small sets.
for(int n: nums[]) {
index = (count of items in nums[] that are lower than n)
index++ until empty slot in sorted[] is found
sorted[index] = n;
}
Austin Powers teaches algorithms
I remember Bubble Sort and Dijkstra’s algorithm when I did my A-level Decision Maths. That confused me so much but when applied to Computer Science it really makes such a significant difference and it’s weird but very interesting fun maths ! :D
you taught me so much in the 90's PBS now you continue to give me knowledge. Thank you.
She talks way too fast. Its easy to understand but slow down. Why is she rushing??
This is great, keep up the amazing work CC
Also 38th!
She talks faster than the internet connection.. you in a hurry?
I'm a self thought programmer and i want to study computer science in college. but I'm really bad at math specially algebra and algorithms I literally don't understand anything should I really study computer science? because a lot jobs require a university degree.
next week we will discuss algorithms.... intrigued? you would be!
Can I be a computer scientist at 62?
(Well, I know that the best time was 45 years ago.)
Awesome look, love the glasses!!!
you could make a math series, it would be awesome you explain things so neatly i have literally studied of your videos to get good grades lol, it would help me get into collage cause honestly im lost when it comes to advanced complicated math. i have 5 months to learn everything and its really overwhelming and frustrating im fucked if i fail that test cause where i live if you're not a professional you wont earn more than 4 bucks an hour and thats if you're lucky
7:31 I saw just that in an anime about scientists-- (and love)
Ah yes, the graph: depth-first vs breadth-first search. I also quite enjoyed the binary search tree (BST). Really fascinating field of algorithms and data structures. :)
Every TH-camr should watch this before complaining about the "algorithm".
Why? People complain about the algorithm, for not sorting their videos in first because of mature content, and this proves that is what an algorithm does, sort
I was surprised to hear about Dijkstra's algorithm. I've learned about that in my networking class, particularly in regard to the link-state routing protocol known as OSPF (Open Shortest Path First).
Nice
Algorithms aren't just about coding they are about the steps involved in solving a problem when you use a programming language to perform an algorithm then its coding.
Please any one help. I am in 1st year 2nd semester going to finish. Now holidays due to Corona virus .I cant develop the logic of how to put the values properly and all .for eg like in pattern printing and most of the competitive problems like in codeforces and hackerank. My friends do simply all these.i dont know how to do it. What should I do. HELP.i dont know what And how to code.
@@Rohit-rx5rz Well
1. Don't be afraid of coding I mean not even professionals write working code n the first go try pondering and experimenting with different ideas
2. Every complex problem is just a set of many simple problems I recommend you to just see a problem as a puzzle you just not pick up all the pieces and put them together you put them down bit by bit by carefully looking at each piece with focus well that's just a general tip for solving life problems.
3. Try to reason a problem to its roots, for example, think what caused and build your logic till you don't know what caused it then learn it
4. If knowledge is power learning is superpower so try to use Feynman technique first read something then go to a paper or your laptop and write down what you read as simply as possible wherever your teaching couldn't be understood by a fresher in programming stop and revise the topic
Here are my suggestions well I am just 13 wish me luck
@@59vibhusharma31 lol thanks🤗
Welcome
CPU Later! love it!! Didn;t take long to PROCESS that one! LOL
whiterun _ riverrun and winterfell _ hammerfell
This course is getting better - while it started out great anyway.
O(n^2) is inefficient? Depends, it's pretty great when you usually deal with NP-Difficult problem. :P
8:14 This is how routers build routing tables. In other words, it's how all those ones and zeroes find their way across the Internet.
this is so good for review
I just learned this 2 days ago in class!!!! Amazing.
Nice tutorial!
Thank you but you are talking FAST i am not from UK or US i cant understand chen you talk quickly
Ok holy cow, does anyone remember "Brute Force Hacking" ? From DOS days I think?
CREEPER!!!!!!!!!!
Aaaawwwwwwwwww MAN
so we back in the mine
got our.....