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
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%.
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
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.
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)
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.
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!
@@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.
@@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
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
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)
@@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.
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???
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 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
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.
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...
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.
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.
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.
Just a quick jump in on Dijkstra's Algorithm - there's one scenario where it knocks every other graph search out of the park. Dijkstra's Algorithm doesn't just tell you the fastest route from point A to point B - it tells you the fastest route from point A to *literally every other point on the map*. It's absolutely great if you plan on pre-calculating and storing routes because you solve so many of them at the same time.
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).
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. :)
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.
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
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
OK, question. Splitting an array of size 8 into 8 arrays of size 1 takes 7 split actions. That might only constitute three steps, but each subsequent step contains more actions. Splitting a single array of size 8 in half is 1 action, which results in two arrays of size 4. Splitting those two arrays of size 4 in half may constitute 1 action, but that action is carried out once for each individual array. That's 2 actions for a total of 3, resulting in four arrays of size 2. Splitting those in half is, again, a single step which consists of a split action per array, meaning 4 actions, or a total of 7 actions. Ignoring the fact that array creation is a slower, more memory-intensinve process than swapping values in an array, isn't it misleading to count compound steps as a single action for the sake of complexity?
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; }
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 ?
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.
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.
If you find the topic of algorithms intriguing, I highly recommend the 2016 book "Algorithms to Live by: The Computer Science of Human Decisions", which applies algorithms from computer science to daily life.
All this channel reminds me of just all those nerdy kids in my ap chem class back in high school who make nerdy jokes all the time while they watch crash course
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)!)
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
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
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.
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.
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)
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
This video was incredibly well done! This lady is really great at teaching material in a clear, easy-to-follow manner.
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'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 laugh at your puny algorithms!" says Littlefinger as he transports instantly from Highgarden to Winterfell.
"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
I learn much more in 7 minutes here than 3 hours at university.
*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.
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
Best series on crash course
You have reignited my interest in computer science
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
Thank you for mentioning alkhawarzimi because allot of us don't know him but we admire him
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
you taught me so much in the 90's PBS now you continue to give me knowledge. Thank you.
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.
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!
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.
I can listen to you all day about the rest of the sorting algorithms.
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!
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 ;)
Holy crap, homegirls an algorithm herself. Slow down
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
My favorite algorithm is hybrid sort, it's literally a hybrid of counting sort and quick sort
Always feeling a bit smarter after watching Crash Course, thank you :)
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...
episodes 7-12 I was totaly lost, finally i start to understand again a little
I'm so glad I found this channel. You explain everything so well! Thank you! :)
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.
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.
This episode brings back memories of university classes/lectures, wish my professors were this good though :P
Wow CaryAnne. I dont think a better explanation at the speed that you delivered exist anywhere. Thank you.
This course is getting better - while it started out great anyway.
LOOOOOVING THIS SERIES!!! THANK YOU CARRIE AND THANK YOU CRASH COURSE
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.
Finally I really like programming
Check Out Treask Codie.....JUst Started!
Just a quick jump in on Dijkstra's Algorithm - there's one scenario where it knocks every other graph search out of the park. Dijkstra's Algorithm doesn't just tell you the fastest route from point A to point B - it tells you the fastest route from point A to *literally every other point on the map*. It's absolutely great if you plan on pre-calculating and storing routes because you solve so many of them at the same time.
I just learned this 2 days ago in class!!!! Amazing.
Dijkstra rocks 🤟!! Thank you Carrie Ann and Crash Course... ❤️
is there any videos or books about algorithms somewhat as good as this one? I'll be happy to know about them
This was better explained in 10 minutes than in an entire semester at school. My professor tried to explain these algorithms with excel...
CONGRATULATIONS ON 6M SUBSCRIBERS!
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
Best one in the series so far. . .imo
Wow, that was a great visual and explanation of Dijkstra’s Algorithm
I just binged this entire series and learned so much. Now I have to wait 5 more days for the next one! >.
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.
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. :)
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
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.
This video should be shown as an intro to all CS course majors.
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
Every RUclipsr 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
OK, question. Splitting an array of size 8 into 8 arrays of size 1 takes 7 split actions. That might only constitute three steps, but each subsequent step contains more actions. Splitting a single array of size 8 in half is 1 action, which results in two arrays of size 4. Splitting those two arrays of size 4 in half may constitute 1 action, but that action is carried out once for each individual array. That's 2 actions for a total of 3, resulting in four arrays of size 2. Splitting those in half is, again, a single step which consists of a split action per array, meaning 4 actions, or a total of 7 actions.
Ignoring the fact that array creation is a slower, more memory-intensinve process than swapping values in an array, isn't it misleading to count compound steps as a single action for the sake of complexity?
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;
}
That was the best visual representation of Djikstra's algo I've ever seen.
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.
Thankyou crash course for existing..
I'm making my way through these and it's too much information to remember but can we all just shout out to Carrie Anne for being so awesome!
This video explained what a logarithim is better than years of high school math ever did
Why is it that this video explained logarithms better so I explain it more than my algebra 2 teacher
I seriously think youtubers should replace teachers.
*J*, thats just the initial cost
+J B
LOGArithms? or did you mean ALGOrithms?
no offense but seem kinda dumb anyway :/
pretty sure (s)he meant logarithms, since (s)he is talking about the algebra teacher...
subtle GoT reference. That too in Graph search. Awesome!!
i used to watch the video about computer programming languages of yours. that was very interesting and educational. this video also really good!
thanks guys, that's all I can say, you make these seen like fun
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.
If you find the topic of algorithms intriguing, I highly recommend the 2016 book "Algorithms to Live by: The Computer Science of Human Decisions", which applies algorithms from computer science to daily life.
I have watched all your videos, Carrie. Now I am looking forward to your next video #14.
Dijkstra Algorithm is super useful! Now I see why OSPF uses it! :)
This is my favorite episode!
Your tutorial so bright to me, thank you so much 😊
The game of thrones graph really helped with this concept !
I like just subscribed to the channel and I feel like a new, smart person
carrie anne is a great presenter!
Loving the series, it's amazing. Also, algorithms are the coolest brain products in all the universe.
I like the way you named nodes.I will do the same.
What a great host, keep up the good work!
Great Game of Thrones reference
AlterDieg8 vv
When?
Shoutout to people who have a computerscience gcse exam tomo and haven’t revised untill a day before
Selectipn sort is not n * n because at each turn we decrease the number of steps by 1. The n + (n-1) + (n-2) + ... + 1
All this channel reminds me of just all those nerdy kids in my ap chem class back in high school who make nerdy jokes all the time while they watch crash course
So interesting but now I'm getting a headache trying to do the math D: lol
This was an awesome video! Extremely informative.
Tu tutorial es tan brillante para mí, muchas gracias 😊 ❤️
Brilliant intro! Thank you. The graph search is awesome and I was really intrigued to search further. :)
Nailed graphic animation and pictorial information as the explanation goes.. Amazing for learning :) Happy, Thank you so much Team :)
Now the really important question: does Carrie Anne actually own a ceramic cat collection? :P
The joke in-between made my day
Computation is the basic of all the science.
Very nice video. Educational AND entertaining with good production value.
Thanks for sharing...
Can I be a computer scientist at 62?
(Well, I know that the best time was 45 years ago.)
ive always loved the math behind a* for gaming as opposed to dijkstra's
If only I had this when doing A-level CS.
Love this channel