# Intro to Algorithms: Crash Course Computer Science #13

Hi, I’m Carrie Anne, and welcome to CrashCourse

Computer Science! Over the past two episodes, we got our first

taste of programming in a high-level language, like Python or Java. We talked about different types of programming

language statements – like assignments, ifs, and loops – as well as putting statements

into functions that perform a computation, like calculating an exponent. Importantly, the function we wrote to calculate

exponents is only one possible solution. There are other ways to write this function

– using different statements in different orders – that achieve exactly the same numerical

result. The difference between them is the algorithm,

that is the specific steps used to complete the computation. Some algorithms are better than others even

if they produce equal results. Generally, the fewer steps it takes to compute,

the better it is, though sometimes we care about other factors, like how much memory

it uses. The term algorithm comes from Persian polymath

Muḥammad ibn Mūsā al-Khwārizmī who was one of the fathers of algebra more than a

millennium ago. The crafting of efficient algorithms – a

problem that existed long before modern computers – led to a whole science surrounding computation,

which evolved into the modern discipline of… you guessed it! Computer Science! INTRO One of the most storied algorithmic problems

in all of computer science is sorting… as in sorting names or sorting numbers. Computers sort all the time. Looking for the cheapest airfare, arranging

your email by most recently sent, or scrolling your contacts by last name — those all require

sorting. You might think “sorting isn’t so tough…

how many algorithms can there possibly be?” The answer is: a lot. Computer Scientists have spent decades inventing

algorithms for sorting, with cool names like Bubble Sort and Spaghetti Sort. Let’s try sorting! Imagine we have a set of airfare prices to

Indianapolis. We’ll talk about how data like this is represented

in memory next week, but for now, a series of items like this is called an array. Let’s take a look at these numbers to help

see how we might sort this programmatically. We’ll start with a simple algorithm. First, let’s scan down the array to find

the smallest number. Starting at the top with 307. It’s the only number we’ve seen, so it’s

also the smallest. The next is 239, that’s smaller than 307,

so it becomes our new smallest number. Next is 214, our new smallest number. 250 is not, neither is 384, 299, 223 or 312. So we’ve finished scanning all numbers,

and 214 is the smallest. To put this into ascending order, we swap

214 with the number in the top location. Great. We sorted one number! Now we repeat the same procedure, but instead

of starting at the top, we can start one spot below. First we see 239, which we save as our new

smallest number. Scanning the rest of the array, we find 223

is the next smallest, so we swap this with the number in the second spot. Now we repeat again, starting from the third

number down. This time, we swap 239 with 307. This process continues until we get to the

very last number, and voila, the array is sorted and you’re ready to book that flight

to Indianapolis! The process we just walked through is one

way – or one algorithm – for sorting an array. It’s called Selection Sort — and it’s

pretty basic. Here’s the pseudo-code. This function can be used to sort 8, 80, or

80 million numbers – and once you’ve written the function, you can use it over and over

again. 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. This relationship of input size to the number

of steps the algorithm takes to run characterizes the complexity of the Selection Sort algorithm. It gives you an approximation of how fast,

or slow, an algorithm is going to be. Computer Scientists write this order of growth

in something known as – no joke – “big O notation”. N squared is not particularly efficient. Our example array had n=8 items, and 8 squared

is 64. If we increase the size of our array from

8 items to 80, the running time is now 80 squared, which is 6,400. So although our array only grew by 10 times

– from 8 to 80 – the running time increased by 100 times – from 64 to 6,400! This effect magnifies as the array gets larger. That’s a big problem for a company like

Google, which has to sort arrays with millions or billions of entries. So, you might ask, as a burgeoning computer scientist, is there a more efficient sorting algorithm? Let’s go back to our old, unsorted array

and try a different algorithm, merge sort. The first thing merge sort does is check if

the size of the array is greater than 1. If it is, it splits the array into two halves. Since our array is size 8, it gets split into

two arrays of size 4. These are still bigger than size 1, so they

get split again, into arrays of size 2, and finally they split into 8 arrays with 1 item

in each. Now we are ready to merge, which is how “merge

sort” gets its name. Starting with the first two arrays, we read

the first – and only – value in them, in this case, 307 and 239. 239 is smaller, so we take that value first. The only number left is 307, so we put that

value second. We’ve successfully merged two arrays. We now repeat this process for the remaining

pairs, putting them each in sorted order. Then the merge process repeats. Again, we take the first two arrays, and we

compare the first numbers in them. This time its 239 and 214. 214 is lowest, so we take that number first. Now we look again at the first two numbers

in both arrays: 239 and 250. 239 is lower, so we take that number next. Now we look at the next two numbers: 307 and

250. 250 is lower, so we take that. Finally, we’re left with just 307, so that

gets added last. In every case, we start with two arrays, each

individually sorted, and merge them into a larger sorted array. We repeat the exact same merging process for

the two remaining arrays of size two. Now we have two sorted arrays of size 4. Just as before, we merge, comparing the first

two numbers in each array, and taking the lowest. We repeat this until all the numbers are merged,

and then our array is fully sorted again! The bad news is: no matter how many times

we sort these, you’re still going to have to pay $214 to get to Indianapolis. Anyway, the “Big O” computational complexity

of merge sort is N times the Log of N. The N comes from the number of times we need

to compare and merge items, which is directly proportional to the number of items in the

array. The Log N comes from the number of merge steps. In our example, we broke our array of 8 items

into 4, then 2, and finally 1. That’s 3 splits. Splitting in half repeatedly like this has

a logarithmic relationship with the number of items – trust me! Log base 2 of 8 equals 3 splits. If we double the size of our array to 16 – that’s

twice as many items to sort – it only increases the number of split steps by 1 since log base

2 of 16 equals 4. Even if we increase the size of the array

more than a thousand times, from 8 items to 8000 items, the number of split steps stays

pretty low. Log base 2 of 8000 is roughly 13. That’s more, but not much more than 3 — about

four times larger – and yet we’re sorting a lot more numbers. For this reason, merge sort is much more efficient

than selection sort. And now I can put my ceramic cat collection

in name order MUCH faster! There are literally dozens of sorting algorithms

we could review, but instead, I want to move on to my other favorite category of classic

algorithmic problems: graph search! A graph is a network of nodes connected by

lines. You can think of it like a map, with cities

and roads connecting them. Routes between these cities take different

amounts of time. We can label each line with what is called

a cost or weight. In this case, it’s weeks of travel. Now let’s say we want to find the fastest

route for an army at Highgarden to reach the castle at Winterfell. The simplest approach would just be to try

every single path exhaustively and calculate the total cost of each. That’s a brute force approach. We could have used a brute force approach

in sorting, by systematically trying every permutation of the array to check if it’s

sorted. This would have an N factorial complexity

– that is the number of nodes, times one less, times one less than that, and so on until

1. Which is way worse than even N squared. But, we can be way more clever! The classic algorithmic solution to this graph

problem was invented by one of the greatest minds in computer science practice and theory,

Edsger Dijkstra, so it’s appropriately named Dijkstra’s algorithm. We start in Highgarden with a cost of 0, which

we mark inside the node. For now, we mark all other cities with question

marks – we don’t know the cost of getting to them yet. Dijkstra’s algorithm always starts with the

node with lowest cost. In this case, it only knows about one node,

Highgarden, so it starts there. It follows all paths from that node to all

connecting nodes that are one step away, and records the cost to get to each of them. That completes one round of the algorithm. We haven’t encountered Winterfell yet, so

we loop and run Dijkstra’s algorithm again. With Highgarden already checked, the next

lowest cost node is King’s Landing. Just as before, we follow every unvisited

line to any connecting cities. The line to The Trident has a cost of 5. However, we want to keep a running cost from

Highgarden, so the total cost of getting to The Trident is 8 plus 5, which is 13 weeks. Now we follow the offroad path to Riverrun,

which has a high cost of 25, for a total of 33. But we can see inside of Riverrun that we’ve

already found a path with a lower cost of just 10. So we disregard our new path, and stick with

the previous, better path. We’ve now explored every line from King’s

Landing and didn’t find Winterfell, so we move on. The next lowest cost node is Riverrun, at

10 weeks. First we check the path to The Trident, which

has a total cost of 10 plus 2, or 12. That’s slightly better than the previous

path we found, which had a cost of 13, so we update the path and cost to The Trident. There is also a line from Riverrun to Pyke

with a cost of 3. 10 plus 3 is 13, which beats the previous

cost of 14, and so we update Pyke’s path and cost as well. That’s all paths from Riverrun checked…

so… you guessed it, Dijkstra’s algorithm loops again. The node with the next lowest cost is The

Trident and the only line from The Trident that we haven’t checked is a path to Winterfell! It has a cost of 10, plus we need to add in

the cost of 12 it takes to get to The Trident, for a grand total cost of 22. We check our last path, from Pyke to Winterfell,

which sums to 31. Now we know the lowest total cost, and also

the fastest route for the army to get there, which avoids King’s Landing! Dijkstra’s original algorithm, conceived in

1956, had a complexity of the number of nodes in the graph squared. And squared, as we already discussed, is never

great, because it means the algorithm can’t scale to big problems – like the entire road

map of the United States. Fortunately, Dijkstra’s algorithm was improved

a few years later to take the number of nodes in the graph, times the log of the number

of nodes, PLUS the number of lines. Although this looks more complicated, it’s

actually quite a bit faster. Plugging in our example graph, with 6 cities

and 9 lines, proves it. Our algorithm drops from 36 loops to around 14. As with sorting, there are innumerable graph search algorithms, with different pros and cons. Every time you use a service like Google Maps

to find directions, an algorithm much like Dijkstra’s is running on servers to figure

out the best route for you. Algorithms are everywhere and the modern world

would not be possible without them. We touched only the very tip of the algorithmic

iceberg in this episode, but a central part of being a computer scientist is leveraging

