Intro to Algorithms: Crash Course Computer Science #13

[@CaptNSquared]

3:53 "N Squared is not particularly efficient." There's no need to get personal...

[@EclecticFruit]

Snerk....

[@Elesario]

It's hip to be square ;)

[@lcmiracle]

Hey, still beats N!

[@ayaghsizian]

Haha that's ur real name that's so funny

[@renisnyanbinary]

At least it's not O((N+1)!)

[@wheezyair]

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

[@AdmiralWen]

Have you checked out the Coursera class on algorithms hosted by Princeton?

[@jakedcruz7057]

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.

[@anonymousexistence4304]

Yup they are certainly giving all this knowledge for free. Thank you!

[@riordan381]

Don't!

[@anandananda2277]

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

[@nohero23]

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

[@SilverMiraii]

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.

[@cholten99]

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%.

[@rmsgrey]

Only if by "write an algorithm" you mean "write code that implements a named algorithm". Any code is (an expression of) an algorithm...

[@onthegoprint]

I think he meant to re-write

[@EddieSaleh]

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

[@nahblue]

Odds of the developer writing accidentally quadratic code: 1 - epsilon

[@hexa3389]

Academia is Lonely. Ignored by everyone.

[@paruby]

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)

[@pearlsswine]

This video was incredibly well done! This lady is really great at teaching material in a clear, easy-to-follow manner.

[@unvergebeneid]

"I laugh at your puny algorithms!" says Littlefinger as he transports instantly from Highgarden to Winterfell.

[@fizzylazer]

you taught me so much in the 90's PBS now you continue to give me knowledge. Thank you.

[@danielgronbjerg]

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!

[@keerthivasanb7931]

Watching at 0.75x, and still pausing many times to see the frame, take in and process the information

[@paxdriver]

Best series on crash course

[@MFMegaZeroX7]

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.

[@flatfoot1983]

Just a little remark: Θ is called "the_t_a".

[@MFMegaZeroX7]

Thanks flatfoot! Fixed!

[@charntechakraisri6302]

I learn much more in 7 minutes here than 3 hours at university.

[@yatharthtyagi8766]

You have reignited my interest in computer science

[@wasimraja2980]

Watching in 0.75x speed !

[@luiselpro007rgz6]

Omg y wish you luck

[@brokeperson7103]

thanks for the save man :)

[@wasimraja2980]

@@brokeperson7103 welcome 😃

[@forMacguyver]

You've got a great point but try 2x speed, much more entertaining 😆

[@viraa7231]

me too, she talk way too fast and I cant keep up

[@firenationfiles2063]

*brain.exe stopped responding*

[@devi_buns]

Damn...mine crashed at the 1st quarter 😂

[@thinkingmind8868]

Mine too 😂

[@goofball9292]

Fire Nation Files same here, man this coding stuff is way too tough for me

[@ridwanrf6074]

@@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.

[@diaryoflife2024]

@@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.

[@syhusada1130]

We need Crash Curse for Math!

[@officialabs9019]

i agree

[@chesshooligan1282]

2 + 2 = 4, goddammit!!

[@armanke13]

Cursed

[@luiselpro007rgz6]

Yeah that sounds good

[@2-dsynctium773]

This is technically math. Except you're mostly just reorganizing or shuffling numbers to make a clear statement

[@xXAkirhaXx]

Did you just say "I'll CPU later?" GET OUT. Just kidding terrible jokes are the mark of great computer scientists.

[@only20frickinletters]

I expect an outtake with giggling from it.

[@ganaraminukshuk0]

Jeff Bond For a chemist, all the chem jokes are gone.

[@xXAkirhaXx]

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.

[@Equals_NULL]

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.

[@shehr-yar7135]

When does she say this

[@petershort3889]

Easily the best explanation of Big O I've seen... better than my professor explained it last semester.

[@rmsgrey]

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)

[@VladSvoka]

read some art of computer programming by Knuth. Great explanation there.

[@s.r6174]

Peter Short nice

[@Scarabola]

@@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.

[@rmsgrey]

@@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.

[@asp-uwu]

"I'll CPU Later" Now I think science _has_ gone too far.

[@planewire2153]

ill CuP later

[@hharlington7156]

Eli Smith oh no

