Transcript

Good morning everybody. My name's Jason Ku. I'm going to be teaching this class in introduction to algorithms with two other instructors here, faculty in the department, Eric Demaine and Justin Solomon. Uh they're excellent people and so they will be working on teaching this class with me. I will be teaching the first lecture and we'll have each of them teach one of the next two lectures. And then we'll go from there. Yeah, so that's this is intro to algorithms. Okay, so we're going to start talking about this course content now. What is this course about? It's about algorithms, right? Introduction to 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 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 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 important 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 What do I mean when I say solve a computational problem? What is a problem? 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? 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 kind of your prerequisite in 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 1 2 3 4 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 uh 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 correct.

So 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. Here's a Here's some kind of mapping here. These edges represent a binary relation. It's kind of a graph of 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 computational problem I'm not going to specify the problem to you by saying, "Okay, for input one the correct answer is zero and for input two the correct answer is three 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 am checking for whether this index contains a five I can just go to that array, look at index five and say 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 than something like the square of the number of you, right?

Then I'm less likely than than than even to to have a pair of you that that that's a kind of the a birthday problem you may have seen in uh 042 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 in general in this class we're not going to concentrate on inputs such as is there a pair of you in this class that have the same birthday? That's kind of boring, right? 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 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. I want an algorithm that not only applies to this classroom, but also the machine learning class before you, right? I want an algorithm that can change uh it's 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 uh general problems that have arbitrarily sized inputs, right?

So these these inputs could grow very large, but we want to kind of a fixed size algorithm to solve those problems. Okay? So what is an algorithm then? rithm. What what am I No. I really can't spell. Told you. Okay. I didn't lie to you. Um So an algorithm is a little different than a problem. A 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 what I want to I want to fix 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, 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 uh Does anyone have a a possible algorithm for checking whether any two of you have the same birth time as specified before? I'm going to let someone else have a try. Sure. Just ask everyone one by one and every time see if they have 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?" And then I'm going to write it down, right?

I'm going to put it in a 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?

Uh maintain uh a record. Interview students students in some order. And what does interviewing a student mean? It means two things. It means uh check if birthday in record. And if it is, return a pair. So, return pair. Otherwise, add uh 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 we'll be looking for you in the theory parts of this the theory uh questions that we ask you on your problem sets, right?

It's a verbal description in words that uh you know, I it's maybe not enough for a computer to know what to do, but if you said this algorithm to any of your the your friends in this class, right? They would at least understand what it is that you're doing. Yeah. But does an algorithm have to be a pure function in the mathematical sense? Uh 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? Uh as in it can't modify some external state. It can't take in a state. It can't like do IO. Uh so, we're we're talking about kind of a functional programming definition of uh of a of a of 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 basically isn't algorithm like 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 uh It's just some kind of procedure, right?

It's a uh 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 have given you what I argue to you or I'm asserting to you is a solution to this birthday problem, 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 uh every uh you know, uh I could assign these four 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 could just 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 it as a computer scientist is we write a constant-size 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, uh and that's part of the reason why we ask you to take a 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? We got to use induction. So, how can we set up this induction?

What do I need for an inductive proof? Sure. Base case. We need a base case. Uh we need some kind of uh a 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 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 first K students, right? If there was a match in those first K students, I want to be sure that I've a 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 uh contain a match, uh algorithm returns a match. before interviewing say student K plus one. 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's 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? 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, this 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? 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 inter- 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'th student, the K prime plus one'th student. If there is a match in the first K prime plus one students, then it will include K plus K prime plus one, the student K prime plus one, because you know, otherwise there would have been a match in in the things before it, right? So, there are two cases. If K uh contains match K prime. If first K contains match, already returned turn turn-ed by induction. Right? Else, if K prime plus one students contains match, the algorithm checks all of the possibilities. K prime checks K against against all students essentially by brute force.

It's a 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 would have uh reestablished the inductive hypothesis hypothesis for the K prime plus one students. Does that make sense, guys? Yeah. Okay, so 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 the problem al- the algorithm we stated was correct. Now, we want to argue that it's efficient, right? What does efficiency mean?

Uh 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 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. 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 re- 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. 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 uh performance I'm going to use performance instead of time here. We expect that to depend 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 a 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 is how we measure performance 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 array, 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 it how much space I would need to convey to you that graph, that information. Okay, so you we compare how fast a an algorithm is with respect to the size of the input, right? And if that uh uh we'll use the asymptotic uh notation. We have big O notation, which corresponds to upper bounds, we'll have omega, which corresponds to lower bounds, 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? Now, we have a couple common ways a com- a couple common functions that algorithms their running time uh 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 Can anyone give me some of those? Say again? Inserting a node. Uh sorry sorry. So, like a function I'm 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 si- the the running time of my algorithm performance of my algorithm is linear with respect to the size of my input, right? Yeah. Say again? Like putting something in a list. 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 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, n 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 some 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, which is something like uh Let's do this. Two to the theta of n, right? Exponential time. This is some constant two 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 1,000 on on my n scale here. Okay? What does constant look like? Maybe this is 1,000 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 two 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, 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'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. N log n after a long time really starts just looking linear with a a constant multiplied in front of it, Okay. So, these things good, that thing bad, okay? That's what that's trying to convey. 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 some kind of model of computation 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 is 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. 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 Do Does anyone know how modern computers are addressed? Yeah. Okay, so so we're going to 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 to the the CPU, operate 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 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 4 GB, right? So, when I In my day, all hard drives were limited to, you know, being partitioned even if you had a bigger than 4 GB hard drive, I had to partition it into these 4 GB chunks, which, you know, the the computer could then read onto, 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 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? Generally, I have binary operations. I can compare two words in memory, and I can either do, you know, integer arithmetic, kind of uh logical operations, bitwise operations. Uh we're not going to use those so much in this class. And I can read and write from the 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? 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? Uh 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, n 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, uh 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, what 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 uh you go, I just want to give you a quick uh overview of the class. To solve an algorithms class in algorithm problem in this class, we essentially have two different uh strategies. We can either reduce to 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 data structure, we're going to 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 one, the first 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.

Seek backward 5s ←
Longer seek (10s) Shift ←
Play Space Seek forward 5s →
Longer seek (10s) Shift →
0:00 Auto-scroll A Copy link at current time S

1. Algorithms and Computation