Skip to main content
Loading Explore guides…
Introduction to Algorithms · Acedra
Home
Explore
Computer Science
Introduction to Algorithms
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
53 segments
Copy
Hide video
0:12
good morning everybody my name is jason kuh i'm going to be teaching uh this class in uh introduction to algorithms with uh two other instructors here uh faculty in the department uh eric domain and justin solomon uh they're excellent people and so uh they will be working on uh teaching this class with me i will be teaching the first lecture and we'll have uh each of them teach one of the next two lectures and then we'll go from there yeah so uh that's this is intro to algorithms okay so we're going to start talking about this uh course content now what is this course about it's about algorithms right introduction algorithms really what the course is about is teaching you to solve computational problems but it's more than that it's not just about teaching you to solve computational problems so solve goal
1:16
one solve computational problems but it's more than that it's also about communicating those solutions to others and being able to communicate that your way of solving the problem is correct and efficient okay so it's about two more things uh prove correctness
1:53
argue efficiency and in general it's about communication communication i can't spell by the way uh communication of these ideas and you'll find that over the course of this class you'll be doing a lot more writing than you do in a lot of your other courses it really should maybe be a ci kind of class because you'll be doing a lot more writing than you will be coding for sure so it's really imp of course solving the the computational problem is important but really the thing that you're getting out of this class and other theory classes that you're not getting in other classes in this department is that we really concentrate on being able to prove that the things you're doing are correct and better than other things and being able to communicate those ideas to others and not just to a computer right to other people convince them that it's correct okay so that's what this class is about so what do we what do i mean when i say solve a computational problem what is a problem
3:06
what is an algorithm right i know people make fun of me because i start with this question but i mean anyone want to answer that question
3:17
no what's a problem computationally no okay so it's not such a stupid question yeah something you want to compute okay yes that's that's true right but kind of a little bit more abstractly what i'm going to think of a computational problem being and this is where uh kind of your prerequisite and discrete mathematics should come in right it's a problem is kind of you've got a set of inputs inputs okay maybe i have uh one two three four five possible inputs i could have to my algorithm okay then i have a space of outputs okay outputs and maybe i don't know maybe i have more of them than i do inputs but these are the possible outputs to my my problem and what a problem is is a binary relation between these inputs and outputs essentially for each input i specify which of these outputs is correct right it doesn't necessarily have to be one right if i say give me the index in an array containing the value five there could be multiple fives in that array and so any of those indices would be
4:39
correct so uh maybe this guy maps to that output and maybe this guy maps to i don't know two or three outputs right this input goes to one two i don't know there's a there's some kind of mapping here these edges represent a binary relation it's kind of a graph a bipartite graph between these inputs and outputs and these are specifying which of these outputs are correct for these inputs all right that's really the formal definition of what a problem is now generally if i have a problem and a computational problem i'm not going to specify the problem to you by saying okay for input 1 the correct answer is 0. and for input 2 the correct answer is 3 and so on and so forth that would take forever right usually what we do when defining a problem is specify some kind of predicate saying that oh we can check if i give you an input and an output i can check whether that output is correct or not that's usually how we define a problem is if i i'm checking for whether this index
5:51
contains a five i can just go to that array look at index five and say or that the index you gave me and see if it equals five right so usually we're putting it in terms of predicates because in general we don't really want to talk about small instances of problems so let's say i had the problem of among the students in this classroom do any pair of you have the same birthday okay all right well probably if there's more than 365 of you the answer is yes right right that by what pigeonhole principle right two of you must have the same birthday right but so let's let's generalize it a little bit say that i don't know i need a bigger space of birthdays for this question to be interesting maybe i tack on the year maybe i tack on the hour that you were born and that's a bigger space of inputs and i wouldn't necessarily expect that two of you would be born in the same year on the same day in the same hour right that would be a little less likely in fact as long as that space is larger
6:58
than something like the square of the number of you right then i'm less likely than then than even to uh to have a pair of you that that's a kind of a birthday problem you may have seen in uh 0-4-2 potentially right but in general i don't i don't i'm not going to mess with probability so much here i want a deterministic algorithm right a way of checking whether two of you have the same birth time let's say okay so uh in general in this class we're not going to concentrate on input such as is there a pair of you in this class that have the same birthday that's kind of boring right uh i i could just say well uh i i could do a lot of different things but what we we do in this class this is first a fixed classroom of you i want to make algorithms that are general to any classroom right to go to your recitation i want an algorithm that will apply to your recitation an algorithm that not only applies to this classroom but also the machine learning class before you
8:12
right i want an algorithm that can change its it can accept an arbitrarily sized input right here we have a class of maybe 300 400 students right but i want my algorithm to work for a billion students right like maybe i'm trying to check if there's a match of something in the facebook database or something like that right okay so in general uh we are looking for general problems that have arbitrarily [Music] sized inputs right so these these inputs could grow very large but we want a kind of a fixed size algorithm to solve those problems okay so what is an algorithm then
9:19
i really can't spell i told you okay i didn't lie to you um so an algorithm is a little different than a problem of problem specification i can state to you what this graph or i can tell you what this graph looks like an algorithm is really i don't know what the outputs are i don't know what these edges are but i want to i want a fixed size kind of machine or procedure that if i give it an input it will generate an output and if it generates an output it better be one of these correct outputs right so if i have an algorithm that takes in this input i really want it to output this output or else it's not a correct algorithm similarly if for this one it could output any of these three outputs but if it outputs this guy for this input that would not be a correct algorithm right and so generally what we want is a an algorithm is a function it takes inputs to outputs right an algorithm is some kind of function right that takes these inputs maps it to a single output
10:28
and that output better be correct based on our problem okay so that's what our algorithm is uh it solves the problem if it returns a correct output for every uh problem input that is in our domain okay and the example for uh does anyone have a possible algorithm for checking whether any two of you have the same birth time as specified before
10:57
i'm going to let someone else have a try sure just ask everyone one by one
11:05
ah great so uh what your colleague has said is a great algorithm well essentially what it's going to do is i'm going to enter i'm going to put you guys in some order okay i'm going to give each of you a number one through however many number of students there are in this class and i'm going to interview you one by one right i'm going to say what's your birthday anytime we'll write it down right i'm going to put in in some kind of record okay and then as i keep interviewing you i'm going to find out your birthday i'm going to check the record i'm going to look through all the birthdays in the record if i find a match right then i return yay i found a pair and i can stop otherwise if i get through the record list i don't and i don't find a match i just stick you at the end of the record right i add you to the record and then i move on to the next person i keep doing this okay so that's that's a proposed algorithm for this birthday problem for birthday problem what's the algorithm here
12:11
maintain a record
12:20
interview students students in some order
12:33
and what does interviewing a student mean it means two things it means check if birthday in record and if it is return a pair so return pair otherwise add a new student to record and then at the very end if i go through everybody and i haven't found a match yet i'm going to return that there is none right okay so that's a statement of an algorithm that's kind of the level of description that will be looking for you in the theory parts of this theory questions that we ask you on your problem sets right it's a verbal description in words that you know it's maybe not enough for a computer to know what to do but if you said this algorithm to any of your your friends in this class right they would at least understand what it is that you're doing yeah does an algorithm have to be a pure function mathematical pure function in the does a an algorithm have to be a pure function in the mathematical sense uh as in it needs to map to a single output
14:11
so we're talking about kind of a functional programming definition of uh of a of a of a function right this is um i am talking about the mathematical i have a binary relation and this thing has an output for every input and there is exactly one output to every input that's that's the mathematical definition of function that i'm using for when i'm defining an algorithm yeah so basically is an algorithm like uh like a plan yeah an algorithm is a procedure that somehow i can do whatever i want but i have to take one of these inputs and i have to produce an output and at the end it better be correct right so it's just a procedure you can think of it as like a recipe you can think of it it's just some kind of procedure right it's a a sequence of things that you should do and then at the end you will return an output okay so here's a possible algorithm for solving this birthday problem okay now i've given you what i argue to you or i'm asserting to you is a solution to this birthday problem
15:24
and maybe you guys agree with me and maybe some of you don't right so how do i convince you that this is correct right well if i had you know if i was just running this algorithm on say the four students in the front row here right i could argue it pretty well to you i could go through every you know i could assign these for people birthdays in various combinations of either their none of them have the same birthday some two of them have the same birthday i could try all possibilities and i could go through lots of different possibilities i had to check that this algorithm returns the right answer in all such cases right but when i have i don't know 300 of you that's going to be a little bit more difficult to argue and so if i want to argue something is correct in mathematics i want to prove something to you for some large value what kind of technique do i use to prove such things yeah induction right and in general what what we do in this class what we do
16:31
is as a computer scientist is we write a constant sized piece of code right that can take on any arbitrarily large size input right if it's if the input can be arbitrarily large but our code is small then that code needs to loop or recurse or repeat some of these lines of code in order to just read that output right and so that's another way you can arrive at this conclusion that we're going to probably need to use recursion induction and that's part of the reason why we ask you to take a course on proofs and and inductive reasoning and discrete mathematics before this class okay so how do we prove that this thing is correct
17:29
we got to use induction so how can we set up this induction
17:38
what do i need for an inductive proof sure base case we need a base case uh we need some kind of uh a predicate yeah but we need some kind of statement of a hypothesis of something that should be maintained right and then we need to have an inductive step which basically says i take a small value of this thing i use the inductive hypothesis and i argue it for a larger value of my well-ordered set that i'm inducting over right okay so in uh for this algorithm if we're going to try to prove correctness what i'm going to do is i'm going to what do i want to prove for this thing that at the end of interviewing all of you that my algorithm has either already it has returned with a pair that match or if we're in a case where there wasn't a mat it wasn't a pair somewhere in my set that it returned none right that would be correct right so how can i generalize that concept to make it something i can induct on right what i'm going to do is i'm going to say let's say after i've interviewed the
18:51
first k students right if there was a match in those first k students i want to be sure that i ever returned a pair right because if after i interview all of you i've maintained that property then i'll be sure at the end of the process i will have returned a pair if one exists so here's going to be my inductive hypothesis sis okay if first k students
19:38
contain a match
19:48
algorithm returns a match
19:54
before interviewing say student k plus 1. okay so that's going to be my inductive hypothesis now if there's n students in this class right and at the end of my thing i'm trying to interview student n plus one oh student n plus one is not there if i have maintained this then if i replace k with n then i will have returned a match before interviewing the last student or the when i have no more students left and then this algorithm returns none as it should right okay so this inductive hypothesis sets up a nice variable to induct on right this k i can have increasing up to n starting at some base case so what's my base case here
21:00
my base case is the easiest thing i can do sure two that's an easy thing i could do i could check those possibilities but there's an even easier base case yeah there's an even easier base case than one zero right after interviewing zero students i haven't done any work right certainly the first zero can't have a match right and so this predicate this inductive hypothesis is true just because this uh initial predicate is false right so i can say you know base case zero check definitely this predicate holds for that okay now we get to go for the uh the meat of this thing right assume the inductive hypothesis true for k equals say some k prime okay and we're considering k prime plus one right
22:15
then we have two cases one of the nice things about induction is that it isolates our our problem to not consider everything all at once but break it down into a smaller interface so i can do less work at each step right so there are two cases either the first k already had a match right in which case by our inductive hypothesis we've already returned the correct answer right the other case is the it doesn't have a match and we interview the k plus one student the k prime plus one student if there is a match in the first k prime plus one students then it will include k plus k prime plus 1 the student k prime plus 1 because you know otherwise there would have been a match in in the things before it right so there are two cases if k contains match k prime if first k contains match already
23:34
returned turn turn it by induction right else
23:48
if k prime plus one students contains match
23:56
the algorithm checks all of the possibilities k prime checks cape against against all students essentially by brute force it's a case analysis i check all of the possible possibilities right this check if birthday is in record i haven't told you how to do that yet but if i'm able to do that i'm going to check if it's in the record if it's in the record then there will be a match and i can return it otherwise i have uh re-established the inductive high policy hypothesis for the k prime plus one students does that make sense guys yeah okay so
24:50
that's how we prove correctness this is a little bit more formal than we would ask you to do in this class all the time but it's definitely sufficient you know for the levels of arguments that we'll ask you to do the bar that we're usually trying to set is if you communicated to someone else taking this class what your algorithm was they would be able to code it up and tell a stupid computer how to do that thing okay so any any questions on induction you're going to be using it throughout this class and so if you're unfamiliar with this line of argument then you should go review some of that that would be good okay so that's correctness being able to communicate that the problem the algorithm we stated was correct now we want to argue that it's efficient right what does efficiency mean
25:59
efficiency just means not only how fast does this algorithm run but how fast does it compare to other possible ways of approaching this problem right so how could we measure how fast an algorithm runs this is kind of a silly question yeah yeah just well i mean just record the time it takes for a computer to do this thing right now there's a problem with just re coding up an algorithm telling a computer what to do and timing how long it takes why yeah it would depend on the size of your data set okay we expect that but there's a bigger problem there yeah it depends on the strength of your computer right so i would expect that um you know if i had a watch calculator and i programmed it to do something right that might take a lot longer to solve a problem than if i asked you know ibm's research computer right to solve the same problem using the same algorithm even with the same code right because its underlying operations are much faster right how it runs is much faster
27:24
so i don't want to count how long it would take on a real machine i kind of want to abstract the time it takes the machine to do stuff out of the picture what i kind of want to say is let's assume that each kind of fundamental operation that the computer can do takes some fixed amount of time okay how many of those kinds of fixed operations does the algorithm need to perform to be able to solve this problem right so here we don't don't measure time instead count kind of fundamental operations okay we'll get to what some of those fundamental operations are in a second but the idea is we want a measure of how well an algorithm uh performs not necessarily an implementation of that algorithm right kind of an abstract notion of how well this algorithm does and so what we're going to use to measure time or efficiency right is something called asymptotic analysis anyone here understand what asymptotic analysis is probably since it's in both of your prerequisites i think
28:47
uh but we will go through a a formal definition of uh asymptotic notation in uh recitation tomorrow and you'll get a lot of practice in comparing functions using an asymptotic analysis but just to give you an idea right the idea here is we don't measure time we instead measure ops and like your colleague over here was saying before we expect
29:18
uh performance i'm going to use performance instead of time here we expect that to depend
29:29
on size of our input right if we're trying to run an algorithm to find a birthday uh in this section we expect the algorithm to run in a shorter amount of time than if i were to run the algorithm on all of you right so we expect it to perform differently depending on the size of the input and how differently uh is how we measure performance uh relative that input usually we use n as a variable for what the size of our input is right but that's not always the case so for example if we have a an array that i give you an n by n ray right that we're going to say n but what's the size of our input how much information do i need to convey to you to give you that information it's n squared right so that's the size of our input in that that context right or if i give you a graph it's usually the number of vertices plus the number of edges that's how big how much space i would need to convey to you that graph that information okay so you we compare how fast an algorithm is
30:44
with respect to the size of the input right and if that we'll use the asymptotic notation we have big o notation which corresponds to upper bounds we'll have omega which corresponds to lower bounds
31:12
and we have theta which corresponds to both right this thing is tight it is bounded from above and below by a function of this form okay
31:29
now we have a couple common ways a com a couple common functions that algorithms their running time we have a couple common functions that uh relate an algorithm's input size to its performance some some things that we saw all the time does it can anyone give me some of those say again sorry sorry so like a function i'm not asking this question well but has anyone heard of a linear algorithm a linear time algorithm right that's basically saying that the side the running time of my algorithm the performance of my algorithm is linear with respect to the size of my input right yeah say it again like putting something in a list okay so that's there's there's a lot behind that question that we'll go into later uh this week uh but that's an example of if i do it in a silly way i stick something in the middle of a list and i have to move everything that's an operation that could take linear time right okay so uh linear time is is a type of function we've got a number of these i'm going to
32:50
start with uh this one does anyone know what this one is constant time okay basically no matter how i change the input the amount of time this running time the the performance of my algorithm takes it doesn't really depend on that okay the next one up is something like this this is logarithmic time okay we have theta n which is linear and log n right sometimes we call this log linear but we usually just say n log n okay we have a quadratic running time in general if i have a constant power up here right it's n to the c for some constant this is what we call polynomial time right we're as long as c is some constant and this right here is what we mean by efficient in this class usually right in other classes right when you have big data sets maybe this is efficient right but in this class generally what we mean is polynomial and as you get down this thing these are things are more and more efficient okay there's one class i'm going to talk to you about over here
34:13
which is something like uh let's do this 2 to the theta of n right exponential time this is some constant to a function of n that's say super linear uh that's going to be uh you know pretty bad why is it pretty bad if i were to plot some of these things as a function of n right let's say i plot values of up to a thousand on on my n scale here okay what does constant look like maybe this is a thousand up here too what does a constant look like looks like a line right it looks like a line over here somewhere it could be as high as i want but eventually anything that's an increasing function will get bigger than this right and on this scale if i use log base 2 or some reasonable small constant what does log look like well let's let's do an easier one what does linear look like yeah this right that's what i saw a lot of you doing okay that's linear that's the kind of base that we're comparing everything against what does log look like like this okay but on at this scale right at this scale
35:43
really it's much closer to constant than linear and actually as n gets much much larger this almost looks like a straight line it almost looks like a constant so log is almost just as good as constant right what does exponential look like it's the exact inverse of this thing right right it's almost an exact straight line going up right so this is crap this is really good almost anything in this region over here is better right at least i'm gaining something uh i i'm not i'm i'm able to not go up too high relative to my input size so quadratic i don't know something like this and n log n is something like this and log n after a long time really starts just looking linear with a a constant multiplied in front of it right okay so these things good that thing bad okay that's what that's trying to convey all right so how do we measure these things if if i don't know what my fundamental operations are that my computer can can can use right so we need to define
37:03
some kind of model of computation
37:12
for what our computer is allowed to do in constant time in a fixed amount of time right in general what we use in this class is is a machine called a word ram which we you know use for its theoretical brevity all right word ram it's kind of a loaded term what do these things mean it means i have what can some does someone know what ram means random access memory right it means that i can randomly access different places in memory in constant time that's that's the assumption of random access memory basically what our model of a computer is is you have memory memory which is essentially just a string of bits it's just a bunch of ones and zeros right and we have a computer like a cpu right which is really small it can basically hold a small amount of information but it can change that information right it can operate on that information and it also has instructions to randomly access different places in memory bring it into the cpu act on it and read it back
38:32
that makes sense but in general we don't have an address for every bit in memory every zero and one in memory we actually does anyone know how modern computers are addressed
38:54
okay so so we're gonna get there actually what a modern computer is addressed in is bytes okay collections of eight bits so there's an address i have for every eight bits in memory consecutive eight bits in memory and so if i want to pull something in into the cpu i give it an address it'll take some chunk right and bring it into the the cpu operate it on it and spit it back okay how big is that chunk this goes to the the answer that you were asking which or saying which is it's some sequence of some fixed number of bits which we call a word okay a word is how how big of a chunk that the the cpu can take in from memory at a time and operate on okay in your computers how big is that word size 64 bits right that's how much i can operate on a time when i was growing up when i was your age okay my word size was 32 bits and that actually was a problem for my computer because
40:06
in order for me to be able to read to address in memory i need to be able to store that address in my cpu in a word right but if i have 32 bits how many different addresses can i address i have a limitation on the memory addresses i can address right so how many different memory addresses can i address with 32 bits 2 to the 32 right that makes sense well if you do that calculation out how big of a hard disk can i have to access it's about four gigabytes right so when i in my day all hard drives were limited to you know being partitioned even if you had a bigger than four gigabyte hard drive i had to partition it into these four gigabyte chunks which you know the the computer could then read on to right that was very limiting actually that's a restriction with 64 bits what's my limitation on memory that i can address byte addressable turns out to be something like uh 20 exabytes to put this in context all data that google stores on their servers on all drives throughout the world it's
41:30
about 10 right so we're not going to run out of this limitation very soon right so what do we got we've got a cpu it can address memory what are the operations i can do in this cpu i have binary operations i can compare two words in memory and i can either do you know integer
42:00
arithmetic kind of logical operations
42:08
bitwise operations but we're not going to use those so much in this class and i can read and write from an address in memory a word in constant time those are the operations that i have available to me on most cpus some cpus give you a little bit more power but this is generally what we analyze algorithms with respect to okay
42:36
but you'll notice that my cpu is only built to operate on a constant amount of information at once generally two words in memory an operation produces a third one and i spit it out right it takes a constant amount of time to operate on a constant amount of memory if i want to operate on a linear amount of memory end things how long is that going to take right if i just want to read everything in that thing it's going to take me linear time right because i have to read every part of that thing okay so in general what we're going to do for the first half of this class mostly first eight lectures anyway is talk about data structures and it's going to be concerned about not operating on constant amount of data at a time like our cpu is uh doing but instead what it's going to do is operate on store a large amount of data and support different operations on that data okay so if i had a record that i want to maintain to store those birthdays that we had before
43:52
i might use something like a static array right which you guys maybe are not familiar with if you have been working in python as your only programming language okay python has a lot of really interesting data structures like a list and a set and a dictionary and all these kinds of things that are actually not in this model there's actually a lot of code between you and the computer and it's not always clear how much time that interface is taking right and so we're going to do starting on thursday is talk about ways of storing a non-constant amount of information to make operations on that information faster so just before you go i just want to give you a quick overview of the class to solve an algorithms class in algorithm problem in this class we essentially have two different strategies we can either reduce just to using the solution to a problem we know how to solve or we can design our own algorithm which is going to be recursive in nature we're going to either put stuff in the
45:01
data structure and solve a sorting problem or search in a graph and then to design a recursive algorithm we have various design paradigms this is all in your notes but this is essentially the structure of the class we're going to spend quiz 1 the first to eight lectures on data structures and sorting second quiz will be on shortest paths algorithms and graphs and then the last one will be on dynamic programming okay that's the end of the first lecture thanks for coming
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat