# 24. Cache-Oblivious Algorithms: Searching & Sorting

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=C6EWVBNCxsc
**Transcript page:** https://www.withtranscript.ai/video/C6EWVBNCxsc

## Chapters

- 0:00 — Chapter 1 (0:00)
- 6:12 — Chapter 2 (6:12)
- 8:23 — Chapter 3 (8:23)
- 9:36 — Chapter 4 (9:36)
- 13:37 — Chapter 5 (13:37)
- 15:22 — Chapter 6 (15:22)
- 17:46 — Chapter 7 (17:46)
- 20:16 — Chapter 8 (20:16)
- 23:32 — Chapter 9 (23:32)
- 26:56 — Chapter 10 (26:56)
- 28:47 — Chapter 11 (28:47)
- 34:25 — Chapter 12 (34:25)
- 36:27 — Chapter 13 (36:27)
- 39:05 — Chapter 14 (39:05)
- 42:54 — Chapter 15 (42:54)
- 47:44 — Chapter 16 (47:44)
- 49:44 — Chapter 17 (49:44)
- 56:42 — Chapter 18 (56:42)
- 58:42 — Chapter 19 (58:42)
- 1:00:32 — Chapter 20 (60:32)
- 1:08:13 — Chapter 21 (68:13)
- 1:13:30 — Chapter 22 (73:30)
- 1:14:08 — Chapter 23 (74:08)
- 1:15:20 — Chapter 24 (75:20)
- 1:16:58 — Chapter 25 (76:58)

## Transcript

**[0:00]:** the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT opencourseware at

**[0:20]:** ocw.mit.edu all right welcome to the final lecture of 6046 today we continue our theme of cash oblivious algorithms we're going to look at two of the most basic problems in computer science searching and sorting uh a little bit of each and then I'll tell you a little bit about uh what class you might take after this one um so brief recap of the model we introduced two models of computation although one was just a variation of the other the base model uh is an external memory model this is a two-level memory hierarchy CPU and cache we view as one so this instant communication between them which means what you're computing on can involve uh this cache of size M total size of the cach is m words the cach is divided into these blocks of size B each so they're M overb blocks uh and your problem doesn't fit here presumably or the problem's not

**[1:18]:** very interesting so your problem size n is going to require uh storing your information on dis so the input is really provided over here uh dis is basically infinite in size it's also partitioned into blocks and whenever you can't access individual items here you can only access entire blocks so the model is you say I want to read this block and put it here I want to write this block out and put it here that's what you're allowed to do in the external memory model and what we count is how many block memory transfers we do we call those memory transfers so you want to minimize that and usually you don't worry too much about what happens in here although you could also minimize regular running time as we usually do uh the cache oblivious variation is that your the algorithm is not allowed to know the cache parameters it's not allowed to know the

**[2:02]:** block size uh sorry it's also a block size B in the dis so they match uh and you're not allowed to know the cache size M uh because of that you need that all the block reads and writs are done automatically so the model is uh whenever you access an item you view the disc is just written uh row by row sequentially block by block so linearized it looks like this partitioned into blocks and so whenever you touch an item uh the system automatically loads that block if it's not already in Cache it loads it in if it's already in cash it's free um when you load a pay when you load a block in you probably already have something there so you have to decide if the cash is already full you have to decide which one to evict and we had a couple of strategies but the one I defined was the least

**[2:51]:** recently used block so whichever one in the cache has least recently been used by the CPU that's the one that gets written out back to disk where it originally came from uh and that's it that's the model okay and this is a pretty good model of how it's a pretty good model of how real caches work although this last part uh is not how all real caches work it's close um and at the very end I mentioned this theorem that Y lru is good um and that's that if you take the number of block evictions uh the number of block reads equivalently that lru has to do on a cachee of size M then that's going to be at most twice whatever the best possible thing you could do uh is given a cache of size M over two so we're restricting opt we're kind of tying opts hands behind its back a little bit

**[3:47]:** by decreasing M by a factor of two but then we get a factor of two approximation basically so this was the resource augmentation and this is regular approximation algorithms in general this is a world called online algorithms which is a whole field I'm just going to mention it briefly here uh the distinction here is lru or whatever we Implement in a real system has to make a decision based only on the past of what's happened uh the system we're assuming doesn't know the future so if you know in a compiler maybe you could try to predict the future and do something but on a CPU it doesn't know what instructions going to come next 10 steps in the future so uh you just have to make a decision now sort of your best guess and least recently used is a good best guess opt on the other hand uh we're giving a lot of power

**[4:42]:** this is what we call an offline algorithm meaning uh uh it's like the Q in Star Trek next Generation or some other mythical being uh lives outside of the timeline it can see all of time and say uh I think I'll evict this block it's like the waste of use resources but I'll evict this block because I know it's going to be used farthest in the future uh lru is evicting the thing that was used farthest in the past uh there's a difference there and it could be a big difference uh but there turns out they're related in this way so this is what we call an online algorithm meaning uh you have to make decisions as you go the offline algorithm gets to see the future and optimize accordingly both are computable uh but this's only computable if you know the future which uh we don't so uh what I haven't done is prove

**[5:32]:** this theorem it's actually really easy proof uh so let's do it I want to take the timeline uh and divide it into uh what I call them periods phases phases sounds cool

**[6:12]:** so this is going to be an analysis and in an analysis we're allowed to know the future because we're trying to imagine what opt could do relative to lru so we're fixing the algorithm it's obviously not using the future when we analyze it we're assuming we do know the future we know the entire timeline so all the algorithms we covered last time all the ones we covered today you can think of is just making a sequence of accesses uh they're making a sequence of accesses to elements but uh We've if we assume we know what B is that's just a sequence of accesses to blocks okay so uh you can just think of the timeline as a sequence of block IDs and if you access a block that's currently stored in cash it's free otherwise you pay one right so I'm just going to look at the timeline of all these axises and say well

**[6:58]:** uh keep take a a prefix of the axises until uh I get to a m overb distinct blocks block IDs keep going until uh if I went one more I'd have M over B plus one distinct blocks so it's a maximal prefix of M overb distinct blocks cut there and then repeat so start over start counting at zero Go extend until I have M overb Block distinct block axises and if I went one more I'd have M over B+ one and so on so the timeline gets divided who knows it could be totally irregular uh if you access the same blocks many times uh you could get along for a very long time and only access M over B distinct blocks who knows the algorithm definitely doesn't know because it doesn't know M orb but from analysis perspective we can just count these things so each of these has exactly M overb distinct

**[7:53]:** axises okay distinct block IDs so uh I have two claims about such a phase first claim is that lru uh with a cach of size M on one phase is it most

**[8:23]:** what it's

**[8:28]:** easy M over B claim it's at most M over B uh basically because lru is not brain dead I mean if you gave it uh so you're you're well you're accessing these uh blocks and they all been accessed more recently I mean let's look at this phase all the blocks that you touch here have been accessed more recently than whatever came before that's the definition of this timeline this is in order by time so anything you load in here you will keep you preferentially over the things that are not in the phase because everything in the phase has been accessed more recently so uh maybe eventually you load all M overb blocks that are in the phase everything else you touch by definition of a phase are the same blocks so they will remain in Cache and that's all it will cost M overb memory transfers per phase so this is basically ignoring any carryover from phase to

**[9:22]:** facee this is a conservative upper bound but it's an upper bound okay then the other question is what could op

**[9:36]:** do so opt remember we're tying its hands behind its back it only has a cach a size M over two and then we're valuating on our phase I have to claim that I want to claim that opt is well at least half that if I want to get a factor of two

**[10:00]:** so I claim it's at least half m b why uh now we have to think about carryover so you know opted something in this phase and then we're wondering what happens in the very next phase so some of these blocks may be shared with these blocks we don't know I mean there's some set of blocks we know that this very first block was not in this set otherwise the phase would have been longer but maybe some later block happens to repeat some block that's over there we don't really know there could be some carryover so how lucky could opt be at this moment in time at the beginning of the phase we're looking at it could be the entire cache has things that we want has things has blocks that appear in this phase that's the maximum carryover is the entire cash okay the sort of the best case for opt is that the entire

**[10:54]:** cach uh is useful uh meaning it contains uh blocks in the phase that we're interested in the phase we're looking at at the start of the

**[11:15]:** phase that's the best case but because we gave opt only m/2 that means uh at most uh what is it 12 M overb blocks this was cache size this is block number of blocks in the cache uh at most this many blocks will be free won't Conant anything for opt but by definition the phase has M overb distinct blocks so half of them will be free the other half op is going to have to load in okay so it's a kind of trivial analysis it's amazing this proof is so simple uh it's all about setting things up right when if you define phases that are good for lru but they're then they're also bad for opt when it has cash half the size and so opt has to pay at least half what lru is definitely paying here we can forget about carryover here we're bounding the carryover just by making the cash smaller that's

**[12:13]:** it so this is at most twice that and so we get the theorem uh I mean changing the cach size could dramatically change the number of of cach reads that you have to do or or dis reads that you have to do into cach uh but in all of the algorithms we will cover we're giving some Bound in terms of M that bound will always be most some polinomial dependence in M usually it's like a one over m one overare root of M one over log M something like that uh all of those bounds will only be affected by a constant Factor when you change M by a constant Factor so this is good enough for cash oblivious algorithms all right so that's sort of review why this model is reasonable lru is good so now uh we're going to talk about two basic problems searching for stuff in an array sorting an array uh

**[13:12]:** in both of these models we won't be able to do everything cash obliviously today but they are all possible just takes more time than we have but it'll give you more of a flavor of how these things work again the theme is going to be divide and conquer like last class

**[13:37]:** so let's say we have n elements let's say for Simplicity We're In the comparison model so all we can really do with those elements is compare them less than greater than equal and let's say we want to do Search In the comparison model which I'll think of as a predecessor search

**[14:01]:** so given a new element X I want to find what is the previous element uh what's this largest element smaller than x in my set I'm thinking of these n elements as static let's say you can generalize everything I say to have insertions and deletions but let's not worry about that for now uh I just want to store them somehow in order to enable search so any suggestions in external memory model or C model how would you do

**[14:37]:** this this may sound easy but it's not but that's okay yeah I like easy answers simple

**[14:47]:** answers there's two simple answers one is correct one is wrong but I like both because I want to analyze both yeah store them sorted in order good that's that's how we normally solve this problem so let's see how it does okay so um that's why I have a solution to here that's okay binary search in a sorted

**[15:22]:** array store the elements in order and then to do a query binary search on it so remember binary search got an array you start in the middle then let's say the element we're looking for is way over here so then we'll go over this way go there this way there this way okay log n time I mean this is a binary search is in a certain sense a divide and conquer algorithm you only recurse on one side but it's divide and conquer uh so divide and conquer is good surely binary search is good if only it were that simple um so sort of orthogonal to this picture uh maybe I'll just draw it on one side there there's a division into blocks and in a CIA setting we don't know where that falls but the point is uh for the most part every one of these block every one of these axises we do as

**[16:17]:** we go farther and farther to the right will be almost all of them will be in a different block the middle one is going to is very far away from the 3/4 Mark is very far away from the 78 Mark and so on up until the very end if if say we're searching for the Mac so this will hold for all of them at the end uh once we're we're within a problem of size order B then there's only a constant number of blocks that we're touching and so from then on it will everything will be free basically so if you think about it carefully uh I mean the the obvious upper bound this is our usual recurrence for for binary search would be constant uh and what we hope to gain here is basically a better base case and I claim that all you get in terms of base case here is T of

