Transcript

Hi everybody. Welcome to the last lecture of 6006. Last lecture we talked about uh summing up this class and talking about future courses in the department that use this material. Um just as a pointer to some of those classes. I have a little slide here I didn't get to at the last lecture talking about kind of what I was talking about the end of last lecture about different models different specialized classes on different aspects of uh 006 material. For example, more graph stuff um different models of computation, randomness uh complexity. All of these things have their own specialized classes in the department as well as a lot of applications uh for this material in subjects like biology, cryptography and in particular for your instructors uh the the realm of graphics and geometry.

Okay? So all of all of your instructors this term happen to be geometers and have be interested in geometry related problems. Um Me in particular, I didn't start out in computer science. I started out in mechanical engineering uh and the thing that was my passion coming into MIT was origami. And so here's a couple of pieces that I designed um origami pieces. One square sheet of paper without cutting. Here's a a lobster. Uh and here's a you know, a copyrighted dinosaur from a particular movie of the year that I designed it. Um I when I was young in high school, I started designing my own origami models.

And what I didn't realize was the procedures that I went about designing these models was actually algorithms, right? I just didn't have the mathematical language to to understand exactly what I was doing, but I could gain some intuition as an origami artist and design these things by using some of those algorithmic techniques. It wasn't until grad school as a mechanical engineer that I uh uh started talking with uh our other instructor here, Professor Demaine, about uh using algorithms in computer science to design not just origami uh which we both do but also uh folded structures that can be used for mechanical applications like space flight um uh deployable bridges in in like um in times when you you can't uh you need a temporary uh bridge or shelter or something like that, deployable structures where uh you might need to make folded structures, transformable structures that can have different applications uh uh for different purposes, need to reconfigure.

The dream being that we have these powerful devices in our pockets right now, cell phones uh which uh you know, are really powerful because we can reconfigure the bits in them to make software of all different kinds, right? There's a there's a exponential number of different programs that we can write and that's part of why you're here is to write the next best one, right? So, that's how to how to make uh kind of a universal a device uh at the electronic level. What if we could do that in a material from a material standpoint. What if I could reprogram the matter in my phone so that not only uh could I reprogram the app that's on your phone, but instead of having the say the iPhone 10 or whatever that you have and and you want to go buy the iPhone 11 instead, you you download a a software app that then reconfigures the matter in your phone.

It folds or reconfigures into the next generation iPhone. You you don't have to throw away that old one. You can essentially recycle the material that you have to potentially save material, save cost, and be better for the environment potentially. So, uh I started moving into computer science because I found that it was a really good way to model the world and solve some really interesting problems about folding that I I really enjoyed. So, um the the three of us today are going to spend some time talking a little bit about how we can use algorithms, 6.006 material and beyond in our own research, and we're going to start off with Professor Demaine and then Professor Solomon.

Sweet. Uh so, why don't I just jump into uh computational origami and uh geometric folding algorithms is sort of a broader umbrella for folding related things, which is encapsulated by this uh class 6.849, which is happening next fall, so you should all take it. Uh 006 should be a reasonable background. Um and in general, we're interested in two kinds of problems. One, the big one is origami design or in general folding design, where you have some specifications of what you'd like to build. In this case, I wanted to make a logo for 6849, and I imagined extruding that text into third third dimension and then I wanted an algorithm to figure tell me how to fold that structure.

And so there is an algorithm which I'll talk about in a moment that gives you a crease pattern and then currently you fold it by hand. The dream is we'll eventually have folding machines that do it all for us. Um and so that's the origami design where you go from the the target shape back to the to the crease pattern. The reverse direction is sort of foldability. If I gave you a structure like this and I wanted to know does it fold? Uh that's a problem we call uh foldability in general a class of problems and sadly most of those problems are NP-hard. Jason and I proved uh that foldability is hard for general given a crease pattern like that telling you whether it folds into anything it turns out to be NP-hard.

So that's bad news. Um so we focus a lot on the design problem because that actually tends to be easier. We can solve it with algorithms like that one you're seeing. Um and so a long time ago we proved that you can fold everything. Uh if I give you a square piece of paper and you take uh any polygon you want to make or maybe the paper's white on one side black on the other you you want to fold some two-color pattern like a zebra or in general some three-dimensional surface like these guys uh there is a way to fold it from a large enough square paper. Um and it's actually really easy to prove that with an algorithm.

I have a the sketch of the two pages of proof that we go over in 6849 but I'll just hand wave a little bit. Uh if you take a piece of paper like my lecture notes here uh the first thing you do is fold it down into a very long narrow strip much longer and narrower than this one wasting most of the material and then you take your strip and you just figure out how to turn it in some general way and then you just sort of zigzag back and forth along the the So it's very cool in that you can prove with an algorithm and a very short amount of time to someone you can actually fold everything. Of course, it's a terrible folding cuz in the very first step we throw away all but epsilon of the material.

Uh but it's a starting point. And then that was back in the '90s, late '90s, uh one of the first results in computational origami. Uh and in modern times we look for better algorithms that are more efficient that try to minimize the scale factor from how big of a piece of paper do I start from to how big of a model do I get. Um and one of the cool ways these days which was invented by Tomohiro Tachi and then analyzed by the two of us uh is called Organa miser. It's free software. You take a 3D model and you can uh it makes it into a crease pattern that you fold from a square. In this case, it uses 22% of the area, which is pretty good.

