Problem Session 3

All right, welcome to practice problem session three double O six. Um today we are going to go through a bunch of problems which you should have already. Um I was thinking of skipping the very first problem because it's just a mechanical thing. If we have time at the end we can come back to it, but there's not really any insight I can give you in how to approach this problem. It's just do you understand hashing? So I want to go into the more creative problems first. Uh let's start with problem 3.2 hash sequence. Uh so I'll just read it and then our first task is to convert the the word problem into a concise formal algorithm's thing we need to achieve, then we need to come up with ideas for how to achieve it, and we need to check the details. That'll be our general pattern. So this problem says hash tables are not only useful for implementing set operations, they can also be used to implement sequences. Remember from lecture two we have a set uh interface which is about querying items by their key and sort of intrinsic order that's about the items themselves versus a sequence interface that we started out with with linked lists and so on uh and arrays for uh where we're given an order we want to maintain that order and that order may not have anything to do with the items themselves. That's what we call an extrinsic order. We're told what the order is by saying insert this item after this one or append this one to the end or prepend it to the beginning. Uh so uh in lecture last week we saw hash tables implement sets and let me just remind you uh some things that they can do. So we have on the one hand a set and hashing. So this we're going to need this in a moment. This is just a reminder from lecture. Uh we can build one in linear time expected. We can find an item in constant time expected by key and we can insert or delete an item uh in constant expected amortized. Okay. Uh so this is a black box that we're given um and the problem statement says that imagine you're given a hash table as a black box, which means we're given a thing that behave behaves just like a Thank you. two Uh we're given something that is a hash table, but it's black box in the sense that we're not allowed to reach in and change the implementation details. We're supposed to use it as is just by calling its interface. So in particular we're given these three operations. I'll maybe also use iter to iterate through the items. Uh so we're allowed to build something in linear time, find, and insert and delete in constant expected amortized. Uh and what the problem is asking is to build out of this data structure a sequence with particular time bounds. Uh so this is what we call a reduction in that we're going to convert uh I guess technically we're reducing the sequence problem to the set problem um because we're showing how to solve the sequence problem using the set problem but the way we'll think about it is in the other direction. We're given a data structure to solve set and we're going to convert it into a data structure that solve sequence. So given that we already know how to do this from lecture, we're going to learn how to do this. Um this is teaching you new stuff in a problem set. Uh so the specific bounds that we're told to achieve are build in constant expected time uh get and set at in constant expected time uh insert and delete at in linear expected time and insert and delete uh first and last in running out of room here constant expected amortized. Okay. Um so this is just what we're told to do and now we start thinking. So we're given this, we want to build this um and so I'm going to tell you a little bit about my thought process about when I'm presented with a problem like this. First thing is to read the problem and see okay, what what's what's the hard part here? What what are the challenges? So clearly we have to do all four all four of these types of operations. Build in linear expected time, that's basically everything we've seen. Uh get or set at in constant expected time, that's fast. Uh and that feels kind of like this find operation. So both of these uh seem pretty matchy matchy, so that looks like a good mapping. I'm going to try to build these operations using those operations. Insert and delete uh at a specific location in constant expected time. Sorry, linear expected time. That's big. Linear expected time means I can rebuild the entire data structure every time I do an operation. So this is easy. Okay, that's first thing you realize, this is big. Great. So I don't really have to worry about these operations. I mean I do have to implement them, but it's not hard to do it that fast cuz I can rebuild. Um and then here, insert and delete at the beginning and the end of the array. These are the deck double ended queue operations, insert and delete at either end in constant expected amortized time. This I feel like is a tricky one. Uh you've seen one way to do this in the problem set but now we're going to see another way with Okay, the other thing to notice is these expected words. Um in this case we're told to use hashing, but in a lot of the problems you're not told how to solve it or what you should be basing your thing on. Um and so expected is always a good keyword uh because it means randomization is involved somehow. If you're told the bound is going to be expected, uh you should you you probably need to use randomization. Um and in this class the only form of randomization you will use is essentially hashing. So uh that's a good hint. In this case we know that we're supposed to use hashing. All right. So um this is going to be the challenge. Um but uh any ideas on how we might tackle this problem? How can we So set, remember every item has a key uh in a sequence items are just items and we're told to insert and delete them at particular locations but they don't have keys. So one of the challenges is going to be to take our items here, give them keys so that we can store them in a set. Otherwise uh we can't use find. There's no keys there. There's no way to search by key. Ideas? So let's think about what we want to do. Let's start with uh so build I think it's fine. If you Well, just want to build a data structure, you don't need to do anything. Uh the hard part are the queries or updates you wanted to be able to do on your data structure. Let's start with this operation. Get and set at. So remember get at you're given an index I and you want to uh find the item at position I and set at uh we're given a a position and we want to change the item stored at that position at that index I. Now over here what we're given um we can insert and delete, but the main sort of look up, let's think about get at first. The natural mapping given this arrow uh is find. Find will search for an item by key. So here's just staring at that. Once you look at all the possible pairings you could do, we have find by key over here and we need to implement get at by index. So let's make the indices keys. Okay, so this is idea number one. Uh index assign a key to each item um equal to index in the sequence. Okay, so then when I do to implement get at, I can just call find of I I is also a key and that should give me the thing that I want. Maybe for this to make sense, let me tell you how I'm building. So if I'm given say an array A of items uh and they're both the only name conflict here is build, so let me call this one sequence build. And I'm going to implement it using set build. And uh I'll use some short shorthand notation here. Let's say I want to make an object that has a key equal to I and a value um equal to A of I uh that's I my object notation for I equals 0 1 to uh size of A minus 1. Yeah, that's a little bit code-like, but not quite literal code. Uh so, I'm just going to use this to say, let's make an object that has two um parts. One is called the key, so we can talk about the object.key. Uh so, we can switch sets one to do. And we're also going to store a value, which is the actual item that we're given. So, I'm just uh cuz these are given in a sequence, I'm just representing that sequence order by assigning I to be the key. And so now, if I want to find the item at index I, I can do find of I. And technically, I should probably do {dot} value. That will give me the actual item that's stored at that position. When I do find of I, I'm going to get this whole object with the key of I, and then I want to get the value part of it. So then, set at um I can just use this find operation to get the object and set its value to X. Boom, we've implemented array-like semantics, get at I and set at I um using a set. If you've ever programmed in JavaScript, this should feel very familiar cuz JavaScript actually implements arrays at's at least at the conceptual level uh as just general mapping types, which are they call them objects, but they are basically sets. Um and if it's even grosser, they convert the in- integers into strings and then index everything by the strings. Semantically, anyway. Implementation details can be more efficient, but conceptually, that's what's going on. And so that's the the idea we're doing here. Which seems great. Um Any any problems? So, I have let's see, there's insert at and delete at. As I mentioned, what I'm going to do for those operations is just rebuild the entire structure. And just write that briefly. Uh basically, uh let's just iterate all the items. Iterate all items. Um say into an array. I can insert delete one of them. And then rebuilt. Okay, and if I was writing a P set answer, I would say a little bit more detail what I mean in this step. Um I've done it in the notes, not that hard. But we can afford linear expected time. I can afford to call build again. Uh I guess technically, I'm calling this build. Sequence build. Uh so, I can afford just to extract things into an array, do the linear time operation on the array of with the shifting and everything, and then just call build again. Yeah, question? I have a question. The question was get at I. Yeah. You're saying you have sequence build and get at I. Uh sorry. No, uh these are separate definitions, yeah. Sorry, they got a little close. So, this is the definition of get at. Okay. This is the definition of sequence build. Oh, I see. Yeah. Just asking. Okay, all good? Yeah? Can you uh explain insert and delete again? Explain insert and delete. Okay, so maybe I should actually write one of them down. Um or I'll just draw a picture, maybe. So, we have this data structure uh which is now a sequence data structure represents some sequence of items. Uh and my goal is to say delete the ith item. So, there's some items in here, X0 up to Xn minus one. I want to remove Xi from the sequence. Or I guess I should draw it this way. It's coming out. So, uh what I'm going to do is first extract all the items from the sequence. And I didn't write it, but there's a an interface over here called iter which just gives me all the items in order. So, I'm going to extract this into an array sequence. Uh let's say uh I'll I'll just build a static array of size n. Uh I also have a length operation that tells me how many items are in here. And the the iter operation will give me all the items in order. And so I'll put into my array X0 and then X1 and so on as they come out. Then uh I go to position I. And I want to delete that item and shift all the others over. This is the boring This is I think we even said how to do delete at in dynamic arrays in recitation two, pretty sure. So, it's just I'm just mimicking that. I'm building this just to get the new order of things. And then I'm applying via the build operation I'm building a totally new sequence. And that's how I would implement delete at. One way. There are other ways, yeah. Um do you mind if I talk about the space and the answer or How much space is this using? Uh oh, it it problem with space if you're inserting. If you're inserting, you probably want to allocate a static array of size n plus one. You know exactly what's going to happen. So, just allocate a little bit bigger, then you can do the shift. You could also use dynamic arrays, but then you would get maybe an it's not an amortized bound cuz you're only doing one insertion. This The point is this is really easy. We can spend linear time. So, we can rebuild the We can rebuild this array three times if we wanted. Question? Uh what if you were to load external uh non-constant space? Huh, you're going to throw me open problems. Uh what if you only have constant extra space? Uh Right. Then I think we need to use insert and delete. So, we could Good question. Um we could conceptually do the shifting, but do it using insert and delete. So, we can uh So, let's do the the delete case again. So, we want to uh Here's Xi. We want to replace it with Xi plus one and so on. Um And so, we can start out by deleting the item with key I. That will get rid of this guy. Then we can delete the item with key I plus one. Give it and that gives us the item. And then we can reassign its key to be I I instead of I plus one. And then reinsert it. So, we can take this item out. It has a key which is I'll draw this properly. So, we have key I plus one and value X I plus one stored in this data structure. Then we update the key to I. And then we reinsert it and it takes the place of this guy. So, you could do that. You could go down this list and or not the list, but you could iterate for I equals Sorry, for J equals I to n minus one. And for each of those items, delete it, change its key, reinsert it with the new key. And then you don't have to build this intermediate data structure. So, if you're told to minimize space, great. And maybe you think of that as simpler. I like to think of this as simpler cuz I Point is I have linear time. I can do crazy, silly, very non-data-structure-y things where I just start from scratch. Okay. Great. But there's one more set of operations, insert delete first and last. Are these easy? Good? Should we try? Uh we can insert last. Uh so, this is given an item X, we want to add it to the end of the structure. So, that means its index is going to be equal to cuz we started zero, it's going to be equal to the length current length of the structure. So, let's just insert a new object which has key equal to length and it has value equal to X. We're done. Delete last, similar. Just delete the item with key length minus one. Okay, WHAT ABOUT FIRST? THIS IS SUPPOSED TO ADD X to the beginning of my sequence. Well now, I realized I have a problem because I want this new item to have key zero because after I do an insert first, get at of zero should return this item. But I already have a item with key zero. And an item with key one, and an item with key two, and so on down the way. And so, if I wanted to give X a key of zero, I have to shift the keys of all of those items, just like we were doing here. And that's going to take linear time. But we're supposed to do this in constant expected amortized time. So, that's no good. So, this idea is not enough. It's not a bad idea. It's still a good idea, but it's no longer what we actually want to do. It's only morally what we want to do. So, what Do you have any thoughts on how we might get around this problem? Seems like inserting at position zero, I need to shift everything down. Linear time, that really sucks. Yeah. Um you could create some sort of link to some something else. Link this data structure with another one? So, we could build more than one set. That's certainly allowed. Uh I don't know how to do Oh, I see. You're saying maybe make build a whole 'nother structure for the items that come before zero? Yeah. Yeah, actually that would work, I think. Maybe. Uh it's like in the Pset you then you have to deal with when if you delete one of them it becomes empty then things get messy. If you delete first is also going to be a problem because I delete the beginning of this data structure uh then I lose my zero item and I want the new zero item to be the one item and so again all the indices shift. So delete and inserting at the front is hard. So we could do that trick like in the Pset but or in like in last problem session and so on. Um but there's a much simpler idea. Uh can you have an extra variable to keep track where is the beginning? Nice. I can have an extra variable to keep track of where the beginning is. Uh Call this first. Uh this is going to be the key of the uh first item. Index zero. Another way to say this is let's just use negative integers. Right? Set sets work for any keys, any integer keys. Okay, actually we technically said they should use keys of zero to U minus one but then uh if you have negative numbers you can easily fold Wait, doesn't it work like in like Uh Python negative numbers means something else but we're not using the Python interface, we're using our custom magical uh set interface which we show how to implement in recitation notes which can take an arbitrary key, it hashes that key and uh you know, finds a place to put that item. So we're not actually storing things in order here, we're storing things in a hash table but we're not supposed to get into the implementation details. I think the way we presented hashing with our uh universal hash functions we only allowed positive numbers so maybe technically I should point out if you have uh positive and negative numbers you can fold this in half by uh mapping zero to zero, one to two, two to four, spreading it out and then you can take minus one and map it to plus one and minus two and map it to plus three. So this is like uh multiplying each of these guys by two and multiplying each of these guys by minus two and adding one. Um and then you get uh non-negative integers out of all integers. This is uh typical math trick for showing that the number of integers is equal to the number of non-negative integers which may seem weird to you but they're both countably infinite. Um so you could if your structure only supports non-negative keys you could map negative keys in this way and throw them into the hash table. Okay, so now I allow negative things for uh like that and so great, if I want to insert at the beginning what I can do is just decrement my um first variable which is keeping track of the index. So initially first is going to be zero. Uh so I'm going to add into my build uh first I'm going to say first equals zero uh cuz I start with key zero and when I initially build the structure uh and if I want to if I need more room before zero I just set first to minus one and if I already have minus one element I'll decrement it to minus two. Decrement means decrease by one. This shows my assembly language programming. This is usually a built-in operation on most computers and then uh I can insert an item with key first and value X. Great, and if I want to delete the first item I would delete the item with key first and then increment first. Uh and now all of my operations have to change a little bit. Let me use another color. Um because I was implicitly assuming here that all my indices started at I but now they start at first. The um index zero maps to key first and so the right thing to do here is plus first. And plus first. Basically add a whole bunch of plus first throughout. Uh this one's probably fine if I'm globally rebuilding I can reassign all my labels uh but this one should be first plus plus length. Okay, so just by keeping track of where my keys are starting I can do this shifting and not have to worry about stuff. And this is a lot easier than having to worry about uh maintaining two structures and keeping them both non-empty and stuff like that. Uh because of if I assume my my set has this power uh dealing with negative integers and strings and whatever else. Cool. Yeah. Uh why didn't I use a linked list? Because this. Linked lists are very bad at get and set at a given index. Is that the bottom idea? Is that the purpose? This is not a linked list. This is just storing a single number as integer in your data structure that says what is the smallest key in my data structure. That's all it does. It's it's a counter. Okay, so data structure keeps track of its length and it keeps track of the minimum key and so it will always consist the invariant is it will always have keys from first up to first plus length minus one. And that's what we're exploiting here. We've no idea where first will be. It depends how many operations you've done, how many inserts at the beginning and so on but the keys uh keys will always be first to first plus length minus one. This is what we call an invariant. Just want to write these things down so you can understand what the heck why is your data structure correct? Because of invariants like this which you can prove by induction by showing each time we do an operation this is maintained. Even when I'm changing first in order to maintain this invariant. Cool. Sometimes you come up with the invariant first. In this case I came up with it ipso facto post facto after the fact uh Cool. Let's move on to problem three. Which is called Critter Sort and uh the other key thing I want you to learn about uh question sorry. Yeah, um so when you do first first plus one is that a rebuilding of a new of a new structure? This is just a sentence. It is not an algorithm or data structure. This is a mathematical property. This is not an assignment. This is a mathematically is equal to. are rebuilding though. Because you're doing first plus one. So are you asking about one of these operations? Like this one? Oh okay, never mind. I get it. Yeah. Okay. So the other important takeaway I want you to get about reading our problem sets is that they have hidden humor inside. I don't know if you've noticed but here's an example of a problem called Critter Sort. Ashley Ketchum collects and trains pocket critters to fight other pocket critters in battle. What is this a reference to? Digimon. Digimon. Wow, you guys are so young. Pokemon. The the old the ancient form. Pokemon is short for pocket monsters and in fact in the original anime okay. I I don't know. This is all after my time. We can debate after. So pocket critters is a reference to pocket mons pocket monsters which is Pokemon. Who's Ashley Ketchum? Ash Ash Ash Ketchum is his full name in the English version um just totally different name in the Japanese version but uh they're both puns on collect them all, right? All right, so that's the important stuff. We'll see more jokes later. Um so uh there's this setup but basically we have N critters and we want to sort them by four different things and so I'm just going to abstract this problem into sort N objects by the following types of keys and for each one we want to know what the best sorting algorithm is and there's this footnote that's very important. It says faster correct algorithms will receive more points than slower correct algorithms. Um also correct algorithms will receive more points than incorrect algorithms but that's implicit. Incorrect generally gets zero. Okay, so uh part A uh it says species ID but basically we have integers in the range uh minus N to N. So uh if I want to sort N integers in the range minus N to N, what should I do? This is a reference to yesterday's lecture. Yeah. Radix sort. Yeah, always a good answer or almost always a good answer when you have integers. It's a good answer whenever you have small integers. Now, radix sort, the way we phrased it, let me maybe put it down here. Uh radix sort sorts um n integers in the range 0 to u minus 1 uh in n plus uh n log base n of u time. And in particular, this is linear time if u is um n to some constant power. Okay? So, can I just apply this as is to these integers? No, because they're negative. So, what should I do? Maybe I should do my folding trick. We just saw how to take negative numbers and fold them in interspersed with positive numbers. If I sort that, will that work? No, because that does not preserve order. It would inter sparse It's just We want all the negative numbers come before all the positive numbers. Yeah. Can you just add n to all the numbers? Just add n. Yep. Boom. Plus n. Now we have integers in the range uh let's be careful 0 to 2n. Cool. Now we can apply this. Now u equals technically 2n plus 1 because we're only supposed to go to u minus 1. But that's fine. That's linear. And so we can sort in linear time. Easy. This is a super easy problem. Okay, but in each one we might need to do some transformation. All right, part B uh is a little more interesting. So, we have strings over 26 letters um of length at most 10 ceiling log n. Okay, this is a little trickier. What could I do? Again, I'd like to see whether radix sort applies. Um I should say radix sort sorts. I'd like to see if radix sort applies. To do that I have to map these strings into integers somehow. Any way to do that? This is easy if you understand radix sort. Yeah. Can you just index the letters in the string? Index the letters? Yeah. Yeah, we can we can map Right, so we can map A to 0, B to 1. Then what? Oh, wait, length. I mean So, it's a 26 That's for each letter. Yeah. But we have a lot of letters. There are only 26 letters, but then we have uh 10 log n letters in a string. That is together a single key that we need to sort. Yeah. Can we not sort by the first um first letter first, then from within Sort by the first letter, then the second letter. That is exactly the opposite of radix sort. Number Radix sort, we want to sort by the last letter and then the next to last letter and finally the first letter. But why not sort by the first one if you want to alphabetize things? No, to alphabetize, we do want to in the end sort by the first letter, but that's at the end. Oh, wait. So, that at the end, remember radix sort always goes backwards from the least significant to the first to the most significant. And so indeed that is what we want to do. You're just saying use radix sort. But what am I radix sorting on? Yeah, on the on the last letters, not the first letters. So, technically that would be using sort on the last letter, counting sort on the next to last letter, dot dot dot, counting sort on the first letter. Um but that is together radix sort on something or uh Jason likes to call this tuple sorting. Tuple sort is the thing is the algorithm that says sort by the last thing, then sort by the previous thing, and so on. Um you can also think of this as radix sorting on a number written in base 26. They're the same thing. Okay, but in the end we can sort in linear time. How do you ensure that the letters are sorted in order though? How do you tell the algorithm that you want A to come like Uh Just like not 0 is less than 1, A is less than B. Right. So, I mean technically when you call something like tuple sort or maybe it's even clearer when you call radix sort. Radix sort, you're giving it a bunch of numbers. So, you're taking these strings and mapping them to numbers. And when you do that, you get to decide which letter is the most significant, which is the least significant. Right? So, you you will choose to always map the first letter in your string to position a two uh um value or the the you you call it position in positional notation position uh 26 to the power 10 log n. Right? As the most significant. So, it's always most significant. Even if your string is of length one, you want to put that in the most significant digit. And you'll pad with zeros at the end if you run out of letters in your string. How many times do you run in counting sort here? How many times do I run in counting sort? Oh, 10 log n times. Oops. Yeah, good ques- good point. Uh I got confused this wrong. So, uh right. There are log n digits in the string. Uh so, that is bad. I mean it's okay. We'll end up with n log n running time by a tuple sort. However, so that's the tuple sort. So, I should really make this not equivalent. If I run tuple sort letter by letter, I'm going to do I'm running counting sort log n times, and so I get n log n cuz each one takes linear time. Um if I map my strings into numbers, first radix sort doesn't use base 26. It uses base n. And then it will only run 10 times because uh you know, 2 to the 10 log n is n to the 10. And so uh the numbers that we're sorting are between 0 and n to the 10. And so u is n to the 10, and so that's the case when radix sort runs in linear time. So, uh if you run tuple sort letter by letter, it's slow. If you run radix sort, it's doing a whole bunch of letters at once. Effectively, it's doing log n letters at a time in a single call to counting sort. And so the radix sort will actually win and get linear. There's a subtlety here, which is I'm assuming that we can actually take these strings and convert them into integers in constant time each. Um and this problem set was ambiguous, and both answers were accepted. If you assume these letters are nice and compactly stored, then uh and they fit in 10 words because a word is at least log n bits long, uh then you can actually do this. If you're store each letter in a separate word, then just reading the entire input will take n log n time. So. That's a subtlety which we don't need to worry too much about in this class. Yeah. I'm looking at something you did before like mapping the letters to numbers. So, like how would that work? Doesn't still have to be 26 Yeah, there are 26 possible letters. Numbering them 0 to 25. Um and then when we take a string like um AA, we map this into 00 in base 26. That's a number. If we do uh BB, for example, this is maps to 11 in base 26, which means uh 1 * 26 + 1. Which is 27. Okay, so that's that's the mapping that I mean. You're mapping a whole string to a The whole string to a single number. Yeah. And there's a subtlety cuz I want lexicographic, I need to pad things with spaces at the end or pad them with A's at the end in case they're shorter than 10 log n. Okay. Uh cool. That was B. C is not very interesting. It's integers in the range 0 to n squared. This I can just solve with radix sort because my radix sort at this point we've done it our third time. Radix sort, we can sort as long as uh the integers are bounded by a polynomial. Here it's fixed polynomial with constant exponent. So, this will n This is radix sort uh like we saw that just calls counting sort twice. Uh linear time. D is where things get more interesting. Let me get the phrasing same. So, D, we have rational numbers of the form w over f. This is win some win ratio. Um always in the range 0 to 1. let's say W is at most F, and zero is less than W is F is less than N squared because the That is really confusing. It's less than N squared. Sorry, separate statements. Uh because the F actually comes from part C. C is really a setup for this one. Um doesn't really matter what this means. It's just that we have numbers W and F where W is always less than F, and they're between zero and N squared. So, you should think this is a good range for me, right? That I'm representing this rational in terms of two numbers between zero and N squared, so there's like N to the fourth possible choices for what W and F are. So, the range of my values is N to the fourth. That's the setting where radix sort should run fast. Unfortunately, these numbers, what I want to sort by, is not an integer. It's a rational. And that's annoying. So, there couple of ways to solve this problem. Uh in general, good way to solve sorting is to use merge sort. Merge sort is always a good answer. It's not the best answer. In these cases, we've we shaved off a log. We got to linear time. But N log N is pretty good. It's really close to N. So, first goal might be can we even achieve N log N by a merge sort? What would I need to do in order to achieve uh apply merge sort to this instance? What does merge sort do to its keys? Sorry? Isolates It isolates and compares them. Yeah. Right. So, there's an array data structure and it indexes into the array, but that's the isolation. But then it the thing it actually does with the items themselves is always a comparison. And this is why we introduced the comparison model and proved an N log N lower bound in the comparison model because merge sort, insertion sort, and selection sort are all comparison algorithms. Radix sort is not, but this one is. But to run to apply merge sort, I need to say how do I compare W I over F I versus W J over F J. My computer only deals with integers. We can't actually represent W I over F I explicitly in in binary because it has infinitely many bits. But I can represent it implicitly by storing W I and F I. Yeah. Multiply by F I and F J. Yeah, as when I when I didn't go to school, but then we learned cross multiplication. Uh so, it's which is the same as multiplying both sides by F I and multiplying both sides by F J, as you said. So, then we get F I F J less than {question mark} uh F whatever. F I W J Uh when we do that, we better make sure that the things we're multiplying by are non-negative, otherwise the sign flips. But uh here we assume they're all non-negative. So, this is good. And now we're just multiplying two integers here, multiplying two integers here, comparing. Those are all things I can do in a word RAM. Okay. So, this was actually the intended solution when this problem was posed. Here's a way to do a comparison sort, we get N log N. But in fact, you can achieve linear time. Yeah. Uh I feel like there's a joke here. Like uh Pikachu is superior. That's always the answer. So, how do I tell whether one Pokémon is superior to the other? If I I multiply uh my I multiply I's F value with J's W value, and I see whether that's greater than uh I's W value times J's F value, and if it is, so these are equivalent. If this one is greater than this one, I know that this is greater than this. These are equivalent sentences by mathematics, by algebra. And so, uh this is what I want to know. This would say J is superior to I. And so, I determine that by actually doing this. So, then I don't have to divide and deal with real numbers cuz I don't know how. Cuz I'm a computer. We're all computers in the end. Okay. Uh So, it would be great if my numbers all had the same denominator, right? If they all had the same F, then I could just compare the W's. So, that's one intuition for why we can actually do this in linear time. Um But the the way I like to think about it, so let's just draw the real interval from zero to one, and there are various spots all over here um that represent I can't actually compute this, but conceptually each of these W I over F I's fall somewhere in that interval from zero to one. And I want to sort them somehow. Um so, one thing that would be great is if I could take these real numbers and somehow map them to integers. They're uniformly spaced. Maybe a little few more of them. Uh but these go from zero to U minus one. If I could get U relatively small, and I could map each of these So, I want the mapping to be order preserving. And I want two very close but distinct items to map to distinct keys here. I want them to map to distinct integers down here. If I could do that, then I just sort by the integers, and that's the same as sorting by the real numbers. And so, at this point I wonder how close can two of these numbers be? So, how close can two keys be? So, I want to consider W I over F I minus W J over F J in absolute value. Okay. Uh now I do algebra. Um so, this is I'd like to bring this into one ratio. So, this is I can do that by multiplying one by F I and one by F J. Um and it's W I F J minus W J F I, which should look a lot like something here. Uh but never mind. So, I'm sure there's a deep connection here. You could probably use this to prove that or vice versa. Uh Cool. So, with some absolute values, same thing. Uh maybe these are non-negative, so I can actually just put absolute values on the top part. And Okay. W I is an integer, F J is an integer, W J is an integer, F I is an integer. All greater than or equal to zero. So, this thing is an integer. So, uh it could be equal to zero. It's a non-negative integer cuz all the things are non-negative. It could be equal to zero, but if they're equal to zero, that's actually identical ratios, right? If this is zero, the whole thing is zero, and so these two values were the same. Okay, but let's suppose it's not zero. If it's not zero, it's actually at least one in absolute value because it's an integer. What about the bottom? F I So, now we want this I want to know how small this ratio can be. It's going to be small when this is small and this is big. How big could F I F J be? Well, we're told that all the F's are less than N squared. So, this thing is at most N squared N to the fourth. Less than N to the fourth. N squared minus one squared, less than N to the fourth. Uh F I is at most N squared. F J is at most N squared. So, it's N squared squared. So, this is at least one over N to the fourth. So, the the closest the two points can get here is one over N to the fourth. So, what could I do to scale that up to make them kind of like integers? Multiply by N to the fourth. So, just multiply uh by N to the fourth, and then uh floor. So, we're going to take each um F I over I'd like to compute this ratio, but I don't know how. So, instead I'm going to take F I multip- Okay. Conceptually, what I want to do is multiply by N to the fourth and take the floor. How do I actually do this? In a machine that doesn't have real numbers like this. So, I don't have a floor operation. Just have integer operations, then I can uh take F I multiply it by N to the fourth, and integer divide by W J. That is the same that computes exactly this because I can do the multiplication and the division in either order uh in real space and then this does the floor at the appropriate time. But this is just operations on integers. And now these are integers representing how good my Pokémon are. They have the property that any two distinct ones, before I take the floor, any two distinct ones are at least one apart. So after I take the floor, they will remain one apart. They will remain distinct integers. And so I have successfully mapped my real numbers to integers where distinct real numbers map to distinct integers. Yeah. Wait, so why is F I now in the denominator and W I in Did I flip them? Yeah, sorry. Uh please invert everything uh just here. This is W and F I. That was just a typo. That's all of Okay? Are they both I's or J's? Uh these should uh are supposed to both be I's, yeah. Thank you. This was for each for each Pokémon I, we're going to compute this as our key. Then we're going to sort by those integer keys and that will sort the Pokémon by the ratios. Let's try that. Pokémon for monster. Yeah. So you have U minus but U minus one. Uh so my U was just a Sorry, this is uh a label on this thing. Will that help you? Yeah. So uh now in my U, all right, what is my U? How What is my largest key? First to me, I really would like F I to be bigger than zero, but Yeah, let's not worry about it. Uh how big could U be? Well, the biggest this could be is if F I is small and this is big. Let's say F I can only go down to one, otherwise I get a division by zero. I have to deal with infinity specially. Probably the problem isn't even well defined then. Uh how big could this be? Well, I know the W I's F I defined is positive. Oh, good. Thank you. There's also a positive constraint here. Just I failed to uh to preserve that constraint in my mapping from the word problem into the formal problem. Um So F is at least one, good. But let's minimum worst case is when it's one. And when W I, how big could it be? Well, N squared minus one. So this could be basically N squared times N to the fourth divided by one, which is N to the sixth. So W I sorry, U, the largest key I can have plus one is N to the sixth. But that's okay because radix sort can handle any fixed polynomial in N. So it's going to end up doing six counting sort passes. Yeah. That's problem three. Let's move on. Four. So problem four, MIT has employed Gank Frary. Who's that? Frank Gehry, yeah. This is a common uh encoding that Jason really likes. I have I've grown to like it. Uh this is called spoonerism where you replace some some part of the beginning of your uh thing. Okay, that's one joke. There's another joke in this problem. Uh anyway, they're building a new wing of the Stata Center as one does. Uh we have a bunch of cubes. If you read long enough, you realize that's a red herring. That's cubes do not play a role in this problem. In the end, what we have is a bunch of integers which happen to be the side lengths of the cube cubes, but we just care about the side lengths, not their volume or anything. S N minus one and we want uh two numbers in S summing to H. Uh this is a side length, not the number of sides. So you have a cube. Cool, I didn't know we'd be doing 3D geometry today. S S I. Okay, so you got little cubes, you got big cubes. Okay, this is the smallest side, this is the biggest side. Doesn't matter though. They're just numbers. Okay, we're not using them at all. In the problem you're trying to like stack one cube on the other, but all we really care about is two numbers whose whose sum, regular old sum, is exactly H. Ideally, there's going to be two versions of this problem. And so the first goal is to solve this exactly in linear expected time. That's what the problem says. So what do we know? Well, linear time, that's can't get much faster than that cuz we need that just to read the input. Expected time. Hashing. Right? We're told basically we should use hashing. Now, if we're really annoying, maybe we throw that in even when you don't need it, but that's pretty rare. Uh so when we see expected, we should in a problem set setting like this. In real life, you never know what you should use, but in our in what you're learning in this class, we're going to tell you basically what tricks you're allowed to use. Here you're allowed to use randomization, so probably we need it. Indeed, you need it to achieve this bound. Uh cool. Hashing. Not obvious how to approach this problem with hashing. So I'm going to give you uh the way I It's It's hard for me to not know this algorithm, but um to me the the first thing you should think about is if if I have linear time and N things and I'm going to use hashing, the the obvious thing to do is to take those N things and put them in a hash table. Built. Why not? Uh so let's just build a hash table on all the keys in S. That's idea one. Seems like the first thing to try. So what does that let me do? It lets me I just erased the interface for hash tables, but um I can build a sequence out of it, but normally it makes gives me a set interface. So I can call find now in constant time. It lets me, given a number, determine immediately whether that number is in S. Well, that sounds interesting cuz I'm looking for two numbers in S. So let's let's we find one of them. So I call it twice. No, uh calling it twice and only spending constant time on this beautiful data structure will not give you anything useful. Um but we have linear time, right? So in addition to building a table, we could call find on that table a linear number of times cuz each find only takes constant expected amortized time. So if I do N of them, that will take linear expected time. The amortization disappears because I'm using it N times. All right, find never has amortization, so it doesn't disappear cuz it was never there. Never mind. I can afford N calls or 5 N calls to find cuz each one costs constant constant expected and the total for that will be linear time. So next idea is let's just somehow call find uh linear number of times. Okay, okay. Uh so I want to find two numbers summing to a given value H. That wasn't maybe clear, but H is given. Sorry, um how long does it take to build the hash table? How long does it take to build a hash table? It was previously on this board, linear expected time. See previous lecture. No, two lectures ago. Uh okay. Well, if we're going to do this linear number of times, I guess we should have a for loop. Let's do a for loop over the numbers. That's next idea. Loop over S. And at this point we're done, almost. Um that's space. So I want to loop over the numbers and each one I want to do a find. That's kind of all I have time to do, so seems like a natural thing to try. This This is by no means easy. Don't don't get me wrong. Having these ideas is Well, I'm explaining them as the obvious ideas, they're not obvious. But uh they are easy at least, just not obvious to come up with the easy ideas. So let's loop over S, somehow call find using our hash table. So the order is actually we're going to build the hash table, then loop, and inside the loop we're going to call find once per loop iteration. So let's do it. Let's say for uh SI in S. So, I want to find two numbers. Here I've exhaustively loop over one number. I just need to find the second number that could possibly add up, right? I want to find um whether there's an SJ in S such that SI + SJ = H. Can I do that query with find? No. So, what what does find do? Find says if I give you a key it will tell me whether like if I knew what SJ was I it would tell me whether it's in S. Yeah. Well, can you just check like H from SI and see if SJ exists? Okay, H from SI and see whether that exists. Did I get it right? H minus SI. H minus SI. This is I always get wrong. I don't feel bad that you also got it wrong. Does this feel better cuz I always get it wrong? Uh so, the claim is this. Why? Because what we want to do is find uh Well, okay. Let's write see what it says over here. So, if we do H minus SI equals SJ. Right? So, these are equivalent statements just by moving the SI over. And this is a query we can do. We don't So, let's remember these are things we know. And SJ is something we don't know. All that we know is that it's in S. Okay, so we know these two things. So, if we bring them over to the same side, we're searching for an unknown thing which is equal to exactly this thing that we can compute. So, we just compute H minus SI. We call find. That will tell us whether there's an SJ equal to this. Okay, so this is this is like a comment. All right, and then this is what we actually do. And if there is a pair of numbers summing to H, this will find it. How much time did it take? Well, we're doing N iterations of this loop. Each one we're calling a single find operation. And find costs constant expected time. And so, the total is linear expected time. Great. Part A done. Then they throw part B at us to make it harder. Those pesky instructors. So, we read part B. Part B says two things to make it harder. So, first of all, we want linear worst case time. And furthermore, so we can't use hashing anymore. Furthermore, uh so here we just needed to solve the exact problem to find whether the two numbers sum to exactly H. Now, we would like to find the best solution smaller than or equal to H. So, uh find biggest uh pairwise sum uh that's less than or equal to H if no if there's no perfect pair. Uh but we're given a little bit of extra information which is we can assume H equals 600 n to the sixth. It's a weird polynomial. Took me a while to even notice that that was a joke in here. 6006 hiding in a polynomial. All right, so polynomial, hmm. That should make you think radix sort. It is radix sort week, so that is a natural thing to try. But in general, even later in the semester when you see uh a nice polynomial with a fixed constant like this and it's somehow related to the integers we're dealing with, you should think radix sort. Especially cuz now we want constant worst case time radix sort seems like a good thing to do. Don't know what to do with it yet. In fact, I can't even apply radix sort, but idea one is radix sort. Just cuz I see that polynomial, I think maybe I should try it. Now, there's a problem here because we're given some numbers we're also some integers SIs. We're also given H. We're told now that H is a nice small polynomial, but we have no idea how big these numbers are. So, problem with this idea is that um well, SI could be bigger than H. We we have no idea how big the SIs are. Can I what can I say about SIs that are bigger than H for this problem? Summing to H. Oh, I didn't say, but all these numbers are non-negative. That's important. That looks like greater. Greater than or equal to zero. Yeah. Well, they can't be a solution because Right. If I'm finding a sum that's less than or equal to H, they're non-negative uh and any number any number that's greater than H, I can just throw away. They'll they'll never be in a solution. It's like already a sum sum of one number is bigger than H, so two is only going to get bigger if they're non-negative. Uh So, let's Idea number two is let's just throw out all the big SIs, anything bigger than H. Now, that won't change the answer because those can never be in a solution. And now I have all the SIs having the property that they're less than or equal to H. And so, they are small. Bounded by a fixed polynomial, and now I can apply radix sort. So, after this idea, I can apply this idea. Okay, this gives you a flavor of how I like to think about problems. I see clues, polynomial, I think radix sort doesn't work, but with some more ideas I can get it to work. Okay. What good is it to So, now I've sorted SI. Okay, great. S is sorted. I guess we can try to do the same algorithm except I don't have a hash table anymore. So, let's just try doing a for loop over the S. Why not? So, let's do for SI in S. But now, it's sorted, so presumably I should exploit the sorted order. So, let's do in do them in order. So, I equals 0 1 up to n minus 1. Let's say that S0 is the smallest, S1 is the next smallest, Sn minus 1 is the biggest. So, I want to do something with S. So, I have SI and I want to figure out whether H minus SI is in there. Okay. Hard to do that better than uh Actually, I could do this with binary search. Right? I know I'm looking for this value. So, I could and I have a sorted array now. So, I could binary search for H minus SI and log n time I will find whether that guy is in there. And if not, keep looping. I can keep track of the best thing that I found. And so, in n log n time I can definitely solve this. But I'd like to get linear time. Do you have a question? Well, I was just wondering how would you keep track of like why would you keep track of whether that is in there or not? That's all. I I'm not looking for SI. I'm going to compute H minus SI. So, so this is I mean, I shouldn't even write this down, but asking about the um because that's right. Uh we're not looking for H, we're looking for something small smaller than H. Or Something larger Oh, this thing. less than Right. So, in particular, if um if there are two items that sum to H, I want to find it. So, uh so, let's start with that. So, I'm binary searching for H minus SI in S. So, I can certainly do that. And um if I if I find it, great. I found a pair that sums to exactly H. If I don't find it binary search tells me not only that it's not there, but it tells me what the previous and next value are. So, even though H minus SI isn't there, I can get what the large the next largest thing and the next smallest thing. What I want is the next smallest thing. And that will be the largest sum I can get using SI. And so then, that's one candidate for a sum less than or equal to H. I want to find the largest one, so I do a for loop. I always keep track take a list of all the candidates I got. Each time I do a for iteration of this loop, I get one candidate. Then I take the largest one. Okay, so return largest candidate. Uh so, this gives me a candidate which is uh equal to the previous item. This is what we called find previous or find prev probably in our set interface. And if you have a sorted set, you can do that in log n time. So, this is an n log n solution. I want cuz we do n iterations of the loop, each binary search takes log n. I want to get linear. This is not obvious. Uh The best intuition I can think of for this next idea is well I start with the very small smallest item in S. And I want to sum up to something that's kind of big. I threw away all the items bigger than H. If I start if S 0 is like tiny like close to 0 cuz it's the smallest one, then maybe I should look at the end of the array cuz I want to compare or I want to add the smallest thing probably with the biggest thing. That's as close as I can imagine. Uh so then So here's my sorted S. This is the smallest item, biggest item. So I'm going to loop over these items one by one. So let's start by comparing the first one with the last one. The two-finger algorithm. Okay. This is the big idea. You're doing it all the time in this class. It's super useful. We saw it in merge sort for example in merging two lists. We have fingers in two lists that advance and because they only advance it take linear total time. So we're going to do this kind of folded and backwards here. We're going to start here. This seems like a good candidate to start with. Now what else could this add with? Uh well, maybe smaller items. And maybe I have to go all the way through here and then I've got to advance my left finger. Yeah, okay. So uh There's the idea. So um let's look at So I'm going to call this finger I this finger J. So we want to sum two things. So I guess another inspiration here is we want to add two things up and we have one algorithm that has the word two in it and it's the two-finger algorithm. So let's try that. Um so we're going to start with I equals 0 and J equals n minus 1. We're going to look at S I plus S J and see how good it is at how close to summing to H is it. Well, in particular it's either uh less than or equal to H or bigger than H. If it's bigger than H, so this sum is too big. I can't even use it as a candidate. Well, that means I really don't need this guy, right? It's too big overall. This was I'm adding the smallest item to this item and it's too big. Well, then I should go to the left. I should move my right finger to the left. So in this case uh we decrement J. Move the right finger to the left. So I'm guessing in this case I'm going to increment I. Why? Um if I add these two items up and this is too small smaller than H, then this item was probably too small. It might actually it's an okay solution. It's less than or equal to H. So I should keep it as a candidate. Um Let's say add candidate. So I'm just going to keep a list of candidates that I see. So this is a possible solution. Might not be the best one, but it's one to add to my list. And then I'm going to increase I and now work with on this sub array um cuz that will be a little bit bigger. I can't go this way to make it bigger cuz I'm at the last item. And it's not obvious that this works. I think there's a nice invariant that will help. Uh Somewhere I got to put my piece of paper. Yeah. So here's an invariant. Uh Oh. Yes. It's really clear this is the right thing to do in the first step and the tricky part is to argue that it works in all steps. Cuz when I really have the smallest item and the small and the largest item, it's clear that I should advance one or the other. I'm too small and too big. But the way to prove it in general by induction is to show this invariant that so at in some point through this execution I and J are somewhere and I want to say that if I take any J from the right any J prime to the right of J and then the I prime to the left of I non-strictly then all of those pairs all those pairwise sums are either too big and that's when we decrease J or they're less than or equal to the largest candidate that we've seen so far. Um that's because we add these candidates in there. So this that invariant will hold by induction cuz whenever there's a possible thing that's good, I add it to my candidate list. And then at the end of the algorithm I just loop through my candidate list, compute the max, return that pair. Okay. So that is two-finger algorithm which solves the non-exact problem in linear worst-case time. Yeah. I cannot equal J. Oh, I cannot right. So what are the termination conditions? When I equals J, that's probably when you want to stop. It depends. You could say if I is greater than J, stop. Uh return max candidate. Uh it's There are two ways to interpret this problem. One is that the the two values you choose in S need to be different values or you allow them to be the same value. Like they can both be H over 2. And either way is easy to solve. If you if you want to allow S over 2, then I would put greater than here. If you don't want to allow uh S over S H over 2, then I would put greater than or equal to. Either way. Both both of these problems you can solve both ways or both algorithms can handle both situations. Okay. One more problem. All right. Yeah. A lot of time. But I'm getting faster and faster. So of course on the hardest problem I can do it the fastest. All right. So Jeff So sorry. Meth Jaw. This is a reference to Jeff Ma of the MIT Blackjack team who I got to see speak here at LSE a bunch of years ago, but he's featured in the movie 21 and so on. Fictionalized. Um So I was playing this game. It's great great great set up. You should definitely read this problem. Uh p o k e r. Um And he has a deck of cards where each card has a letter of the alphabet on it. I guess this the right way up. So I of course have such a deck. This doesn't everyone? You can buy these. I have several actually. Um and so we can do a quick magic trick like pick a card any card here. Pick a card. Here. Yes. I can't Oh, good choice. I I can't force so it doesn't really matter. Okay. And uh so this is your card. Right? And your card is an S, right? Okay, good. Okay. No, not all the cards are S's. But he has mirrors in his glasses. No. Uh I'll reveal later how it's done. Um Okay. So a deck of cards each card has 26 possible letters on it. And uh there's this weird dealing process. Even just defining this problem is going to take a little while. Oh, here's my piece of paper. Uh So we have this dealing process. Here's an example. It's in the problem. A B C Sorry. D B C. So that you know the order of the cards. This is the top card. This is the bottom card. And now randomly you do a cut. Cut is this. All right. So I take some chunk off the top, move it to the bottom. Once randomly. So for example, I could take this cut and then uh what I would get is C D B C for for this part that's copied here and A B. That's the So this is So first thing we do is cut at I. This is position I. This example I equals 2. Okay. Then we deal the top K cards. So uh let's say we deal the top four cards. K equals 4. So this is uh deal K. Uh so we get C D B C in that order, but the order doesn't matter because the last operation we do in the problem is sort them. Which is B C C D. Okay. Like you do when you get a hand of cards you tend to sort them. Okay. So this is a process given a deck. So the deck here is fixed. Uh we call this process uh I think P of D {comma} I {comma} K. We're told what D is. We're told what K is. I is chosen randomly. And we'd like to know what happens with different I's. Um So So if you stare at this problem enough, it begins to simplify. So, this is a complicated setup, but what's really going on is we're starting at position I, and then we're taking the next K cards from there cyclically. So, here we just took those four. If I would equal three, we would deal D, then B, then C, then A, but then we sort them. Okay, so we're getting different substrings of length K cyclically, but then we're sorting those letters. Sorting is really crucial for this problem to have all be feasible. Um and it took me a while even to to see how to solve this problem, but the key is sorting. That they get sorted because that means because we sort, it doesn't matter whether you have A A B A or B A A A or A B A A, these are all the same. Uh if you take these cards dealt, you sort them to the same thing, which is the one I didn't write, A A A B. All of these get sorted to the same thing. So, we lost some information when we sort. Lost the order. The first question to get you thinking in this direction, part A, says, "Build a data structure given D and K that lets you lets me know, given two indices I and J, do I end up with the exact same hand?" This thing is called a hand. And it's exactly this P D I K. So, I want to do P D I K and P D J K, and I want to know J K, and I want to know whether those two things are equal in constant time. That's what this says. Constant time. Doesn't say worst case, but worst case is possible. Uh and that sounds hard because I mean there's K symbols for one of them, another K symbols for the other guy, but we don't have to compare the symbols. We just need to compare the sorting of those strings, and this we can compress. So, this is a subtlety, but what I really need to know is that there are three A's here and one B and zero C's and zero D's and zero E's and so on. But because there's only 26 letters in this deck, and indeed in this deck happens to have upper and lower case A through Z, but we might have N cards, but there are only 26 possible labels. So, in fact, a lot of them are going to be equal if N is large. So, this is a good compression scheme cuz I to represent the things I get after sorting, I just need to give you 26 numbers. For us, 26 is small cuz 26 is a constant, independent of the number of cards. I just need to say how many A's are there, could be anywhere between zero and N. How many B's are there between zero and N. How many C's are there between zero and N. So, 26 numbers in the range zero to N. I like to think of this as a 26 digit number base N plus one. Uh we can map this into base N plus one uh and we get 26 digits in that base. Another way to say it is that the number of possible uh combinations here of how many A's, how many B's, how many C's is um not even theta, it is N plus one, anything between zero and N, uh to the power 26. This is a good polynomial. So, I can do stuff like radix sort. Uh Cool. So, let me summarize a little bit how we solved part A. So, I want to build a data structure which is for each value I, I know I'm going to end up serving these four cards or in general K cards. So, for those cards, I would like to compute um how many A's, how many B's, how many C's are there, and then just write down this number. This is a number which I can write down in at most 26 words um cuz we're can represent numbers between zero and N in a single word. That's the W is at least log N assumption. Uh so, it's constant size. In a constant number of numbers, I can represent all I need to know about a thing of size of length K here. Cuz I don't need to know the individual which letter is where, just need to know the sorted order. So, I just need to know this is called a frequency table. How many A's, how many B's. And so, if I can compute those, then given that representation for starting at I, and given that representation for starting at J, say, which would be these two and these two, um I can compare them by just comparing those 26 numbers. If they're all equal, then they're the same string after sorting, and if there's any difference, then they're different. So, that's how I could do it in constant time if I can compute these representations. And it's not hard to do that. You it's called a sliding window technique where you compute it for the first K guys, and then you remove this item and add this item into just by incrementing the counter for B, decrementing the counter for A. Now I know this the representation for these guys, make a copy of that, which is a copy of those 26 numbers, constant. Then I add on C, remove B, then I add on A, remove C, then I add on B, remove D, add on C, remove B, then add on D and remove C. Well, I got back to the beginning. So, now I have representation of those. Okay, so I by sliding this window, I'm only changing at the two ends. I add one guy on, I increment one of these counters, I decrement one of these counters. So, in constant time, uh given the representation of one of these substrings, I can compute the representation of the next one. And that's how I in linear time can build such a data structure that lets me tell whether any two hands are equal. The next problem, part B, is given all these representations, uh can you find which one is the most common? Cuz we're choosing I uniformly at random, I want to know what the most likely hand that you get is. And I think the easiest way to say this is you can do that by radix sorting. You take all these representations, they are nice numbers in the range zero to N plus one to the 26 power. So, I can just run radix sort and sort them all. And then do with a single scan through the array, I can see which one is the most common. Or rather, I can in a single scan, I can compute, okay, how many of the same things are at the front? They're sorted, then all the equal ones will be together. So, how many are there? Then how many equal ones next? And how many equal ones are next? Each time comparing each item to the previous one. Then I get frequency counts for all of these uh hands, and then I do another scan to find the most common one. And I can do another scan to find the lexically best one and the most lexically last one. And that's how you solve problem five.