[@Momo-bb2fn]

​@@planewire2153 I'll pucc u later

[@abdinasirawil2949]

Thank you for mentioning alkhawarzimi because allot of us don't know him but we admire him

[@FedJimSmith]

I can listen to you all day about the rest of the sorting algorithms.

[@tellingfoxtales]

Well, I guess I'm going to have to learn maths now.

[@chappie3642]

@@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

[@jakkuwolfinsomnia8058]

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

[@Grimlock1979]

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???

[@Grimlock1979]

Yah! I got it right!

[@asphoD3l]

is there any videos or books about algorithms somewhat as good as this one? I'll be happy to know about them

[@navi_dust]

I'm so glad I found this channel. You explain everything so well! Thank you! :)

[@mcho8137]

Wow CaryAnne. I dont think a better explanation at the speed that you delivered exist anywhere. Thank you.

[@Marcos-qv3mz]

LOOOOOVING THIS SERIES!!! THANK YOU CARRIE AND THANK YOU CRASH COURSE

[@spyrex3988]

My favorite algorithm is hybrid sort, it's literally a hybrid of counting sort and quick sort

[@Leotique]

Always feeling a bit smarter after watching Crash Course, thank you :)

[@sugami82]

This episode brings back memories of university classes/lectures, wish my professors were this good though :P

[@armorsmith43]

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.

[@matthewgarber5517]

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

[@TheRilonator]

Good call.

[@sboochek]

episodes 7-12 I was totaly lost, finally i start to understand again a little

[@dawncrime3121]

I just learned this 2 days ago in class!!!! Amazing.

[@catalix5098]

CONGRATULATIONS ON 6M SUBSCRIBERS!

[@Ayplus]

Best one in the series so far. . .imo

[@chillwavefrequency8108]

Wow, that was a great visual and explanation of Dijkstra’s Algorithm

[@Barnardrab]

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).

[@s.r6174]

Nice

[@DieNoobCompany]

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.

[@JotoCraft]

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.

[@andrewshirley9240]

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.

[@botha42]

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.

[@DerUnbekannte]

the one by computerphile?

[@PhoenixDude]

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)

[@rmsgrey]

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...

[@DuluthTW]

This course is getting better - while it started out great anyway.

[@SpaceEngineerErich]

I just binged this entire series and learned so much. Now I have to wait 5 more days for the next one! >.

[@mausmalone]

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.

[@bee5120]

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. :)

[@pradyutdas7358]

Dijkstra rocks 🤟!! Thank you Carrie Ann and Crash Course... ❤️

[@saeedbaig4249]

That was the best visual representation of Djikstra's algo I've ever seen.

[@OmnipotentO]

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.

[@sjwimmel]

If you're interested in algorithms, you might like the channel Computerphile too.

[@P234rer]

If you want to learn how to code some algorithms, I would recommend Tushar Roy

[@richardpaul5427]

*Computerphile

[@Kabodanki]

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

[@treaskcodie4649]

Check Out Treask Codie.....JUst Started!

[@williamlewington3223]

Big Up Nottingham UNI for computerphile!

[@pavansonty1]

subtle GoT reference. That too in Graph search. Awesome!!

[@adibbehroozitv6447]

Finally I really like programming

[@treaskcodie4649]

Check Out Treask Codie.....JUst Started!

[@jeancarlo912]

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 ;)

[@kujmous]

This is my favorite episode!

[@malanlk1014]

i used to watch the video about computer programming languages of yours. that was very interesting and educational. this video also really good!

[@gauravphalke5311]

Thankyou crash course for existing..

[@dandy-lions5788]

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...🤔

[@farawaymorgan2629]

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.

[@pinklady7184]

I have watched all your videos, Carrie. Now I am looking forward to your next video #14.

[@th3voice]

Loving the series, it's amazing. Also, algorithms are the coolest brain products in all the universe.

[@mojajojajo]

thanks guys, that's all I can say, you make these seen like fun

[@adomagala1]

This was better explained in 10 minutes than in an entire semester at school. My professor tried to explain these algorithms with excel...

[@mikeg9b]

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 ?

[@divinegrace92]

Michael Gainey I is universal for index

[@mikeg9b]

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.

[@hciprof]

Nice catch. You are indeed correct.