Um similar to these guys in terms of uh efficiency, but very very different kind of folding uh than what you would get uh from more traditional origami design, which uses different algorithms, which I'm not going to talk about, but you should take the class. Jason gives a lecture in the class that you can learn from him. Um But the the you know, the vision is we can take any sheet of material that can hold a crease uh like this sheet of steel that Tomohiro is folding uh is cut by a big laser cutter at MIT. Um and this is him in the state of the center several years ago folding it uh into a steel bunny.

And so, this is like a totally new way to manufacture 3D objects and uh you can make particularly interesting objects that either collapse flat for uh transportation uh or transform like Jason was talking about. But I'm just giving you a flavor. Uh the I think the first paper we wrote together was on maze folding. Uh so, this is an example of folding a maze from a rectangle of paper. And you can all try this out. Uh you just Google for our maze folder. Uh you can generate a random maze, and this 3D structure can be folded from this crease pattern. Uh that's a really hard one, so try maybe try something smaller.

Um you can also write your favorite message um and fold this maze extruded graph uh from this crease pattern. Uh might want to start with something smaller, but that's the general idea. Um and it's actually quite easy to prove this algorithmically if you have a really good origami split Jason on your team. Um what you do is design how to fold each type of vertex. This is just a graph on a grid. So, there you know, some constant number of different ways that each vertex could look. It could be degree four, it could be degree three. Uh and as a T, it could be degree two either as a turn or a straight.

And you design little gadgets, little crease patterns that fold into each of those little structures. And if you can do it in a way that these boundaries are compatible, then to fold the whole thing, you just sort of glue together those crease patterns, and that's how that software works. Um and so that was This is particularly interesting because you can fold an arbitrarily complicated graph uh arbitrarily complicated maze n by n with a constant scale factor. As long as the height that you're extruding that maze is constant, uh then this is one family of shapes we know how to fold really well.

In general, we're trying to understand, you know, what makes uh this lobster a nice shape in that it can be represented with a not too large piece of paper. We don't have general answers to that that problem. Uh I think that was a whirlwind tour of computational origami. Um I also play a lot in the uh in algorithmic sculpture. One of the leading edges in in origami and origami math is understanding how curved creases work. Um and one of our favorite models is this one uh where you fold concentric circles alternating mountain and valley, cut a circular hole out, and it folds into this kind of Pringle shape as a nice physics equilibrium thing.

And then you can turn it into fun sculptures like this. These are done with my dad, Martin Demaine, who's also here at MIT. Or this guy. This paper has been printed with a pattern according to getting burned by glass, and then it gets folded and then put inside glass also. Made here at MIT. And so we use sculpture to try to explore and understand intuitively how curved creases work, and then we get better and better understanding of the mathematics of even we don't even know whether this surface exists, whether it's possible to fold in this way, although getting close to proving it. So, that was sort of in the top level of this hierarchy.

Computational geometry is a bigger umbrella which is represented by another class 6850 that's being taught this term. And then I talked about geometric folding within that branch. Let me briefly tell you about another world of geometry very different in terms of model of computation. Oh, I'm jumped ahead a little bit. Rewind. Let me show you one more fun demo which if I find my scissors. So, if I take a rectangle of paper and I fold it flat and make one straight cut what shapes can I get? This is called the folding cut problem. Hundreds of years old. Uh Here for example I get a swan. Uh here I get one straight cut I unfold and get angel fish.

Tough audience today. I keep going. Seeing all these before. This is This one is um a particularly difficult one to fold. Only fold and to cut, yeah. Okay. Hopefully that works well. This is the MIT logo. Ooh, ah. Yeah. Go MIT. All right. So, um that's That's actually the first problem I worked on in computational origami. It's a lot of fun. And there's a really interesting algorithm here also for computing the crease pattern and how to fold your piece of paper to align, in fact, any graph you draw on a piece of paper, you can align all those edges and nothing else. So, you cut along the line and you get exactly what you want.

Cool. All right. Uh now I want to talk about something completely different, which is self-assembly. Uh a fun thing you can do with DNA, which we all have, um just pick out some cool DNA strands and design them in a clever way so they fit together to form a kind of square with dangling ends, which I'll call glues. And each of those dangling ends can have a very particular pattern, and only identical or complementary patterns will attach to each other. Um and so you can use this to design your own self-assembling system, like biology does, but engineered, uh for example, to build a computer. This is an example of taking a bunch of these square tiles um and building a binary counter.

This thing is roughly counting in binary along the diagonal. It's a little skewed, so it's hard to see, but the general model is you have um squares. This is sort of the computational model with four different glues, and you can build any square you want, but you don't have very many of these different glues, ideally. And then, uh if you have two tiles with complementary uh glues, they'll want to match together. But, it depends how strong this glue is, how much affinity there is for how long those DNA dangling ends are, um and also the temperature of your system. If you have really high temperature, nothing will stick together.

Low temperature, things will stick together even if they're not supposed to. Um and so, you can if you tune your system really well, you can design uh a system so that maybe these guy these glues are really strong. And so, let's I don't know, write E here, Eric. Um and so, these tiles will always glue together. But, only when all three of these have are glued together can this tile, which has C complement and F complement, then it will if you've set the temperatures just right, only because both of these edges match, will this tile be able to come in. And that's the basis for that building that binary counter.

