Transcript

Welcome everybody uh to the second-to-last lecture of 6.006. Uh in this lecture, we've mostly covered all of the testable material that we're going to have on uh the final or on quiz three. Right? Today, really what we're talking about is putting into context all the material that we've uh learned over the course of the term at a high level and talk about where we can go from here in terms of other theory classes and other classes in the department that are related to this material. Now, uh most things in the department are in some way related to this material, and so that's why this is a foundational course.

Uh but we're going to try to talk about it from a high level and to talk about how uh some future uh things that you might be interested relate. Okay. So, we started out the term in lecture one talking about 6.006, and we had four main goals that we had for our course, really three main goals. Uh does anyone remember what those goals were? It was uh so uh it was Uh you got to the last one first. The first one was to solve hard computational problems, right? To be able to solve problems. Okay? So, this is kind of like the the let's uh make an algorithm part of of the course, right? One, solve hard computational problems.

I guess hard here maybe should be in quotes because we saw in the last lecture what hard means in a technical sense, right? Hard could mean that there's no efficient algorithm that we know how to solve a problem on. That's getting a little bit of ahead of ourselves. Computational problems with algorithms is really the key part about this goal. It's kind of the same goal that you have in a class like 6.001 or 6.009, right? You're trying to convince a computer that you solved a problem. Okay? On a finite set of inputs. But really what this class is about is two other things, which uh is more about communication to people rather than computers.

Right? Your your algorithm might be correct or efficient, but you need to be able to communicate that to humans, and that's what the other two goals are, right? So, second one is uh argue correctness. Basically, that the thing that I'm doing to my inputs is always going to lead me to a correct output. Right? No matter No matter what input I give it, any valid input, there could be a infinite space of possible inputs, and in this class that that's the case because we want our input size to grow arbitrarily large. We need to be able to argue correctness that it's going to return me the correct thing no matter what my inputs are.

And in order to do that, that's essentially that's that's 6.042, right? This This whole class has basically been applied 6.042. Right? I've given you some procedures, and you have to prove things about these procedures. Or most of the time we proved it for you, and then you've used them as black boxes, right? But that's that's a lot of what this class is about. And the third one is efficiency, right? Argue argue that it's good. For lack of a better thing, this is efficiency. What does good mean? Well, that was hard to know at the beginning of our class, and so we set up this model of computation, a framework through which we could uh determine how good or bad our algorithms were by saying by defining a model of computation, saying what things we can do in constant time, and then just building off of that.

Right? So, this is basically our model, you know, plus some, you know, asymptotics or something like that. Ran out of space. What? It's about scalability. Yeah, this is about scalability. This is a model of computation tells us how how much time we can spend, but it's compared to our input size. Right? This is always about how does our algorithm perform relative to the rate that our problem size grows. Right? And so that's what we mean by good. And in this class we don't tend to talk about constant size problems. It's about how algorithms can scale as you have arbitrarily large inputs. That's why we need recursion and induction to be able to prove things about our algorithms because they're for arbitrary n.

And that's why we need uh you know, this relative to input size, the growth factor of of our algorithm's performance relative to the input. Okay. And then the last thing is kind of to me one of the most important things is communicating these things to another human, right? So, communication is key here, right? If you can always write good code that's always right, good for you. I can't do that all the time. But that might mean that you can be very uh a competent independent computer programmer. Right? But you're going to be limited in what you can do if you're uh if you're only able to rely on yourself.

Right? A lot about computer science is working with others to solve computational problems, and when you're working with others to solve computational problems, you need to be able to communicate with them, and you need to be able to communicate them both what it is you're doing and why it is you're doing it, right? That it's you're doing the correct thing and that it's efficient. Right? And so that's a big part about what this course is. It's at the end of the day on your quiz, if you write down um you know, Python script for a correct algorithm, but we don't know what it's doing, but it's correct, we're not going to give you full points on that because you're not satisfying the conditions of this class.