[@abbaspetiwala7672]

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.

[@Gobberwart]

No Name this was bugging me too.

[@hyees13]

Holy crap, homegirls an algorithm herself. Slow down

[@Andrew-ht7rf]

This video should be shown as an intro to all CS course majors.

[@andarted]

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.

[@felipec3788]

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

[@ze_rubenator]

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.

[@andresbolivar702]

Dijkstra Algorithm is super useful! Now I see why OSPF uses it! :)

[@MaggotDiggo1]

What a great host, keep up the good work!

[@Jackscin]

I like just subscribed to the channel and I feel like a new, smart person

[@aeebeecee3737]

Your tutorial so bright to me, thank you so much 😊

[@dakotaboy80]

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.

[@ryann5568]

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.

[@troyh8461]

How did your interviews go?

[@KokahZ777]

@@troyh8461 he invented an algorithm to teleport

[@colza1025]

Brilliant intro! Thank you. The graph search is awesome and I was really intrigued to search further. :)

[@darthteej1]

This video explained what a logarithim is better than years of high school math ever did

[@saleemsaif41]

The joke in-between made my day

[@aeebeecee3737]

Tu tutorial es tan brillante para mí, muchas gracias 😊 ❤️

[@Malidictus]

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?

[@pooja05rejoice]

Nailed graphic animation and pictorial information as the explanation goes.. Amazing for learning :) Happy, Thank you so much Team :)

[@kevnar]

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; }

[@gabrielbyram5658]

This was an awesome video! Extremely informative.

[@brandonhenley4844]

The game of thrones graph really helped with this concept !

[@jamesbaxterfirst]

Why is it that this video explained logarithms better so I explain it more than my algebra 2 teacher

[@delvinc822]

I seriously think youtubers should replace teachers.

[@puppeli]

*J*, thats just the initial cost

[@BertGrink]

+J B LOGArithms? or did you mean ALGOrithms?

[@MARTOUFFF06]

no offense but seem kinda dumb anyway :/

[@mahnas92]

pretty sure (s)he meant logarithms, since (s)he is talking about the algebra teacher...

[@n_b7467]

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!

[@mikeg9b]

At 10:31, how does O(6 log 6 + 9) = 13.7? Since log2(6) = 2.58, 6 x 2.58 + 9 = 24.5 What I am doing wrong?

[@Sarcasmitron]

It's log(6 + 9), not log(6) + 9

[@mikeg9b]

That still doesn't equal 13.7.

[@lotrbuilders5041]

Michael Gainey it's not log2, but log 10 which they used

[@mikeg9b]

LoTR Builders, thank you. Now I can finally arrive at 13.7. 6 x log10(6) + 9 = 13.6689.... I wonder why log10 is used. Log2 makes sense to me in divide-and-conquer algorithms that successively divide the problem in halves (like binary search).

[@mikeg9b]

Also, at 6:30, she explains that log2 is used and the graphic on the screen shows log2. It doesn't make sense.

[@DaElfer]

ive always loved the math behind a* for gaming as opposed to dijkstra's

[@tartanhandbag]

carrie anne is a great presenter!

[@umidnazarov5725]

I like the way you named nodes.I will do the same.

[@RibbittIII]

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)

[@tannerbatt9027]

This was a GREAT video, but I like *hardware* topics more as I find that more entertaining and important. (though that's like comparing air and waters importance, either way, thanks again)

[@aqualeung]

Great intro. I was going to comment about algo optimization but I'm guessing that will have an episode of its own later. So I'll hold my tongue until then :)

[@yaya5tim]

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

[@sourcedrop7624]

winter is upon us at crash course castle!

[@MK-ji9ke]

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?

[@MondSemmel]

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.

[@melonm8882]

I might be wrong, but the pseudo code after the first "NEXT" should be "swap array items at i and smallest", right? I see that that 'index' is outside the for-loop, but I found it a bit confusing to understand at first, because of the re-usage of that word :D I love this series btw, she explains it so well and enthusiastic!

[@GMODISM]

Great video! Made me catch up the class I almost understood! ^___^

[@walterbatchelder8070]

"Form follows function!" An exceptional course, in my assessment.

[@mehmedcavas3069]

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

[@albertogr7356]

I love your videos, keep it up!