**[17:04]:** b equals order 1 and if you think about it this just solves to log n minus log B which is the same thing as log n over B okay which is a small improvement over just regular log n but not a big Improvement I claim we can do better you've actually seen how to do better uh but maybe we didn't tell you so it's a data structure you've seen already B tree

**[17:46]:** yeah so because we weren't thinking about this memory hierarchy business uh when we said B tree we meant like you know two four trees or uh five 10 trees or some some constant bound on the degree of each node but if you make the degree of the node b or some some Theta B Be approximate so you allow big branching factor it's got to be somewhere let's say between B over2 and B um then we can store all of these pointers and all of these keys in a constant number of blocks and so as we navigate down if we're doing just search as we navigate down the B tree we'll spend order one block reads to load in this node and then figure out which way to go and then let's say it's this way and then we'll spend order one memory transfers to read this node then figure out which way to go so

**[18:39]:** the cost is going to be proportional to the height of the tree which uh is just log base B of n up to constant factors uh because we're between B over2 and B but that will only affect this by a small by a factor of two uh so we can do search in a b Tree in log base B of n uh memory

**[19:10]:** transfers okay remember log base B of n is log n / log B so this is a lot better here we had log n minus log B now we have log n divid log B and this turns out to be optimal In the comparison model this is the best you can hope to do so good news uh bad news is we kind of critically needed to know what B

**[19:40]:** was B trees really only make sense uh if you know what B is you need to know the branching Factor uh so this is not a cache oblivious data structure but it has other nice things we can actually do inserts and deletes as well so I said static but if you want Dynamic insert and deleting elements you can also do those in log Bend memory transfers using exactly the algorithms you've seen with splits and merges so all that's good but I want to do it cash obliviously just the search for

**[20:16]:** now and this is not obvious but it's our good friend Venom deas

**[20:31]:** so uh despite the name this is not a data structure that Venom deos invented this is but it's inspired by the data structure that we covered uh and it's actually a solution by Harold procup who was who did the M thesis on this work it's like in the conclusion it's like oh by the way here's how you do search this is like the best page of that thesis um so uh and then I think we called it Bonos because we thought it was reminiscent so here's the idea um take all the items you want to store and you're really tempted to store them in sorted order but I'm not going to do that I'm going to use some other divide and conquer order first thing I'm going to do is take those elements put them in a perfectly balanced binary search tree so this is a BST not a b tree just binary tree okay

**[21:21]:** because I don't know a b is so you know the the maybe the median up here and then there's two children and so on okay the min's over here Max is over here regular BST now we know how to search in a tree right you just walk down the big question is in what order should I store these nodes if I just store them in a random order this is going to be super bad log in memory transfers but I claim if I do a clever order I can achieve log base B of n which is optimal so vanm deis suggests cutting this tree in the middle y in the middle this was n nodes over here and we're breaking it up into uh square root of n nodes at the top right because the height of this overall tree is log n if we split it in half the height of the tree is

**[22:17]:** half log n 2 to the half log n is root n I'm losing some constant factors but let's just call it root n uh then we've got at the bottom everything looks the same we' going to have a whole bunch of trees of size square of n rly okay that's what happens when I cut in the middle level then I recurse okay and what am I recursing what am I doing this is a layout layout from last time we did it we did a very similar thing with uh matrices we had an N byn Matrix we divided into four n over2 by n over2 matrices we recursively laid out the top one quarter uh wrote those out in order so it was consecutive then we laid out the next quarter next quarter next quarter did the order of the quarters didn't matter what matters that each quarter of the Matrix was stored as a consecutive

**[23:09]:** unit so when we recursed good things happened same thing here except now I have roughly square root of n + one uh chunks little triangles I'm going to recursively lay them out

**[23:32]:** and then I'm going to concatenate those layouts so this one uh I'm going to recursively figure out what order to store those nodes and then put those all as consecutive in the array and then this one goes here this one goes here actually the order doesn't matter but might as well preserve the order so I'll do the top one then the bottom ones in order and so recursively each of these ones is going to get cut in the middle recursively lay out the top then the next one Let's do an

**[24:10]:** example let's do an actual tree this is actually my favorite diagram to draw or something my most frequently drawn diagram uh complete binary tree on eight children eight leaves so this is 15 nodes uh happens to have a height that's a power of two so this algorithm Works especially well so I'm going to split in half then recursively lay out the top to lay out the top I'm going to split it in half then I'm going to recursively lay out the top well single node it's pretty clear what order to put it in with respect to itself so that goes first uh then this then this then I finish the first recursion next I'm going to recursively lay out this thing by cutting it in half laying out the top then the bottom Parts okay then I'm going to recursively lay out this 7 8 9 10 11 12 13 14 15 it gets even

**[25:16]:** more exciting the next level up but uh it would take a long time to draw this but just imagine this repeated so that would be just the top half of some tree cut here and then you do the same thing here and here and here this is very different from in order traversal or any other order that we've seen this is the Venom de boas order okay and this numbering is supposed to be the order that I store the nodes so when I write this into memory it's going to look like this okay just the nodes in order and when I'm drawing a circle this going to get tedious uh Etc um and then you know there's pointers here every time I draw a circle there's a left pointer and a right pointer so one's going to point two and three uh two is going to point to four and seven okay so just take

**[26:05]:** the regular binary search tree but store it in this really weird order I claim this will work really well log base bent search let's analiz

**[26:17]:** it okay first claim this is Cash oblivious layout right I didn't use B at all there's no B here start with a binary tree and I just do this recursion to give me a a linear order to put the nodes in just going to store them in that order as linear size all that okay uh now in the analysis again I'm allowed to know B so say B is B and uh let's consider uh the level of