Right? It's really about the communication here. Okay. So, just to review since we've not uh discussed uh how the most recent lecture fits into your problem sets, we didn't have any problem sets that covered complexity. So, how does that fit in? Well, argue that this is that the the ways that we're solving our problems are good. What we proved in the last lecture was that most problems cannot be solved good. Right? They can't be solved in polynomial time with respect to the size of your input. However, most of the problems that we think about in a sense, I can I can prove to you that it's a yes uh solution.

I can show you a uh a simple path in this graph that has a certain uh length, or I can show you a subset that sums to a certain value in a particular problem. I can give you a certificate that I can prove to you in a reasonable amount of time that yes, I can prove to you that this is the answer to this thing is correct. And that's what we uh talked about in the last lecture, what So, not always good uh algorithms to solve problems. But many problems we think about can be either checked in polynomial time. This is the concept of having a certificate that I could give you of polynomial size that could be checked in polynomial time, right?

In a In a sense, that's a a way check checked in polynomial time. This leads to our class of decision problems NP. Or, you know, can be uh solved by brute force in exponential time, right? Most of the things that we've talked about in this class fall into one of these two categories, right? We can just brute force over the combinatorial space of possible outputs and check to see if they're correct. Right? Or I can give you a certificate basically saying uh look, I can solve that actually anything that's of this form can be checked in this form because there's only a polynomial number of things to check or sorry, an exponential possible number of certificates of polynomial length to check.

Um but basically this is saying that the the problems that we think of mostly fall into these two categories and so there usually are algorithms to solve the problems that we care about even if most random problems in terms of bit strings that we gave an analysis in the last lecture actually prove that most random problems are not solvable. Right? Though in a sense the problems we think about are not random. They kind of have this structure that they can be checked pretty quickly. Okay. So, that's kind of what we mean when we're talking about complexity. For the purposes of the final, you'll be able to see on your final exam uh practice um problems that we're going to give you.

Most of what we uh cover uh in terms of material on the final that will be covered that will be testing the lecture 19 material will be in terms of these definitions. Do you understand what the the decision problem class NP is? Exp is? Do you know how these relate to each other? Exp is definitely a super set of NP here, right? NP nestles inside here. They could be equal, probably not, right? Those are the types of things that we would address knowing kind of a directionality of a reduction, right? If you have a a problem A and a problem B right? And I know that this one is difficult by some measure.

Right? I already happen to know that it's you know, very hard, right? Like NP hard or something like that. If I can if if this is a problem that I'm interested in knowing the complexity about and I can prove that I can solve it if I had a black box to solve B any black box to solve B and I could make this reduction in polynomial time. And if this is hard, that means this can't be That means that if this is hard, then I better not be able to solve this in polynomial time. Right? Because then I would be able to solve this in polynomial time. So, that's basically the type of argument usually in a true false question we might have on the final exam for you to kind of understand the basic high-level definitions involved in what was talked about in lecture 19.

Hardness, right? The very most difficult problems of these classes and completeness Sorry. Uh anything harder than things in these classes where completeness is the ones that are in this set but at least as hard as anything in those classes. Okay? So, that's just to give you a brief overview of the only material that hasn't been tested but might be tested on the final. Okay? So, when we don't have a good algorithm we can actually prove that it doesn't might probably doesn't have a good algorithm. Uh and that's kind of a a problem that you'll be able to solve in future classes if you continue along this track.

Okay. So, what's the actual content that we talked about and this is a very high-level overview of why we're taking this class, why you're taking this class, right? But what is the content we actually covered? It kind of I I like to break it up into three units and kind of in a sense two sub units. Okay, so quiz one material and quiz two material was about showing you some nice black boxes, right? Basically, if I'm going to have inputs of non-constant size, it's going to be useful for me to be able to find things among those elements. Right? So, that's really what quiz one is all about. Right?