And so, this is a very different model of computation from what we're used to in this class, where you think of instructions and they run one at a time. Here, the model of computation is geometric. It's these squares that are just floating around and gluing together. And so, your program at any moment is some conglomerate of squares. And so, I just wanted to mention it cuz it's a really fun model. You can prove cool things in this model like uh how to build any shape by a sequence of pours, mixings between tiles, uh that you can execute in parallel. And so, it only takes log n time in of parallel steps, a linear number of different mix operations to make an arbitrary shape, even using a constant number of different glues.

Uh which is cool and maybe practical. Um you can also use it to build a replicator, where you're given an object like this uh that you don't know the shape of like we don't know whether this exists we can't map model it mathematically very well and you would stick it in a vat and all these tiles would attach and basically build a mold and then start photocopying in 3D that mold. And you can build that with a system with only two steps I believe and a constant number of tile types and it does all of that in this model in constant time. In reality you'd have to feed this machine and and wait for it to print out all these things and and these experiments take hours if not days to run but in theory it's really cool and you get some really fun models and very general results.

You can also use it to build a miniaturizer or a magnifier and other other fun stuff. Okay. Um So that was brief tour of computational geometry. I work mostly in four different areas of algorithms geometry data structures graph algorithms and what I call recreational algorithms. I think I made up that term. Um and let's go into data structures which is represented by this class 6851. Um all of the classes I mentioned have online video lectures so especially for those watching at home on open courseware uh most of these classes are on open courseware and if not uh they're on my webpage. Um so 6851 advanced data structures is an extension of the sorts of data structures you've seen in here in 006 and the ones you will see in 6046.

Um I thought I'd give you a flavor of one such result which is a problem we've seen in this class done better. Uh so suppose you want to store a dynamic ordered set. So this is the set interface dynamic in the sense that I have insert and delete and ordered in the sense that I want to support find next and find previous. Okay, so exactly which subset of the set interface you choose influences what what data structure you've seen. We've seen for dynamic sets you want to use hashing. If you don't care about find next, if you just care about find, then hashing is great constant expected. You can prove stronger things about hashing we do in that class.

Um, but if you want dynamic and ordered uh, you cannot do constant time per operation. You can prove that. Uh, which is cool. But and so what data structure have we seen that solves this problem pretty well? Set AVL trees which solve everything in log n. So log n is one competitor. Uh, Yeah. Uh, I I'm interested in this in the word RAM model. Which is the only model we see in this class. This happens to work in a stronger model. Um, and uh, we can do better than log n in the following It'll take me a while before I get better, but here's at least a different bound we can get. Log W. Uh, this is via a structure called van Emde Boas.

Who's a person. AVL is two people. Van Emde Boas I've actually met. Um, so log W, remember W is our word size. So this is a bit of a weird running time. It's great if W is like log n, then this is log log n. And we know W is at least log n, but it could be bigger. Uh, we don't really have a sense of how big W could get. Maybe it's even n. Maybe it's big and then these are the same. Maybe it's bigger than n and then this is maybe worse. But for most W's this is actually pretty good and indeed optimal. Um but it's not strictly better in any sense yet. On the other hand, there's another data structure which runs in log n divided by log W.

This is called fusion trees. This was invented around the time that ColdFusion was in the news and so they wanted to data structures to represent. And so we can achieve this bound or we can achieve this bound and this bound is good is if W is large, this bound is good if W is small. And so you can always take the min of the two, whatever's better. Um and in particular the min uh the min of those two things is at most I think it's square root log n over log log n. If you want a bound just in terms of n uh then the crossover point between these two is this place and so you're always at most this which is quite a bit better than the log n of AVL.

We've got a square root and we've got a slight uh thing in the denominator, pretty tiny. Uh but the big thing is the square root and that's kind of cool and it turns out that's pretty much optimal. In terms of an n bound this is optimal. The min of these two in general is roughly optimal up to like log log terms. I for fun I threw up the actual formula for the right bound uh it which is tight up to constant factors. There's matching upper and lower bounds which we talk about. It's min of three things four things uh including log of W over A divided by log of log W over A over log of log n over A.

That's the last term that I just read. It's messy. Surprisingly, that is the right answer for this very particular problem, very natural problem. A is the log of the space you're using. So, it's the address size. Good question. If you throw So, it depends If you have a polynomial space data structure, then basically these are optimal. And this is generalizing to beyond that. Maybe you have a little bit more than polynomial space. Cool. So, that's data structures. I'm going to jump ahead to graph algorithms, which if you want to take this class, I recommend a time travel device. Go back to fall 2011.

It may never get taught again, but it has videos, so you can watch instead of time traveling. If you don't want to watch it live, you can just watch the recorded version. It was taught by a bunch of postdocs that were here and and a bit myself. And so, what I like to do with graphs is the world of planar graphs or near planar graphs. So, we've talked a lot about this class of algorithms that work for arbitrary graphs. And the algorithms we've seen in this class are pretty much the best we know for a lot of problems for for arbitrary graphs. But if your graph has some structure like it's a road network and there aren't too many overpasses, you can usually draw these graphs in the plane without crossings.

That's the meaning of planar. Maybe not exactly, maybe just a few crossings. There's a generalization of this which I won't go into. But let's just think about planar graphs. Planar graphs have some nice features like they always have a linear number of edges. They're always sparse. So, you can immediately plug that into our existing bounds. But even so, you know, Dijkstra would take in this such a graph would take V log V time. For planar graphs, you can do the the equivalent of Dijkstra, meaning I can compute single source shortest paths with non-negative edge weights in linear time. Uh no log.