**[26:56]:** recursion uh let's say the first level of recursion uh where the triangles have less than equal to B nodes so I'm thinking of this picture uh I cut in the middle then I recursively cut in the middle of all the pieces that I recursively cut in the middle I started out with a height of log n and size N I keep cutting basically Square rooting the size at some point when I cut I get triangles that are size uh at most Square Ro of B so the tree now will look

**[27:36]:** uh actually let me draw a bigger

**[27:53]:** picture all right uh let's start down here so I've got a triangle less equal to B triangle L equal to B

**[28:47]:** okay this is some attempt to draw a general tree so uh and we we first we cut in the middle level then we cut in the middle levels and let's say at that moment uh all of the leftover trees have size have at most B nodes in them okay it's going to happen at some point it's going to happen after uh roughly log n minus log B levels of recursion right these the Heights Here will be roughly log B we keep cutting in half till height log B then we know the size was B okay so this is a picture which exists in some sense what we know is that each of these triangles is stored consecutively by this recursive layout we guarantee uh that at any level of recursion each chunk is stored consecutively so in particular this level uh level B is nice so what that tells us is that um each triangle

**[29:51]:** with the most B elements um it's consecutive

**[29:59]:** which means uh it occupies at most two blocks if we're lucky it's one but if we're unlucky in terms of uh here's memory here's how it's split into blocks maybe uh it's consecutive but it crosses a block boundary okay but the distance between these two lines is B and B and the length of the blue thing is B so you can only cross one line so you fit in two blocks each of these triangles fits in two blocks now let's think about search algorithm we're going to do regular binary search in a binary search tree we start at the root We compare to X we go left to right uh then we go left to right left to right eventually we find the predecessor or the successor or ideally the element we're actually searching for and the so what we're doing is following some uh root to node path in the tree maybe we stop

**[30:59]:** early worst case we go down to a leaf but it's it's a vertical path you only go down say over here same thing we go let's say because these are the ones I drew uh you go here

**[31:16]:** somewhere okay but in general you're following some root to node path and you're visiting some sequence of triangles okay each triangle fits in basically one block let's assume as usual m b is at least two so you can store at least two blocks which means once you start touching a triangle all further touches are free the first one you have to pay to load in maybe these two blocks every subsequent touch as you go down this path is free then you go to a new triangle that could be somewhere completely different we don't really know but it's some other two blocks and as long as you stay within the triangle it's free so the cost is going to be at most twice the number of triangles that you visit Mt n is going to be at most uh twice the number of triangles visited uh by a root to node path a downward path in

**[32:17]:** the binary search

**[32:21]:** tree okay now to figure that out we need not only an upper bound on how big the triangles are but also a low bound I said the height of the tree is about log B it's close um maybe you have triangles of size B plus one which is a little bit too big so let's think about that case uh you have b+1 nodes and then you end up cutting in the middle level so before you had a height of almost log B slightly more than log B uh then when you cut in half the new heights will be half log B okay and then you'll have only square root Ro of B items in the Triangle so that may seem problematic these things they're at most B they're also at least square root B okay the height of a triangle at this level um is somewhere between half log B and log B luckily basically

**[33:25]:** we're binary searching on height we're stopping when we divided by two and we get something less than log B in height luckily we only care about height so we don't care that there's only root B items here that may seem inefficient but because everything's in a log here because we only care about log B in the running time and we're basically approximating log B within a factor of two everything's going to work up to constant factors okay in other words if you look at this path we know the length of the path is log n we know the length of each uh the height of each of these triangles is at least half log B that means the number of triangles you visit is uh log B over half log B sorry log n / half log B

**[34:25]:** here and the length of the path

**[34:31]:** is log n so the number of triangles on the

**[34:39]:** path is at most log n divided by how much progress we make for each triangle which is half log B also known as 2 * log base B of N and then we get that the number of memory transfers is at most twice that that so number of memory transfers is going to be at most four * log Bas B of N and that's order log base B of n which is optimal now we don't need to know

**[35:17]:** B how's that for a cheat okay so uh we get optimal running time except for the constant Factor admittedly this is not perfect B trees get basically one time log Bas B of n this cach oblivious binary search gives you four times log Bas B of n but this was a rough analysis you can actually get that down to like 1.4 Times log base B of N and that's tight so you can't do quite as well with cach oblivious as cash aware sorry as external memory but close and that's sort of the story here if you ignore constant factors all is good in practice where you potentially win is that uh if you designed a be tree for specific B you're going to do really great for that level of the memory hierarchy but in reality there's many levels to the memory hierarchy if they all matter cash oblivious is going to win a lot

**[36:07]:** because it's optimal at all levels simultaneously it's really hard to build a b tree that's optimal at many for many values of B simultaneously uh okay so that is search any questions before we go on to sort

**[36:27]:** ah one obvious question is what about Dynamic um again I said static obviously the elements aren't changing here just doing search in log based B ofn uh it turns out you can do insert delete and search in log based B ofn memory transfers per uh per operation uh this is one this is my first result in cach abvious land um it's when I met Charles lesus in actually

**[37:11]:** okay but I'm not going to cover it if you want to know how you should take 6851 Advanced data structures uh which talks about all sorts of things like this but

**[37:23]:** Dynamic turns out um there's a lot more to say about this this universe and I want to go on to sorting instead of talking about how to make that Dynamic uh because oh okay search log based BN that was optimal and I said oh you can also do insert and delete in log Bas BN turns out that's not optimal it's as good as be trees but you can do better uh be trees are not good at updates and if you've ever worked with a database you may know this if you have a lot of updates be trees are really slow they're good for searches not good for updates you can do a lot better and that will be exhibited by sorting so sorting I think you know the problem you're given n elements in an array in some arbitrary order you want to put them into sorted order or equivalently you want to put them