Data structures for finding things in uh non-constant constant size uh uh database. Sure. And when we were storing these things, we want to support maybe two different types of queries. Ones that were intrinsic to the items, what the items were and ones based on what an extrinsic order was placed on these items. Right? And that was a way in which we broke down how should I approach looking at this problem? I want to be able to support queries and maintain an extrinsic order on these things. I might want a sequence. Right? This is a sequence. Extrinsic order. Or I want to be able to look up is this thing in my set, right?

By by a key that we identify it with, a unique key. Right? So, this is some intrinsic uh queries and often order. Right? Not all like a hash table doesn't maintain any order on my keys. Right? But it does support intrinsic queries. Is this thing in my set or not? But we did show you other set data structures that do support a intrinsic order that allows me to see what the next larger and next previous uh the the the next larger or the next smaller item uh is in my set, right? So, here's a summary of those data structures that we had. I'm not going to go into how to use these things or how to choose from among them here.

That's what your quiz one review lecture was all about. Right? But basically the idea here is if we have a sequence, most of the time when you're programming being able to push and pop at the end of a list is pretty good, which is why Python, the most fundamental data structure that you have, is a list because it's a super useful thing. I just want to store a bunch of things, have random access to uh the say 10th element to my thing. But I'm not necessarily having to dynamically update uh the order of these things in uh dynamically. I don't necessarily have to insert something in the middle of the list.

Uh most of the time what I can do is put it at the end of the list and maybe swap it down into place if I need to. Right? So, that's why a list is super useful. A sequence AVL tree useful but not as ubiquitous as a linked list I mean as a dynamic array, sorry. I said linked list, I meant Python list, which is a dynamic array. Okay. So, the dynamic array tended to be in in in in your coding practice your most common sequence data structure here. Though we can get pretty good for this insert in the middle operation with a sequence AVL. Okay. Then for on the set data structure side, I kind of categorize these things into a couple different categories here in terms of the operations we can support on these things.

These are all intrinsic operations, finding things, inserting, deleting things. I think of the first three as being dictionary operations, right? I want to just look look up whether something's there. Whereas the last two are order preserving operations where it matters what the order these things are stored in. And so, as you can see from the uh you know, asymptotic complexity of the various operations here, the hash table is actually super good if you want to dictionary opera if you just want to support dictionary operations. But in the cases where you need to maintain order dynamically a set AVL is the way to go, right?

Uh but if you don't need it dynamic but you still need those order operations, a sorted array is just good enough if you don't need to change what they are, right? So, uh that's that's a a quick overview of quiz one type data structures material. But then we used most of these data structures to get faster sorting algorithms in different contexts, right? Basically everything on this list involved making a data structure and exploiting that data structure to get a better running time. All except for merge sort really. Right? The first two we we presented in terms of a priority queue. Right? Whether we used a sorted array or an array uh we we represented it at the end of lecture eight.

Um to get n squared running time, we generalized that down to to n log n by using a heap. That was a nice optimization, but we also got uh interesting data structures using an I mean interesting sorting algorithms using an AVL tree because of the power of maintaining a dynamic order over time. But then uh exploiting a direct access array to be able to sort in linear time for small bounded bounded in terms of the input polynomially bounded in terms of the input ranges of numbers, right? So, we we leverage that count direct access array to get counting sort. And then we kind of amplified that effect by sorting on a bunch of digits uh multiple times to get basically polynomial uh blow up in terms of the numbers that we could sort in linear time.

Okay? So, that's uh uh an overview of the content of quiz one. In quiz two, we were kind of like, "Okay, now you know how to find things within a a set of of just a flat list of things, right? You can put it in a data structure, but in a sense a graph is a special kind of data structure, right? That relates the different things in your input, right? So, uh if you've got um a bunch of vertices, right? There's a relation now between those vertices that are your edges. And this is a super useful framework in about discrete systems because you can think of a vertex as a state of your system and then connect these transitions as a graph, right?