Okay? Not that impressive, but we remove a log. More impressive is we can do the equivalent of Bellman-Ford, uh which is single source shortest paths with arbitrary edge weights in a planar graph in uh some time. Almost linear time. V uh log squared V over log log V. Okay, so there's a couple log factors here, but for the almost linear time, whereas Bellman-Ford would take V squared time. So, this is a huge improvement over what we've seen in the class. These are quite complicated algorithms, but they're covered in that class if you're interested in them. Um then the the area I work in a lot is approximation algorithms for planar graphs.

Uh and let me just give you a fun flavor using something we know, which is uh breadth-first search. So, breadth-first search you can think of as building these sort of rings around a single root node. Um and there's this general approach as introduced by Baker in 1994, we've used for lots of different problems. Uh you want to solve some NP-hard problem on on a graph. So, just run breadth-first search from an arbitrary vertex, decompose your graph into these layers. You could number them, you know, zero, one, two, three, these are the levels. Um and let's just like delete some of those layers. Let's say, let's delete every fourth layer.

So, maybe I delete this one. I delete all the vertices in that layer, and then I delete all the things in layer eight, and layer 12, and so on. Um guessing I don't know which one to start with, but from I'll just try them all and then I delete every fourth layer after that. So, I've deleted on average about a quarter of the graph. Um and it turns out for a lot of problems that you care about, um like choosing where to place fire stations in this graph to minimize, uh you know, travel time for there's a fire somewhere in the graph. It happens, you know, fires in graphs. Then, uh this will only hurt your solution by like a factor of uh 1 plus a quarter.

Uh so, you'll get a solution that's uh within 25% of the optimal for a lot of problems. Um and uh that works for any value of four. So, I could do it for 10 and then I'd get within 10% of the optimal solution. Uh okay, but how do I actually solve the problem once I delete every fourth layer? Well, then your graph has this extra special structure, which is a constant number of layers, let's say, a constant number of breadth-first search layers. If you just look at this portion, this connected component, or this connected component in here, you can your graph is almost like a cycle. It's like four cycles kind of stacked up together with some connections between them and it turns out that's something you can solve with very fancy dynamic programming, um like the stuff we've seen bef- in this class, which focuses on just a single path or a single cycle.

If you just have a constant number of cycles, with more work, you can still do everything in polynomial time. And so, this is a very general approach for getting uh arbitrarily good approximation algorithms. We call these 1 plus epsilon approximation for any epsilon. But the larger the epsilon, the more time you take. It's something like uh two to the order one over epsilon times polynomial in n. So, as long as epsilon's constant, this is polynomial time. It's called a PTAS. Anyway, uh those graph algorithms last topic is recreational algorithms which is maybe best encompassed by this class 6892 is its latest name it changes names every once in a while and I mentioned it in the hardness complexity lecture because this class is all about hardness proofs analyzing fun games and puzzles.

We saw the Tetris NP hardness in that lecture but you can also prove Super Mario Brothers is hard or portal is hard or Mario Kart is hard or the witness and modern video game is hard or one of our latest results is that recurse that game in the top right is undecidable. There's no algorithm to play that game perfectly. So and you can even download the level and an example of the level and play it if you if you dare. So that's a lot of we have a lot of fun in that world hardness of different games and puzzles. Where do I want to go next? Okay, next topic is balloon twisting totally different. This is recreational but not about hardness.

So this is an octahedron twisted from one balloon. I made another one on a stick and so each of these is made for one balloon. What graphs can you make from one balloon? Well, you should read our paper and you can characterize how many balloons do you need to make each each polyhedron and some of these problems are NP hard and it's a lot of fun. Um Cool. I think that's the end of the slides. The last thing I wanted to show you is um a problem a puzzle / magic trick comes from the puzzle world called a picture hanging problem. So imagine you have a picture you want to hang it on a wall so you invested in some nice rope and you hang it Uh and then if the on a nail, if the nail falls out, the picture falls and you're sad.

So, you invest in two nails, uh like I have here, and maybe you hang your picture on both those nails. Now, if one of the nails falls out, you still have a crookedly hang hung picture. The other nail falls out, okay, it's gone. Um I want to hang a picture on two nails such that if I remove either nail, the picture falls. So, Jason, pick a nail, left or right? Left. Left we remove. Make sure this doesn't fall off, and boom, the picture falls. Same wrapping, you can check you can rewind the video, make sure I did the same wrapping. I'll take out the right one. Okay, take out the right one, good choice.

Uh then also the picture falls. Uh and so, this is a classic puzzle, but you can generalize it, so let me do it to for three nails, which is all I have here. This nail's sagging a little bit. Y X or Y inverse X inverse, okay, I think that's right. Uh so, this is one way to hang a picture on three nails such that if I remove any of the nails, picture falls. Uh just just Justin, uh one, two, or three? Uh two. Two. Okay. Yeah, I want to get out of the way. Make sure Make sure I don't go over the edge here. Uh Yeah. It's a lot easier to make this one work, but you can see boom, picture falls there, and of course, imagine infinite gravity, and the picture falls.

Ta-da. Um and so, you can generalize this to do essentially any it's called a monotone Boolean function on any set of nails. I mean, you can make any subset of the nails cause the picture to fall, and any collection of subsets of nails to make it fall. Of course, if you remove more nails, it's still going to fall. That's the monotone sense, but uh otherwise, you can do an arbitrary pattern, uh which is fun. That's actually a result with Ron Rivest and a bunch of other other people. Um I think I'm approximately on time. So, that was a quick tour uh and there are obviously various classes here you can take.