**[38:10]:** into a vom Deo order once they're sorted it's not too hard to transfer into this order so you can do search fast or whatever sorting is a very basic thing we like to do um and the obvious way to sort when you have basically a let's pretend we have this B data structure cach oblivious even or we just use regular be trees let's use regular be trees forget about cach obliv external memory we know how to do be trees we know how to insert into a b tree so the obvious way to sort is to do n inserts into uh if you want a cach oblivious B tree or just a regular B tree how long is that take n * log Bas B of n

**[39:05]:** sounds okay but it's not optimal it's actually really slow compared to what you can do you can do roughly a factor of B faster uh but it's the best we know how to do so far so the goal is to do better and basically what's going on is we can do inserts in this universe we can do inserts and deletes faster than we can do searches which is a little weird um it will become clear as we go through uh so what's another natural way to sort what name some sorting algorithms that we've covered that are optimal In the comparison model merge sort that's a good one could do quick sort too I guess I'll stick to merge sort merge sword's nice because a it's divide and conquer and we like divide and conquer it seems to work if we do it right right uh and it's also cach oblivious right there's no B in

**[40:00]:** merge sort we didn't even know what B was so great merge sort uh is divid and Conquer and C Olivia so how much does it cost well let's think about merge sort you take an array you divide it in half that takes zero time that's just a conceptual thing you recursively sort this part you recursively sort this part that looks good because those items are consecutive so that recursion is going to be an honest goodness recursion on an array so we can write a recurrence um and then we have to merge the two parts so merge uh you know we take the first out of each guy compare them output one of them advance that one compare output one of them uh advance that guy that's three parallel scans right we're scanning in this array we're scanning in this array we're always advancing forward which means as long as we store uh the first block

**[40:54]:** of this guy and the first block of this guy who knows how it's aligned um but you know we'll read these items one by one until we finish that block then we'll just read the next block read those one by one the total cost and similarly for the output array we first uh start filling a block once it's filled uh we can kick that one out and read the next one as long as M over B is at least three we can afford this three parallel scan it's parallel not it's not really parallel it's more like interleaved scans uh but we're basically scanning in here while we're also scanning in here and and scanning in the output array and we can merge uh two sorted arrays into a new sorted array in scan time n over B + one okay so that means uh the number of memory

**[41:47]:** transfers is 2 times the number of memory transfers for half the size like regular merge sort plus uh n over B + 1 that's our recurrence now we just need to solve it well before we solve it in this case we always have to be careful with the base case base case is Mt of M this is the best base case we could use let's use it uh when I reach an array of size M uh I read the whole thing and then that's all I can pay so I won't I won't incur any more cost as long as I stay within that region of size M maybe I should put some constant time M because this is not an in algorithm so you know maybe 1/3 M or something as long as I'm not too close to the cache size I will only pay M overb memory transfers so far so

**[42:54]:** good now we just solve the recurrence this is a nice recurrence very similar to the old merge sort recurrence we just have a different thing in the additive term and we have a different base case the way I like to solve nice recurrences is with recursion trees this is actually a trick I learned by teaching this class before this cach oblivious was really painful to me because I could never solve the recurrences then I thought the class like oh this is easy uh hope the same transformation happens to you you'll see how easy it is once uh we do this example okay this is merge sort I've put remember recursion Tree in every node you put the the additive cost uh so that if you added up the costs of all of these nodes you would get the total value that this expands to because we're basically making two children of size n/2 and then we're putting at the root this cost which means if you add up all of these nodes uh you're getting all of these costs and that's

**[43:52]:** the total cost okay so it's n over B at the top then it's going to be n/2 / B and so on I'm omitting the plus one just for cleanliness you'd actually have to count um and this keeps going until we hit the base case this is where things are a little different from regular merge sort other than the divided by B uh we stop when we reach something of size M so the leaf level we have something of size M which means we basically have m overb in each leaf and then we should think about how many leaves there are uh we this is just n/ m leaves I guess lots of ways to see that uh one way to think about is we're conserving Mass we started with n items split it in half split it in half so the number of items is remaining fixed then at the bottom we have M items and so the number of Le has to be exactly n over M because the total should be n okay you can also think of

**[44:54]:** it as 2 to the power log of that uh we have usually log n levels but we're cutting off a log M at the bottom so it's log n minus log m is the height that's actually need that the height of this tree is log n minus log M also known as log n/ M uh okay so we've drawn this tree now what we usually do is add up level by level that usually gives a very clean answer so we add up the top level that's n / B we add up the second level that's n/ B by conservation of mass again and because this is a linear function okay so each level in fact is going to be exactly n over B cost uh we should be a little careful about the bottom because the base case I mean it happens if the base case matches this but it's always good practice to think

**[45:47]:** about the leaf level separately uh but the leaf level is just M over B * n/ m the M's cancel so M over B time n / M this is n over B so every level is n over B number of levels is log of n / M cool so number of memory transfers is just the product of those two things it's n/ B times that log log n / M now let's compare over here that was that's sorting uh over here we had a running time of n time log base B of n over here so uh you know this is n log n divid log B right log base B is the same as dividing by log B so n log n divid by log we had regular sorting and then we divide it by log B over here we have basically regular sorting time but now we're dividing by B that's a huge Improvement a b divided by log B Improvement uh so before we were I mean think of B being like a million

**[47:13]:** so before we were dividing by 20 which is okay but now we're dividing by a million that's better okay so this way of sorting is so much better than any way of than than this way of sorting okay still not optimal but we're getting

**[47:44]:** better we can actually get sort of The Best of Both Worlds divide by B and divide by log B I claim uh but we need a new algorithm any suggestions for another

**[48:12]:** algorithm I want to divide into block size B so you mean you merge sort so merge sort I take my array I divide it into blocks of size B I could sort each one in constant in one memory transfer and then I need to merge them so then I've got n / B sorted arrays uh I don't know how to merge them it's going to be hard but very close so the answer is indeed merge