That's That's the reason why I mean graphs are are awesome, right? But they're awesome because they can be used to model so many different things within our world, right? It's not just about, you know, road networks, right? It can also be about playing your favorite uh turn-based game, right? Like tilt, right? Okay. So, uh we we talked about a lot of different types of problems that you could solve, various algorithms with a focus on a bunch of different ways of solving single source shortest paths. And again, just like the sorting algorithms and just like the data structures we presented multiple of them because we had this trade-off of generality of the graph that they apply to contrasted with their running time, right?

So, I guess in in particular the the the top um uh line there is in some sense the most restrictive. We We don't have any cycles in our graph. That's a very special type of graph and we're able to get linear time. But then even if we do have cycles in our graph, we can do better if we have a bound on the weights in our in our thing, whether they be uh there's an easy conversion to a linear time algorithm via an unweighted process or whether these things are non-negative, so there can't be negative weight cycles and we don't have to deal with that. Okay. So, that's quiz two material. And then quiz three material was kind of applying this graph material to a recursive framework.

What was our recursive framework? Everyone say it with me. Dynamic programming and the framework was sort bot, right? Missing a letter, but sort bot, right? You can actually think of the quiz three material as uh as really an application of the graph material, right? What What are we doing in sort bot? We're defining a set of subproblems. This is a set of vertices in a graph. What is the relationship doing? It's saying what are the relation between the subproblems, right? Essentially defining the edges of a graph, right? And then this topological order and the base cases, all of these things are just saying what is the problem that I want to solve on this graph and how do I uh compute that for things that don't have any outgoing edges, right?

I need to start writing on the board again. This is graphs. There was uh uh sorting in here, too. This is basically an application. Okay, graphs was basically a relationship on these non-constant things. So, this was kind of like useful black boxes, right? That you can just bundle up and stick in some inputs, stick out some outputs, and and you're golden, right? Whereas quiz three was very different. The material in quiz three is very different. Dynamic programming Well, it was in some sense related to this graph material. I'm constructing a graph. I have to construct that graph. There's a creative process in trying to construct that graph.

I don't give you a set of vertices. Usually what I give you are a set of like a sequence or something like that, and you have to construct vertices, subproblems that will be able to be related in a recursive way, so you can solve the problem. This is a very much more difficult thing than these other things, I think, because there's a lot more creativity in this, right? In the same way that just applying reducing to the graph algorithms that we have is fairly easy, but actually doing some graph transformations to change the shape of the graph so that you can apply these algorithms, that's a harder thing to do, right?

These are these the the difficulty with these two sets of materials is very similar, right? Figuring out what the graph should be, figuring out what the subproblems should be and how they relate is really the entire part of the the the entire difficulty with solving problems recursively, right? And we've only given you a taste of solving problems recursively. In future classes like 6046, which is the follow-on to this one in the undergraduate curriculum, this is all about introduction to algorithms. The next one's about design and analysis of algorithms, right? It's quite a bit more difficult because we are we've mostly uh left it to you to use the things that we gave you or make your own algorithms based on this very nice cookbook-like framework that you can plug in a recursive algorithm to.

Now, actually that cookbook is super nice for any way of looking at a a problem recursively, but while uh uh while in dynamic programming the inductive hypothesis of of combining your subproblems is almost trivial, right? Uh in other types of recursive algorithms, that's not necessarily the case. Okay? Especially when instead of looking at all possible choices, for example, in a greedy algorithm where you're just looking at one of the choices, the locally best thing, and recursing forward, you're not doing all the work, right? You're not locally brute forcing, you're locally picking uh an optimal thing locally and hoping that it leads you to good thing.

That's a much harder algorithmic paradigm to uh to operate under, and so that's more like the material that you'll be talking about in 6046. Okay? So, uh that's 006, a a very quick uh overview of the content uh of this class. And we really like the structure of of how this this class is laid out because it gives you a fundamental idea of the things people use to store information on a computer and a sense of how you solve problems computationally and how to argue that they're correct and efficient, right? That's really what this problems this this this course is about. And if you feel like you enjoy this kind of stuff, that's where you go to take 6046, right?