Um 6.892, the hardness class, was just offered last semester, so probably won't be for a while. But, all these classes are online. Watch the videos. Feel free to ask me questions. And now we have Justin. I left you space here for your outline. You don't have to. But, I'll put your name up. Thank you. So, just Justin is also geometer. Yeah, we got a lot of geometry people in the 6.006 this semester. Thank you. Okay. You know, it's like I can't help but share that on our instructor chat, Eric was texting that he was going to be he was somehow nervous that the applied guy would have all the like the cool stuff to show off, and now I feel totally boring.

Uh Right. Yeah, so yeah, we have three different geometry instructors uh and and in this class, I don't think we have many different flavors of geometry that are kind of represented in this this room here from mechanical engineering to theory plus lots of other cool stuff to whatever it is that I do. Um right, so I'm a professor also still in and lead a group that studies slightly more applied geometry problems in some sense. Uh here in CSAIL, we kind of cross a lot of boundaries. Actually, closer to the math department than to the theory group in computer science, which I would argue is largely a historical artifact rather than anything interesting about computer science or or math.

Um so, continuing in our whirlwind tour of interesting geometry classes here at MIT, Uh, I have uh, some more fun things to to add to the list and and we'll introduce some of the ideas in the next couple slides here. Uh, so uh, normally every fall I teach 6837, uh, which is the introduction to computer graphics course. In fact, my background was, was working in an animation studio for a little bit of time and and uh, got one movie credit out of it until they changed the standards for movie credits and then that stopped happening. Uh, but but in any event, uh, if you watch what's that movie Up with the old man, if you hit pause at just the right moment, you can find me right above the list of babies that were born during uh, production.

Uh, but in any event, um, although computer graphics might not sound like an algorithmic discipline, I'll try to convince you guys that in some sense, you could take just about anybody in our department, have them teach 6006 and give a similar talk that like the material that you've encountered in this course is going to be relevant to your life. Uh, the other course that I teach that might be of interest, uh, and actually is a little more theoretically flavored, uh, that I teach is uh, 6838. So, since Eric so kindly put my board, my name on the board here, I guess I can draw a picture. So, the main object of interest in 6838 is a particular thing called a simplicial complex.

So, um, usually, uh, in 6006 we spend a lot of time thinking about graphs. Uh, so let me draw you a graph. So, I'm going to take a square and subdivide it. And now, let's say I put edges diagonally. Like that. Now, in 6006, the thing is a bunch of nodes connected by edges. In fact, if I took this edge and I like moved it down or something, it would be the same graph. Uh, but of course, in a lot of uh, computer graphics applications, this thing also looks an awful lot like a square. Uh, and and the reason is that of course, uh, the graph here contains triangles inside of it. Uh, and so for instance, um, maybe I think of my graph as a collection of vertices, collection of edges, this is sort of notation we've seen before, and then I add a third thing to my trip uh, to my description, which is a set of triplets.

Uh, that's the set of triangles here. Right? And we can take a lot of the algorithms that we've talked about in this class and extend it to this case. So, for example, um, here's a deceptively annoying one. Uh, let's say that I want the shortest path between two uh, vertices in my graph. Yeah, so we uh, certainly have learned um, Dijkstra's algorithm as one technique to do that. And indeed, common practice in computer graphics, which is shameful, uh, is on your triangle mesh, if you want the shortest path between two vertices, run Dijkstra's uh, algorithm on the edges. Uh, and let's see if that works really quick.

So, let's say that I want the shortest path between And by the way, I'm going to assume the lengths of my edges are like the lengths as I've drawn them on the board here. So, it's like one, one, square root of two. Okay. So, let's say I want the shortest path between the bottom one and the upper right. If I run Dijkstra's algorithm, we're in good shape, right? We could uh, we can I'll let you do the computations at home. You'll get the path that is these two edges. But here's a really annoying thing. Let's say instead, I wanted the shortest path from the upper left to the lower right. If I run Dijkstra's algorithm on this triangulated square, what's going to be the shortest path?

Yeah, in fact, there's a bunch of them. Um, one of them might go all the way down, and then all the way to the right. What's the length of this path? One, two, three, four? Is that the length of the shortest path? Well, probably not. Well, we'd like our shortest path to do something like that, but graphs don't know how to talk to triangles, uh, and this is going to be a problem. In fact, it wasn't until fairly recent history terms that we were able to kind of work out the correct algorithm for The path in a triangulated domain like this. Um, what is the run time that we would expect? This is called uh, MMP, I'm guessing Eric and Jason could do a better job describing it than I can.

Um, but the basic idea of the MMP algorithm actually is a really happens to be a nice extension of the way that we taught uh, Dijkstra's algorithm in 6.06 cuz they really do keep track of these sort of level sets of the distance function. But now the level sets have to like, oops, uh, have to window an edge like that, uh, when I, uh, compute shortest path which is a giant headache. This is one of these algorithms that was known in theory about 10 years before anybody bothered to implement it in a way that they could give us some themselves really ran in n log n time. Uh, and nowadays is a cottage industry in in computer graphics research papers to implement this and then speed it up in different ways and sadly the reality is that a different algorithm we cover in 6.838 called fast marching which doesn't actually give you the shortest path but some approximation thereof, uh, is faster, easier to use and basically indistinguishable.