**[48:48]:** sort uh what we covered before is binary merge s you split into two groups what I want to do now is split into some other number of groups so that was n overb groups that's too many because merging n over B arrays is hard merging two arrays was easy uh assuming M over B was at least three I could merge these guys just by parallel scans so you have the right bound B way uh maybe square root of B that's what I like to call Root Beer uh uh nope I do call it that um yeah M over B that's what I'm looking for why M over

**[49:44]:** B just because m overb is up here nice not not the right reason but you're get a frisbee anyway all right see if I can do this H would you like another one add to your collection all right um so m overb is the right answer wrong reason but that's okay um it all comes down to this merge step so M over B way means I take my problem size n let's draw it I divide into chunks I want the number of chunks that I divide into to be M over B meaning each of these has size I don't know n over M over B it's a weird we I don't that's weird this is natural because this is how many blocks I can have in Cache I care about that because if I want to do a multi-way merge you can mimic the same binary merge you look at the first item of each

**[50:38]:** of the sorted arrays you compare them in this model comparisons are free let's not even worry about it in reality use a priority q but all right so you find the minimum of these let's say it's this one you output that and then you advance same algorithm right that will merge however many arrays you have the issue is for this to be efficient like it was here we need to be able to store the first block of each of these arrays how many blocks do we have room for M over B this is maxing out merge sort this is exactly the number of blocks that we can store and so if we do M overb way merge sort merge remains cheap and M overb way merge uh cost uh n / B + 1 just like before it's m overb parallel scans m overb is exactly the number of scans we can handle okay technically

**[51:36]:** we have with this picture M over B+ one scans so I need to write M over B minus one but won't make a difference okay so let's write down the recurrence it's pretty similar memory transfers size M we have m/b sub problems of size n / m/ B still conservation of mass and then we have plus same thing as before n/ B plus one so it's exactly the same recurrence we had before we're just splitting into more problems but the sums are going to be the same still going to add up to n over B at each step because conservation of mass and we didn't change this so level by level it looks the same the only things that changes is the number of levels now we're taking n and we're dividing by M over B in each step so the the height of the tree number of levels of the tree of the recursion

**[52:33]:** tree now is before it was log base 2 of n / M now it's going to be log base M over B of n/ M okay if you're careful I guess there's a plus one for the leaf level I actually want to mention this plus unlike the other plus ones I'm going to mention this one because uh this is not how I usually think of the number of levels show you why uh if you just change it by one you get a slightly cleaner formula this has got M's all over the place uh so I just want to rewrite uh n/ M here then we'll see how good this is this is just pedantics uh log base m/ B of N I really want n/ B uh to make this n/ B I need to multiply by bide by m okay these are the same thing right n / M B's cancel okay but I

**[53:37]:** have a log of a product I can separate that out let's go over here uh this is log base M over B of n/ B this is what I like uh and then basically minus log base m B of M B uh I put a minus so it's M over B if I put a plus it would be B over M but in fact m is bigger than b so I want it this way uh and now it's obvious this is one so these cancel okay so that's why I wanted the one just to get rid of that it doesn't really matter just a plus one but it's a cooler way to see uh that in some sense this is the right answer of the height of the tree now we're paying n/ B at each cursive level so the total cost is What's called the Sorting bound this is optimal n/ B * log base m/ B of n/ B oh my gosh what a mouthful but every person who does external

**[54:43]:** memory algorithms and cach obivious algorithms this everyone knows this it is the truth turns out there's a matching lower bound it's a weird bound but let's compare it to what we know so we started out with n log n/ by log B then we got n log n / B uh let's let's ignore this has almost no effect the part in here now we have n log n / B and divid log M over B okay it's not quite dividing by log B but it's it turns out it's almost always the same uh in some sense this could be better if your cache is big now you're dividing by log M roughly before you're only dividing by log B and turns out this is the best you can do so this is going to be a little bit better than merge sort if your cache is I don't know uh 16 gigabytes like your RAM

**[55:36]:** caching your uh caching your dis then log m is pretty big it's going to be 32 or something um 34 I guess uh log M okay I have to divide by B so it's not that good but still I'm getting an improvement over regular binary merge sort and you would see that Improvement these are big factors the big thing of course is dividing by B but dividing by log of M B is also nice and best you can do okay obviously I needed to know what m and b were here so the natural question next is cach oblivious sorting and that would take another lecture to cover so I'm not going to do it here but it can be done cach obliviously you can achieve the same thing and I'll give you the the intuition uh there's one catch let me mention the catch uh

**[56:42]:** here so cach oblivious

**[56:50]:** sorting to do optimal cachia sorting like that bound turns out you need an assumption called The Tall cache

**[57:09]:** assumption uh simple form of the tallach Assumption is that m is at least uh b^ s what that means is M over B is at least B in other words the cachee is taller than it is wide the way I've been drawing it that's why it's called the tall cache assumption and if you look at real caches this is usually the case um I don't know of a great reason why it should be the case but usually is so all is well uh you can do cash assorting turns out if you don't have this assumption you cannot achieve this bound uh we don't know what bound you can achieve but we just know this one is not possible you can get a contradiction if you achieve that without tall cach so it's a little bit weird you have to make one bonus assumption you can make a somewhat weaker form of it which is uh

**[58:00]:** m is Omega B to the 1.000000 one that'll do in general 1 plus Epsilon any Epsilon will be fine we just need that the number of blocks is at least some B to the Epsilon where epsilon's a constant bigger than zero okay then you can do CIA sorting let me tell you how uh we want to do M overb way merge sort but we don't know how to do we don't know what M over B is so instead we're going to do something like n to the Epsilon way merge