And 6046 was actually the first algorithms class I ever took here at MIT uh as a grad student, actually. I uh I didn't This is This is hard for me, right? It was It's actually hard to look at these problems, these types and think in a computational way, especially having not taken this class, 6006. So, hopefully you guys are all in a better position uh than I was when I took it. There's There's two ways I like to think of the content in 6046. One is kind of just as an extension of 006, right? It's the natural follow-on to the things that we do in this class, right? They still talk about data structures.

This isn't the core part of 046, but they do touch on data structures for more complicated uh that that have more complicated analysis involved in them. It's really about, you know, usually in 046, stating what the algorithm is doing is not so hard, right? Basically, giving you the algorithm, number one here, is not so difficult to state what's happening in the algorithm. But the number two and number three here, arguing that that thing is correct and arguing that thing is efficient, that's where the complexity comes in. In 046, the design the the analysis part is quite a bit more complicated in 046 than in 006, right?

So, uh they they they uh solve a problem called union find and give a much uh we we talked a little bit about amortization. This goes into a much better a much for more formal way of proving things uh uh run in amortized time. Okay? So, this is basically amortization the uh what we call a potential analysis. It's basically making that algor- that that that that uh that notion that we talked about when we were talking about dynamic arrays of, you know, we're not doing this expensive thing too often. Basically, what we do is we keep track of the cost of all of uh sequence of operations and prove that the average cost is small, right?

That's that's kind of what this potential uh analysis is doing. It's a little bit more formal process for making that argument uh a little uh more formal. Right. Okay. So, then on on the graph side, right? This is kind of an extension of quiz one type material. This is What What is this union find data structure? It's basically it's a set type thing, right? Where uh I I can make a set of just a single element. I can take two sets, merge them together, make them their union, right? And then given an object, I I say, "Which set am I part of?" Right? Essentially, by electing a leader within a set and saying, "Return me a you know, a pointer to that one." Right?

And so, this can be useful in dynamically maintaining, say, the connected components in a dynamically changing graph. Supporting the query of, "Am I in the same component and as this other guy?" Right? That could be a very useful thing to know about a graph as it's changing. So, that's that's an application of this problem. And they get near constant performance uh for a lot of these these queries. It's not quite, but, you know, pretty close. Okay, on the graph side, they solve a number of uh very useful problems on graphs. Uh minimum spanning tree. So, I I'm I'm trying to find a tree connecting all of the vertices in a connected component of my graph.

And I'm trying to find what in a weighted graph, I'm trying to find the spanning tree that has minimum total weight, right? So, this is that's a problem a fundamental problem in graph weighted graph algorithms. Uh they've solved this via a greedy algorithm. Okay? Uh and network flows. Uh and I guess cuts, right? So, this is What is this? This is I'm given a a weighted graph. Uh basically, each of the um the weights correspond to a capacity. I can push water through along this edge, right? And I'm maybe given a source vertex and a and a sink vertex, right? And I want to say, "I want to shove water through the source vertex along the edges with their various capacities, and I'll get some amount of water on the other end in the source, right?" So, the question is, "What's the most amount of water that I can push through this?" Well, I could build build that pipe network with the different things and just do this experimentally.

I just stick a bunch of Maybe I I'm a mechanical engineer, so that that maybe makes sense to me, but you want to be able to just look at those numbers and be able to tell me how much water can I push through. That's what the kind of max flow in a network is talking about, and we give you some polynomial time algorithms in this class. Basically, incremental algorithms that kind of like Dijkstra or kind of like Bellman-Ford will incrementally update uh estimates to uh uh of of a max flow and and and improve them over time. Okay? Uh then on the ba- basically design paradigms, you've got more involved making your own divide and conquer algorithms, you know, dynamic programming algorithms.