existing algorithms and writing new ones when needed, and I hope this little taste has intrigued

you to SEARCH further. I’ll see you next week.

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

aww..who is chasing you,

You talk to fast

Awesome video🤘

Good.

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.

Follow

Ok holy cow, does anyone remember "Brute Force Hacking" ? From DOS days I think?

came here because of blueshirt kid

what if pyke to winterfell is free!

the smoolest lol

The dijkstra algo has a mistake. You have to keep looping until you pick the final node in the beginning of the loop, you cut it off early.

You found a path to the end, but there could have been a shorter path that you didn't explore yet. Only after picking up the final node as an unexplored node with the smallest cost you know that there aren't any nodes with smaller cost, therefore there couldn't be a shortcut with cost zero from the top left node for example.

This is assuming that costs are non negative, as negative costs really screw it up.

a lannister does not simply travel north without checking his most efficient algorithms first

7:28 Too bad that show had to end :/

Please speak slowly.

Did they name it after the x vice president for inventing the internet? Al Gore?

Ok mow my head hurts

Watching in 0.75x speed !

Is anyone else getting turned on?

we touched only the tip… of the iceberg

Rewatched this video in .75 speed and it all made sense

sorry i dont understand woman

Reading the comments makes me feel better, as I don't feel as stupid as I look.

lol drogon flyin 7:34 was so cool…

Talk to fast.

i just want to say thank you, really amazing

Wasn't born pretty so gotta get smart

You didnt put bogosort in the list i am sad.

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.

Excellent content

Thank you

High quality content.. but why the rush? (almost all the videos from this channel sounds like eminem rapping) let the brain soak the info.

Oh look…more game of groans. You ruined this and destroyed my interest in your videos by forcing me to learn more about a pointless show rather than something I'm interested in. What next? The walking dead? Idiocracy is alive and strong in this one…

Selection sort makes me angry

If Wayne and Garth had a daughter…. Great video btw.

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!

why do you speak so fast ???

Algorithms

Al-khawarizmi was Trumps grandfather, that is why he likes computers, algorithms and muslims. Super smart guy and playboy grown baby blabla….

this is complcat <glitch> . I I I I oh whatever

She's monologuing 🙁 this is so sad, I'm dumb 🙁

nice juggs

I tried the code at 3:25 but the program did not work correctly until i changed the starting value to i

I saw you in the movie Dodgeball except you had a uni-brow back then.

doesn't the selection sort have to loop N + (N-1) + (N-2)….+ (1) times?

Why does she keep making game of thrones references?

CREEPER!!!!!!!!!!

Aaaawwwwwwwwww MAN

so we back in the mine

got our…..

gosh, where r a Russian caps…(((

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

At speed 0.5, it sounds like shes piss drunk xD

Great series tough!

she is the best teacher in computer science…wish i married you

0:46 Props to her!

no

My I use a bit of your video in my live fee

😵😵😵😵😵😵😵😵😵😵

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.

Austin powers has a sister

Has anyone below mentioned how the screen writers of season 8 (7) could have used this algorithm to stop teleporting, hey someone hit that travel thru Westeros program so i can figure how long it will take A to get to B! Oh 7 hells i was gonna make that way faster! Thanks Science!!

im I watching at 1.75X speed ??

Should try this 2x

A very useful and reveling algorithm would be one that would demonstrate the links that tie the militaro industrial complex to the global economy and its carbon footprint.

Should we call a world sitting on a time ticking bomb a free world?

Blaming the other is not going to help either…

Super fast train can you slow down

Blah( )

{

blah blah ;

Blah blah blah blah

}

Cout <<Talking blah blah

So you can use Ockham's razor both for philosophy and judging algorithms

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

I'm gonna eat Honey Butter Chips!!!

wow

First English person who pronounces "Voilà" quite correctly 🙂

Lower your speed of speech

Good

Learning tip for this video: Pause….a lot.

what is log

nice

Usa

I need to know what happened to you in Indianapolis for them to deserve that burn. 😆

Neat!

YOOOOUUUU TAAALK TOOOO FAAAAAAAAAAAAAAAST

YOU TALK TOO FAST!

YOU TALK TOO FAST!!

YOU REALLY TOO FAST!!!

PLEASE READ THIS:

YOU TALK TOO FAAAAAAAAAAST!!!!!!!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 ! 😀

Thank you a lot!

She looks like a female Austin Powers.

Thanxs for the info!!! 👍❤

Very speed language

She reminds me of felicity smoak from arrow

Spryngivevo

I still don't get it

You're talking way too fast. Put down the caffeine. Peace.

Why she talks so fast?

What is spaghetti code!

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

Anybody else notice that they filmed at the "Chad and Stacey" studio

This lady raps faster than twista

noice

oh my god that's so fast

HI

THE BEST APP FOR PC TO EXPERIENCE ALGORITHM

THANKS 😘

Too fast

Isn"t it actually n^2 – n for the selection sort? Edit: I also watch this just for fun.

👍👍👍😓