Um, so in in any event, um, in 6.838 we kind of have an interesting dual mindset where on the one hand we'll talk about a lot of algorithms that look like what we've done in whatever this class is, uh, 6.06. Um, but at the same time start to have a more geometric flavor and we don't worry quite as much about integers. So in our computation model often times we're kind of okay with real numbers cuz that's not where the headache is and of course when you write your code in this class you use double precision floating point. If you're more responsible like in in in Jason's previous lecture you should probably keep track of the number of operations and make sure that your error is bounded but uh, I'm not sure that we we really bother with that.

Um, in any event this allows us to kind of have two different mindsets, right? There's one mindset which is discrete, there's another mindset which is smooth, right? So we think about understanding geometry like these triangulated domains as an approximation of a smooth surface and then we might want to do stuff like compute curvature and so on, which is really associated with computing derivatives, which of course we don't have on these kind of simplicial objects. Uh and that leads to this really fun area of math, computer science, whatever, uh called discrete differential geometry, which sounds like a contradiction in terms, uh and it's something that that that that we we cover in quite some detail in this course.

So, we build up all of calculus if the only calculations you're allowed to do are on the vertices, edges, and triangles of a triangle mesh, uh and get pretty far, including some some some constructions of topology like the de Rham complex and so on. I would argue actually if you take our course and then the differential geometry course at Caltech, somehow some of the indices and headache that you often encounter in that world are much more concrete when you try to make them work on a mesh. In any event, I think I've already spent all of my time. I can tell you a little bit about uh research uh in in our group.

Um so, I lead kind of a weird extremely broad group where some of our students are essentially theory students who don't want to push your keyboard. I'm sorry, it was a reflex. Um but it was fast. Uh all right, so so we have some students uh whose background is in math, other ones that like were in autonomous driving industry and decided to come back and uh uh work in in research. And so, because of that we have this extremely broad set of research problems. Everything from the sort of classic machine learning problems you might encounter in in geometry world, like if I have a self-driving car and I want to identify pedestrians and other cars on the road uh in an efficient and accurate fashion.

Um by the way, part of that is machine learning and deep whatever, but there's another part which is algorithms because actually what comes into your lidar scanner is on the order of like thousands of points in some minuscule fraction of time, and time complexity of your learning algorithm actually is really critical to get right. Uh and something that there are a lot of open problems right now because it's really not compatible with the hardware architecture that that these cards often use. Uh we also look at more abstract geometry problems like if I give you data, can I find a geometric structure?

Uh so it's so classic example of natural language processing where we use words like near and far, you know, in in terms of semantics and meaning all the time. Uh the question is can we actually find an embedding of our, you know, word data into a geometric space to facilitate the kind of statistical algorithms that that we care about? And of course we we apply geometry to lots of practical problems. Everything from meshing in scientific computing, which I think is sort of a classic uh one. In fact, I think we're the first group that sort of enumerated all the cool things that can happen to Actually, if you draw meshes, um which is the sort of bottom figure here.

I should share this with you cuz there's some fun things to look at there. Um to uh other practical problems like taking a, you know, Eric took a zebra and told it that we can take a zebra and and move its texture onto a cat or a pig. Or actually off the side of the screen, but if you download the paper, there's an also a 3D scan of one of my grandchildren. Um so in any event, in uh my 5 minutes remaining here, I thought I'd I'd dig into a little bit of uh detail of two or maybe one application depending on when Jason and Eric get bored. Uh uh and essentially my message for you guys is of course, you know, it's a good thing cuz I'm I'm not really a central CS theory group member here at MIT.

Uh but unfortunately for you guys, 6.06 is unavoidable. Even if you want to go into deep learning, statistics, whatever, data science, you're going to encounter the material that you've seen in this course. And in fact, it's really the bread and butter of just about everything everybody does here in the Stata center. So I thought I'd give you two quick examples, one of which lifted from my teaching, one from my research. So uh if you continue with me next fall, uh we'll teach uh 6.837, which is the intro to computer graphics course. One thing that's always amazing to students is these algorithms that produce these beautiful images can fit in about 10-20 lines of code.

Um so a really this is totally facetious cuz if you want those beautiful images and you use those 20 lines of code, you'll be waiting until the universe to actually compute these things. But in any event, one nice one for rendering, so drawing a bunch of shapes on your screen, something called ray casting um or it's better known cousin ray tracing. Typically the difference is whether your rays can bounce off of the surface and have a secondary effect. All right, so here's the ray casting algorithm. Let's say I have a scene built out of spheres and cubes. I got a for loop over every pixel on the computer screen.

For every pixel I got to discover what color that should be. So I shoot a ray from my eyeball through that pixel and find the first object that runs into. It's not so hard to intersect a line and a sphere or a line and a cube. So what is that algorithm? Well, I've given it to you on the screen here. Not too bad to think about. And I think you guys are all extremely well equipped to analyze the run time of this which is roughly the number of pixels times the number of objects, right? Cuz for every pixel I got to decide what object the ray out of my eyeball hits first. So I need a for loop over every object.

Makes sense? Cool. So let's look at sort of a basic rendering problem. In fact, Eric already secretly snuck this one in here. So there's a very famous 3D model called the Stanford Bunny. Um Stanford Bunny is actually a great example of a simplicial complex in fact a manifold one triangulated surface. Um actually I'm not sure it's manifold in the original form. But but usually it is. Uh and this innocent looking extremely famous 3D model is actually quite pernicious. It's it's composed of 69,000 triangles and if I wanted 1080p like you know a high def rendering of my triangle, then of course there's there's 2 million pixels on the screen.