Uh greedy algorithms. Basically, they go a lot more in depth in terms of how to design these algorithms in these paradigms than we do in this class. Okay? And then the last thing is we only touched on complexity. And in a sense, 046 is only going to touch on complexity. It's a very big field, right? But it will give you the tools to be able to prove that something is NP-hard. Whereas, we just kind of say that, "Oh, there's this thing called reduction." We didn't give you any uh problems in which you actually had to reduce one problem to another, and you'll do a lot more of that here. So, reductions.

So, in a in a big sense, 046 is really just a natural extension to the 006 material plus some additional stuff, which I'm going to get to in a second. Yeah, question? When do we add randomization for time paradigm? Uh I'm going to talk about that slightly in a in a separate I'll get to your question in just a second. I like to think of it as uh a separate topic, which I'll we'll go into right now. The separate topic I like to think of it as instead of being the natural extension to the things in in in the 006 units, what I'm going to do is kind of relax either what it means to have a correct algorithm or relax what it means to uh uh what what my model of computation is.

Okay? So, 006, this is kind of as an extension of 006, and this is kind of like 6046 as, you know, uh change my definition of what it means to be correct or efficient. So, we've already kind of done this a little bit in 006. Um I'm going to Basically, one of the things that we can do, which is what the question that uh a student asked a question about, was about randomized algorithms, which is a big part of 046, actually. Randomized uh analysis of algori- of of algorithms that are not deterministic, right? It's It's not guaranteed that it'll give you the same output every time or not guaranteed that it will do the same computations over the course of the algorithm every time, but it exploits some randomization.

And in 006, this is we've mostly not touched on this except in one area. Where did we use randomization? In hashing, right? Right? When we used hashing, what were we doing? What What What did we change the definition of correct versus efficient? We didn't really change the definition. What we did was we said that it was okay that sometimes our algorithm was slower than we we then then on in expectation, right? That's what we we meant there. We're relaxing the idea of efficient, but we're still saying it's good because most of the time it is good. Right? So, this there's two types of randomized algorithms.

Uh they have these weird names uh based on betting uh uh regions of the world, shall we say? There are uh This is L O Las Veg- Wait, it is Las. Okay. Vegas algorithms. Uh these are always correct, but probably efficient. In a sense, that's what hashing is, right? I'm always going to give you the right thing, right? Whether this thing is in my set or not, but some of the time it's inefficient, right? I have to look through a a chain of length of that's linear in the size of the things that I'm storing. Okay? And this is in contrast to a Monte Carlo algorithm, which is always efficient for some definition of efficient, but only probably correct.

And I mean, I could define you a hash table that has Monte Carlo semantics instead, right? Say for example, I I say that I'm going to it's going to be exactly the same as a hash table, except in store instead of storing all the things that collide in a in a place, I just store the first two, say. Right? Well, actually, that's actually going to be always efficient. I'm going to look through the things and see if it's in there. And the chain the chains that I'm storing there only have two things, it's going to be always efficient. It's always going to give me constant time. But some of the time it's going to be the wrong thing because I'm not storing everything in that chain.

Right? So, there's some probability that that's not going to be correct. Right? And so that's that's a different kind of if maybe I want my hash tables to always be fast, but I can afford to be wrong some of the time. I don't know. In practice, this is actually sometimes a good trade-off in real systems. Sometimes it's okay to be wrong some of the times if we get good performance. Okay. Uh so, but generally can do better uh if you allow randomization. And by better I mean, you know, usually we can get faster bounds on a lot of problems if we allow randomization and things aren't necessarily always correct or always efficient.

Okay? So, this is a big area in O 4 6 uh that requires a lot more analysis uh using uh ran uh randomness and probability. So, if you're uh need some uh primers on that, we didn't have a lot of this in in 006, but if you go on to 046, that's going to be a really important thing for you to brush up on. Okay? The next uh part on 006 is kind of changing what our definition of correct or efficient means. I mean, we've restricted ourselves in this class to a class of problems where we only talk about integers. Right? But there's tons of problems in this world, especially in scientific computing, where I want to be able to find out what the this real number is.