**[58:42]:** sort so so interpretation this is back to your idea roughly uh we're dividing into a lot of chunks and then we don't know how to merge them anymore because we can't do this simple um you can't do regular merge with n to the Epsilon chunks could be n to the epsilon's too big uh so how do we do it we do a divide and conquer merge um this is actually called uh funnel sort because the way you do a divide and conquer merge looks kind of like a funnel actually looks a lot like the triangles we were drawing earlier uh it's just a lot Messier to analyze so I'm not going to do it here take another 40 minutes or so uh but that's some intuition of how you do cash oblivious merge sort uh I think that's what I want to say about cash oblivious stuff oh one more thing one more cool thing

**[59:36]:** you can do I'm a data structures guy so sorting is nice but what I really like are priority cues because they're more General than sorting we started out by saying hey look if you want to sort and use a b tree you get a really bad running time that's weird because usually BST sort is good in the regular comparison model it's n log n uh so B trees are clearly not what we want is there some other thing we want and it turns out yes uh you can build a priority Q which supports insert and delete Min and a bunch of other operations each of those operations costs 1 over B log base M overb of n/ B amortized

**[1:00:27]:** memory

**[1:00:32]:** transfers bit of a mouthful again but if you compare this bound with this bound exactly the same but I divide it by n which means uh if I insert with this cost n times I pay the Sorting bound if I delete Min with this bound n times I get the Sorting bound so if I insert n times and then delete all the items out I've sorted the items in sorting bound time so this is the data structure generalization of that sorting algorithm now this is even harder to do uh there's an originally it was done external memory it's called buffer trees then uh we did it cach obliviously it's called cach oblivious priority cues we weren't very creative um but it can be done and again if you want to learn more you should take 6851 Advanced data structures uh which leads us into the next next topic what class you should take next classes

**[1:01:30]:** classes that's what I meant to say uh

**[1:01:37]:** so all

**[1:01:43]:** right so a lot of bias here and well I'm just going to give a lot of classes it's a lot of them uh I believe this is in roughly numerical order almost let's Chang a little bit so many classes uh you okay with numbers you want titles um all right the obvious follow-on course to this class is 6854 which is Advanced algorithms it's the first graduate algorithms class this is the last undergraduate class roughly speaking uh with the exception of 6047 but in sort of terms of straight General algorithms this would be the natural class it's only in the fall sadly not next fall uh but in general it's cool class it's very broad overview of algorithms but much more uh hardcore I guess um it's an intense class but covers a lot of fields a lot of areas of algorithms then all the other ones I'm going to list are more specialized so 6047

**[1:02:42]:** is computational biology so if you're interested in biology you want algs applied to biology that's a cool class it's also an undergrad class everything else here I mean you know the story you take grad classes all the time or you will soon uh if you want want to do more algorithms so uh 6850 is computational geometry or I think it's called geometric algorithms so we've seen a couple examples like the convex Hall divide and conquer algorithm um and the range trees uh those are two examples of geometric algorithms when you have points and lines and stuff maybe in two Dimensions maybe in three dimensions maybe in log n Dimensions uh if you like that stuff you should take computational geometry that's what this was the devil that led me into algorithms in the first place Cool Stuff um um 6849 is my class on folding algorithms this is a special SE special type of geometric

**[1:03:33]:** algorithms where we think about paper folding and robotic arm folding and protein folding and things like that um so that's a bit of a specialized class 6851 I've mentioned three times now uh Advanced data structures um then we've got 6852 it's neighbor uh this is ny's distributed algorithms class so if you like the week of distributed algorithms there's a whole class on it um she wrot the textbook for it uh then there's 6853 this is algorithmic Game Theory if you care about algorithms where uh involving multiple players and the players are each selfish and they have no reason to tell you the truth and still you want to compute something like I don't know minimum spanning tree or pick your favorite thing everyone's lying about the edge weights and still you want to figure out how to design a mechanism like a an auction so that you actually end up buying a minimum spanning tree

**[1:04:25]:** you can do that and if you want to know how you should take 6853 uh else we have 6855 is Network optimization so this is like the natural follow on of network flows if you like Network flows things like that uh there's a whole universe called Network optimization uh has lots of fancy basically graph algorithms where you're minimizing or maximizing something uh okay this is fortuitous alignment 6856 is kind of a a friend of 6854 these are both taught by uh David carer uh this is randomized algorithms so this is a more specialized uh approach you don't I don't think you need one to take the other but this is the usual starting class and this is specifically about uh how randomization makes algorithms faster or simpler usually they're harder to analyze but you get very simple algorithms that run just as well as their deterministic versions sometimes you can do even better than the

**[1:05:22]:** deterministic versions uh then there's the Universe this is a great numerical coincidence well probably not a coincidence but there's 857 and 875 uh I have to remember which is which 857 is applied cryptography 875 is theoretical cryptography at least as I read it um so they have similar topics but this is more thinking about how you really achieve security and crypto systems and things like that uh and this one is more uh algorithm based and what kind of theoretical assumptions do you need to prove certain this is more proof based and this is uh more connecting to systems uh both great topics uh and I have one more out of order I guess just because it's a recent Edition 6816 is multicore programming that has a lot of algorithms too uh and this is all about parallel computation how when you have multiple cores on your computer how can you compute things like these things

**[1:06:22]:** faster than everything we've done um it's yet another univers which we haven't even touched on in this class but it's cool stuff and you might consider it um then we move on to other Theory classes that was algorithms uh some more obvious candidates if you like pure Theory are 045 and 840 this is the undergrad version this is the grad version although by now the classes are quite different so they cover different things some of you are already taking 6045 it's right before this lecture uh these are General uh theory of computation classes autom complex things like that uh if you liked the brief NP completeness lecture uh then you might like this stuff uh there's so many more complexity classes and other cool things you can do uh if you really like it there's Advanced complexity Theory uh there's basically randomized complexity Theory how Randomness affects it's just the complexity side not algorithms uh