So, if we look at our big O expression, roughly our computation time scales like the product of those two big numbers. So, just to render this ugly gray bunny takes me a pretty large amount of time. Yeah? And in fact, the real By the way, the bunny is like this famous test case in computer graphics. So, if you take my class, you'll be rendering bunnies all day. Um you know, the reality is we don't want just like gray flat shaded bunnies. We want bunnies that are transparent and reflecting stuff and you know, I shoot my bunny with a bullet and it shatters into a million pieces and and all these cool things.

So, of course that ray casting algorithm with each one of these new graphics features I add only adds the time complexity of of of of the technique that I implement. So, pretty quickly and indeed if you write your own ray tracer at home, which I strongly encourage you to do, what you'll discover is that it's hell slow would be the technical phrase. So, what is our way out of this? Well, if you take 837, you'll see that our way out of these problems in graphics is data structures and algorithms. It's completely unavoidable. So, for instance, obviously we spend a quite a bit of time in this course talking about AVL trees.

In 837, we'll spend a big chunk of our course talking about space partitioning trees. So, here I actually forgot what kind of tree this is. I think it's a KD tree. Doesn't matter. In any event, one thing I could do is take all the triangles in my bunny and I could put the entire bunny in a giant cube. Right? And with the property that the cube is outside the bunny. Let's say I cast a ray and the ray doesn't touch the cube. Can the ray touch the bunny? No, right? Things might pass it. Right? So, suddenly I just saved myself a lot of computation time, right? I don't have to iterate over all the triangles inside of the bunny to see whether they hit the ray or not because I already convinced myself by this conservative test that I didn't hit even the bounding box of the whole bunny.

Yeah? Well, that's sort of a nice order one speed up, but depending on how big the bunny is relative to the size of my ray or image, that might not be a super useful efficiency test, but of course what could I do? I could take the box containing the bunny, I could slice it in half, and I would say does my, you know, does my ray hit the front or the back of the bunny? Or maybe both. That's where you got to That's where things get enough. Um and and so on. So now you have this nice recursive tree structure where I taking the box containing my bunny and chopping it in half and placing in some sense usually the triangles maybe not the leaves of my tree, but abstractly that's probably good enough.

You get a structure like what you see on the screen here. And why should you do that? Well, remember it takes sort of PN time to render my image of my bunny normally. Well, now the picture is actually misleadingly suggestive, but you might think that maybe it takes roughly, remember N is the the number of objects in my scene, P log N time to render my bunny now because I can kind of traverse this tree of objects in my scene. Of course, notice I put a question mark here. The devil's in the details here. In fact, I think computer graphics people often believe that the rendering algorithm takes P log N time.

That's often not possible, although kind of there's an interesting question which is that the heuristics they use for building these sorts of trees often do on average give them log N time. And so there's something about the data that's making this problem easier than it might seem. Um so we'll dig into that a little bit in the graphics class. Of course, we're not going to prove as many bounds as we might in a theory course, um but we're certainly building on the intuition that you've seen in this class to build out the practical data structures. And these data structures appear everywhere in computer graphics.

So for instance, directed acyclic directed acyclic graphs appear all over the place in computer graphics literature to describe 3D scenes. So for example, this classroom is a stark reminder of why we need DAGs in computer graphics, because we have all of these entities here, and they're all copies of one another. So, would it make sense for me to store however many like hundred 3D models of the same chair? Probably not. Right? So, instead, what do I do? I have I store one instance of a chair, and then some instructions on how to tile it into my entire scene. So, one way that I can do that is to think of it being a node, which in a graph which knows how to draw one chair.

And now, I can have a bunch of different nodes in my scene for all the instances of the chair that store like a different transformation for each one. So, what if you think about the graph structure here, each of those instances going to point into the same 3D model of the chair for rendering, and that makes a directed acyclic graph uh structure um called a scene graph, which we'll spend quite a bit of time talking about in 827, how to traverse, construct, all that good stuff. Um and there are lots of different models of computation uh in that universe as well. Um your your graphics card is a uh very specific kind of parallel processor that's kind of like Lucille Ball on the uh conveyor belt, you know, hammering at the same object over and over again.

But, if you ask it to do anything other than the one thing it knows how to do to a bunch of data at a time, uh then all of your computation grinds to a halt. This is called single instruction multiple data parallelism, SIMD. Uh numerical algorithms matter a lot for things like fluid simulation, um and approximate approximation algorithms are are quite critical, too. Um in computer graphics, the the complexity is kind of interesting, because of course, your eyeball is sensitive to about 29.97 frames per second worth of material. Um you can choose that time to do like really well rendering one object, but then you take out of the time rendering something else.

Uh so, there's kind of an interesting conservation law that you have to balance when you solve these kinds of problems, which is an interesting balance now between like complexity and runtime of your algorithm and perception. Like what things can you get away with when you draw a scene? And maybe like I can do tons of extra computation to get that extra shadow, but it's just not worth it. Uh so I'll quickly sketch out another completely different application of the material that that we've covered in 6006 for my own research. Again, just like Eric, I guess in a funny way, both of our papers I think are kind of broad in terms of the subject material.

Like rather than some of our colleagues have like really laser focus on one topic or another. Um another research area that I I sort of backed into is the area of political redistricting. This is relevant in the United States. Recently I was reading some grant proposals about other countries, which is really interesting how they they do this stuff. So in the US when we vote for people in Congress, by the way, not necessarily for president, this is a common misconception, but certainly for for for Congress, your state gets divided into little regions, each of which elects one member of the house.