And I can't even store a real number on my computer, so what the hell, Jason? What are you talking about? Right? I can't do that on a computer. But what I can do is basically compute things in a numerical sense, numerical algorithms. And uh in O 4 6 a lot of times we put this in the context of continuous optimization. Continuous uh being the opportune word here, not discrete systems. You have a continuum of possible uh solutions, real numbers essentially. How do we do this on a computer that's a discrete system? Basically, what the what what in O in O 4 6, what you can do and in in other numerical methods classes, what you can say is, "Well, I know that you can't return me a real number.

I got that. Or or you can maybe have a model of computation that allows integers to represent other kinds of real numbers like radicals or rationals or something like that and I can do manipulations on those. But really, what these these algorithms are usually about is computing real numbers not completely, but to some bounded precision and I pay for that precision. Right? The more bits of precision I want on my number, I have to pay for them, right? So, this is basic I think of these as an approximation. Up up approximation of real number to some precision and I pay for precision with time. So, let's say, you know, I want to compute the square root of a number, I could have an algorithm just like the algorithms or I guess division, right?

Long division. You all know the algorithm of long division. You you you know, you put the quotient under here with these, you know, an A B and you get the C on top or whatever, right? That's an algorithm. That's a procedure using essentially small numbers. I'm only talking about the digits zero to nine here when I'm doing that algorithm. So, it's a procedure that only uses small integers to compute arbitrary precision of a division. Right? So, that's an algorithm and I have to pay time to get more digits. Right? So, that's that's an a a an example of this kind of how how we live in the world of real numbers when all we have is a discrete system.

Okay? And then the last kind of uh category I'd like to talk about here is is really approximation algorithms. Whereas this is kind of an approximation algorithm, I'm approximating my outputs, this is an approximation algorithm from the standpoint of well, there's a lot of problems that I can't solve efficiently. They're NP-hard. They're in they're in EXP or, you know, even harder problems. But uh maybe I'm okay with not getting the optimal solution. So, this is in the domain of optimization problems. So, most of the dynamic programming problems that we gave you were optimization problems or the shortest path problems, those are optimization problems.

Basically, the possible outputs are ranked in some way, right? The distance of a of a path that you return or something like that. They're ranked in some way. There's an optimal one, right? The one with the the smallest metric or something like that, right? Well, in an approximation algorithm, what I do is, "Okay, I I I get that it's computationally difficult for you to give me the longest path simple path in this graph or the shortest possible route for my traveling salesman, but maybe that's okay. I mean, my engineering spidey sense tells me that within 10% is fine, right? So, maybe instead of giving me the most optimal thing, can I give you an algorithm that's guaranteed to be within a certain distance from the optimal thing?

Right? Usually, we're looking for constant factor approximations, which are have low constant, or, you know, maybe even have to do for worse if such things don't exist. Okay, so that's approximation algorithms. You know, can we get close to an optimi- optimal solution in polynomial time? Okay. And then the last uh way we could change things in especially future classes, though sometimes they talk about this in O 4 6 as well, is we could change the model of computation. Right? We could basically change something about our computer to be put in some other weird paradigm of of of solving problems with more power essentially.

Or or you're in a situation where there's less power. Okay. So, changing the model of computation. Okay? So, what we've been talking to you in terms of model of computations is our word RAM, right? Word RAM. That essentially says I can do arithmetic operations and I can look up stuff in my memory in constant time. And but if I allocate a certain amount, I have to pay that amount and that kind of thing. So, that's this word RAM model. But in actuality, all of your computers, you know, it's a it's a lot easier for me to figure uh to find and read memory that's on my CPU in a register than it is for me to go out to the hard disk, ask this well, in my day used to be this this movable mechanical head that had to go and scan over a bit on a on a CD-ROM drive and, you know, actually read what that thing was.