**[1:07:16]:** then there's Quantum complexity theory if you care about quantum computers as Scott says it's uh proving things you can't do about with computers we don't don't have uh it's complexity it's all about lower bounds uh and then there's coding Theory which is another Universe it's actually closely related to uh it comes out of like signals and systems and electrical engineering but by now it's closely related to complexity Theory you can use codes bounds on codes to prove things about uh complexity Theory anyway uh Choose Your Own Adventure now I have one last topic which was not on the outline this is a bit of a surprise uh and I want to remind you it's boring surprise I want to remind you uh to fill out student evaluations because you know we want to know how we did and how we can continue to improve the class but really we want to know who's the better

**[1:08:13]:** teacher so but more importantly than who is the better teacher I think we all have a dying question which is who is the better frisbee thrower so uh I want to invite stry davidas our co- lecturer here to uh a duel

**[1:08:38]:** um I think you mean uh I think you mean no contest uh not so sure maybe maybe I actually I'm pretty sure but I I I want to take you on man blue or purple uh blue a good choice Blue's better remember purple's better remember all right uh so how how are we going to do this so uh you guys get to cheer and bet bet I I I don't think we can condone them betting money I think maybe maybe they could bet their frisbees right anyone got a frisbee on them we could bet bet those yeah all right all right maybe not put your frisbees on me yeah huh all right all right so uh uh some rules here we actually talked about this so the way this is going to work I mean it's going to be algorithmic obviously and we get to choose our algorithm maybe a little game theory here we're

**[1:09:39]:** going to toss the coin and we're going to decide who goes first right so we want we want spin the Frisbee remember what happened with that right so you get to you get to call head Tails while it's spinning oh while it's spinning while it's spinning this is our Super Bowl uh heads whoa trick uh Tails Tails all right all right you're going to throw first okay that's your choice I don't know if you've heard the legend of William Tell how many of you have heard the legend of William Tell all right so that was a 14th century Swiss Legend where there was this Archer who's renowned for his uh skill and he was forced by this villainous King to shoot an apple off the top of his son's head okay than so so we going to we going to reenact that did did you bring your

**[1:10:40]:** daughter I I was thinking ta but there's a there's a big difference between the 21st century and the 14th century what is that sued get sued yeah seventh century No that many more lost suits in the 21st century right so we want to avoid lawsuits yeah and and genetically modified electronically modified apples yeah that's going to be another difference so we decided we just throw frisbees at each other right and uh we decided I'm going to throw at you and try to hit a apple off of your head yeah well you might want to tell them what we decided about the Apple well I brought an easy to hit Apple a nice big apple the cowboy hat the cowboy hat right should be a little easier so I get I get to wear hat first y right because you're going to throw first okay and it this is really simple guys knock the hat off

**[1:11:33]:** I I guess from the furthest distance and win right in your case lose but yeah I just I just for the you know Peta people in the audience I want to assure no humans will be harmed during this performance only professors only professors and maybe egos Pride all right uh yeah I think seven is a good number okay right so seven I'm you get to you get to you get to pick a you can you can stand right here that's probably what's good for you but uh or you can go all the way up there and I'll have I'm going to if you knock this hat off I'm going to have to match you right all right so furthest way wins I I'll I'll try from about here right right all right got to got to look good here man right I have to do looking I'm going to stand uh I'm going to stand

**[1:12:27]:** right here right okay uh okay all right I I I got to gear up for this okay look I know how well you throw right it's embarrassing yeah I I I can't deal with this so I you know I just have no confidence in in the way you throw so I borrowed this okay all right since this is mine it's going to cost you a throw to wear this hey all right whatever Fair all right all right now I'm feeling much better about this um I want I want claim to have a pretty face but I like it just the way it is okay just the way it is all right well since we have a little more protection maybe I'll start from farther back all right I think I'll hold this up here right that okay so I just have to hit the hat off right easy y

**[1:13:30]:** all right right you can keep that uh so oh right so I'm gonna get closer one step closer luckily my steps are much bigger than your steps okay throw

**[1:13:48]:** two throw three

**[1:13:55]:** row four that didn't even hurt come on man throw a little harder

**[1:14:08]:** here all right Mark it all right I marked my spot you got a couple more throws here to do better more throws yeah well you can do better go back you got a couple more yeah

**[1:14:25]:** you almost hit me I'm getting better uh can I go back now yeah I don't know the rules

**[1:14:41]:** whoa goodness no contest little wor here one more frisbee uh two more frisbee that was your Frisbee one more all right I think I think we've we've done binary search here all right you need this and you don't really need this but I'll give it to you so much confidence well I have so much confidence in you I I brought some extra

**[1:15:20]:** frisbees I get to use all of them huh you you need it man all right no we going to be fair you threw seven I'm going to throw seven 1 2 3 4 five six seven yeah you got a bit of a big head here all right do this all right so I put the Hat on the head okay where where were you standing by the way uh way back here right uh no no no no I was right there okay right there all right right here can I hold on to the Hat no you can hold on to your helmet all right

**[1:16:07]:** wow how many thr start from right who that was close oh I raed it but it's supposed to fall off what my head getting kind of tight here guys

**[1:16:36]:** whoa oh does that count it does count it's a tie so far it's a tie so far it's a tie all right if I knock it off I win there you go

**[1:16:58]:** this was fair and square we want the world to know that we did not deflate these frisbees

**[1:17:14]:** okay so not only did we do a bad job of throwing frisbe to you guys we didn't throw enough frisbees as you can see through the term so if you want a frisbee uh pick one up and uh if you're embarrassed about throwing frisbees with these letterings on it I got two words for you paint remover all right have a good summer and and have fun on this on the final exam