And this there's sort of a subtle problem if you're not used to thinking about it or one that's like staring you in the face and screaming depending on on how often you read the the news and politics, which is an issue called gerrymandering, where your legislature draws the lines for what area on the map elects a member of Congress. And depending on how you draw the lines, you can engineer different results for who's likely to get elected. So for instance, maybe there's some minority I can cluster them all together into one voting district, then they'll only get the opportunity to elect one person, but maybe if I divide the space where they live into two, I could manage to engineer two districts with a high probability of of electing somebody with their political interests in mind.

So it turns out that political redistricting in a broad sense is a great problem computationally. Even if you're a totally heartless theorist, there's some really fun problems here. Um so for example, the state of Iowa, we all pick on Iowa because um it has a unique law, which is that your districts have to be built out of counties, which are much larger than the typical census unit, so it computationally is easier. But even in Iowa, um which is a giant grid with the exception of one shift in the middle which just fascinated me. Um I know I'm a little on time. This is a fun fact, like literally people were making the map of Iowa and they worked from the bottom up and the top down and and it meets in the middle and their grids were shifted and now we're stuck with that.

And it has an interesting effect on the topology of the graph cuz it looks like squares, but then there's triangles in the middle. Uh but in any event, um even though there's only 99 counties and four districts, there's approximately quintillions of possible ways you can divide that state into four contiguous districts that satisfy the rules as they were at least if you read them quite literally and the uh the the the law. Um so it seems like computers are useful, but unfortunately, it's a little subtle how, right? So for instance, there's no single best districting plan out there. Um I can't think of a single state with a law that gives you an objective function, you know, similar to you know, whatever cute, you know, characters that we've had in 6.006, you know, they often have very clear objectives in life, but unfortunately, redistricting, uh that's very rarely the case, you know, you have to balance contiguity, population balance, compactness, all these different things.

Uh reality check number two is that even if somebody did give you an objective function, for just about any interesting objective function, it's very obvious that uh generating the best possible districting plan is NP-hard. Um and by the way, it doesn't even matter because the law doesn't say that computers have to draw the best district, right? So even if P equals NP, you really could extract the best possible districting plan using an algorithm, um it doesn't mean you have to use it, at least the way the law is written now. Interestingly, this is not true in certain parts of Mexico where they actually make you compare your districting plan against a computer generated one, which is philosophically really interesting on the practice it doesn't work terribly well.

Um Right. So, uh our research has studied analysis of districting plans and sets instead instead of writing a piece of software that takes in your state draws your districts and then you're done, uh instead we ask statistical questions about I propose a districting plan, what does it look like relative to the space of the uh possibilities. Um So, that of course begs the question of what are the possibilities? Um so, these are like connected graph partitions, meaning you have a graph and now you take the vertices and you cluster them together in a way where they're connected to one another. The one thing that we all agree on, actually philosophically it's questionable why, um is that you should be able to start at any point in your district and walk to any other one without leaving.

Um these days with the internet it's not clear that that's actually the best criterion, but that's a law that I think is never going to get passed in the in the near uh future. So, anyway I think I'm out of time so I don't think I'll walk you guys through the uh the theory here. Um if maybe I'll leave it in the slides. Uh there's a sort of very simple proof that can show that at least the very simplest thing you might think of for analyzing your districting plan, which is to say you propose a plan and now I want your plan to be at least as good under some accents as to randomly drawn one from the space of all possible connected partitions, all possible ways that we could draw the lines.

Well, then it might be useful to have a piece of software that could just randomly draw such a thing. Um so, in other words to draw something where the probability of any one partition is one over the number of partitions. Um this seems innocent. In fact, actually there's a number of papers that claim to do things like this. Um but it turns out uh that it's uh computationally uh difficult uh assuming that you believe that P doesn't equal NP. So, I'll I'll maybe leave some suggestive pictures uh in the the slides that we can if you guys text me or during if we have a you know, professor-student chat, I'm happy to sketch it out to you then.

Um, there's a very nice easy proof that reduces this to Hamiltonian cycle. Um, and shows you that maybe you shouldn't trust these tools as much as they're argued about literally in Supreme Court a couple months ago. By the way, it was it was pretty fun. Like our our expert report was referenced in the descent of the the case last summer. Um, and when you read the discussion, like you can see the judges trying to talk their way around complexity and and um, it's an interesting if somewhat dry read. So, in any event, that's just the starting point for our research which says that of course these sampling problems are really hard.

Now, the question is well, what can you do? Like do you throw the baby out with the bathwater or not? Um, but the the real message here is of course that this course is unavoidable. Even in these extremely applied problems showing up in court cases or on your graphics card, you still complexity and algorithms and data structures are going to come back to play. Um, so with that, I'll invite our other two speakers up here for our final farewell. Suitibly distance ourselves. So, algorithms are everywhere. I hope you enjoyed this class. It's been a lot of fun teaching you and having you as students.

Even though you're not here physically in the room, we still feel your presence and and look forward to seeing you all soon. Thanks for being a part of of this fun thing. I want to thank our two uh, my co- two co-instructors for an awesome time this semester. It's been been a lot of fun teaching it to you guys and Thanks for uh, spending 006 with us this term. Yeah, thank you. And hopefully we'll see you again soon. Bye. Bye.

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

21. Algorithms—Next Steps