Right? So, we can add complexity to our model to better uh account for the costs of operations on my machine. One of those models is called the cache model. Uh cache model is basically a hierarchy of memory, right? I have, you know, my registers on board my CPU. I have maybe an L1 cache that's close to my uh CPU. Then I have another set of caches and another set of caches maybe out to RAM. And reading from a hard disk is a solid-state drive of some kind, that's the slowest thing to access. And I can put a cost associated with each of those things. And instead of having to having all of our operations be you know, say said to be constant, the constants are actually different and I have to pay for that difference.

Okay? And so that's, you know, extending our model to be a little bit more realistic to our machine. You know, another one is, you know, we have computers right now that operate in operate in classical physics. Right? That exploit things in classical physics. But in actuality, our world allows for even more complicated types of operations like quantum operations where you're exploiting entanglement and superposition of different atoms to potentially get operations that I can act on my data that are actually provably stronger than the classical models in some sense. Right? So this is a whole a huge reason why uh there's a lot of work being done in say, you know, lots of uh uh industry research facilities in figuring out these models because maybe if you can make a big enough quantum computer, you can break encryption and stuff in polynomial time.

And that's something that maybe the NSA is interested in and you know, I'm not going to go into that. But you know, I mean, some people like you look at artificial intelligence and things like discussions around artificial intelligence, my brain, you know, might be doing things that a classical computer cannot. Right? It could be using quantum superposition in some way. And our computers that are in your phone and your laptop and things like that aren't exploiting those operations. So how could we ever get intelligence? Because, you know, in some sense our brains are more powerful. Right? And so a lot of what AI should be looking into is what is the actual model of computation of our brains that can give us the power to have sentience.

Right? Okay. So that's that's kind of quantum computing. I don't know much about it actually. Uh and then there's things like maybe I have more than one CPU. Right? I I I mean, most computer all the computers you have, even the ones in your phone, probably have multiple cores. Right? In a sense, you have lots of CPUs running in parallel. Right? So this is like pair uh there's one R in parallel? Okay? Parallel computing basically says, you know, it's cheap for me to make another computer potentially. Right? If I have two computers running on the same problem, maybe I can get a twofold speedup on my on the the the time in which it takes to solve my problem.

Now that's not I I mean, suppose I had then 100 CPUs running on a machine. Maybe I can get a 100-fold speedup. And and actually in in real life, 100-fold speedup makes a difference. Right? It's am I waiting for this for 10 minutes or am I waiting for this for 1,000 minutes? Right? That's that's like all day. I don't want to do that. That's a maybe it's on weeks. I don't even remember. Right? Okay. But parallel computing, right? If I can get a 100-fold speedup, that might be a huge win. But for some problems, it's not possible to you know, if I have K CPUs, can I get a K factor speedup? It's not always possible to do.

Okay? And so parallel computing is another paradigm in which uh there's a lot of interesting theory going on. Uh there's a lot of complications there because, you know, there are a couple different models. You can have a multi-core setup where you have a lot of computers that are accessing the same bank of memory. And then you don't want them all to be reading and writing from them at at different times because you don't necessarily know what their state is and you get these collisions which are something that you really have to think about in this world. Or you have situations where maybe I have a bunch of nano flies or something that are going around and they have very small computer brains themselves.

Right? But they can talk to each other and pass information to each other, but they don't have access to one central network repository of information. That's what we call a distributed parallel system where all of the, you know, CPUs that you have can interact with each other maybe locally, but don't have access to the same uh memory system. Uh so they have to work together to gain to to learn information about the system. Okay. So this is that's a a brief overview of the different directions this class, 6.006, and theory in general could lead you into a in a huge array of different uh branches of theory and different problems that you could address with different types of computers.

Okay? So uh I know this is a very high-level lecture and uh and maybe less applied than than some of you might like. But I hope this gives you a good understanding of kind of the way the directions you can go after this class uh that I think are really excited in in terms of uh how to solve problems computationally. Okay? So uh with that, uh I'd like to end there.