Video 2-2: §2.2 Resizable arrays

0:00 <Untitled Chapter 1>

0:02 In the next little subsection, I want to talk about resizable arrays. A simple trick um to get arrays that can to the outside world appear to change the size. Um under the hood, they don't. It's uh an amortization trick how you can create new space when you need it. I suppose many of you have seen this, so I'll go over this a bit more quickly. Um, one little comment is you can see an array as an abstract data type where the operations are create me one of size n and I can get and set uh certain cells at the index i. So of course um most programming languages have special syntax for specifying this because you use arrays all the time. Um but that's that's the usual way how arrays work. Now, I would still say an array is usually not seen as an abstract data type, but rather as a fixed specific data structure um because I don't know of a a programming language that uses arrays for anything other than a contiguous piece of memory.

1:10 But maybe it's sometimes useful to think about these operations specifically. Um that is what makes an array really. Now how can we do uh a stack of unbounded size with arrays of fixed size? We have to somehow uh allocate new arrays obviously and uh we can do this as follows. This was the invariance for maintaining a stack in an array. We have an array S and uh it was it was drawn like this, right? you remember just a couple of slides back and it had a certain capacity C and we had a pointer to where is the stack currently. So point top would essentially u store the index of the topmost used element. Now the new thing is that we insist that at any point in time uh this capacity is sandwiching the number of elements in this way. N must be at most the capacity well we have to store the elements and we also want that the capacity is not um is not four times bigger than n. So we don't want an overly um large array if there's not also uh many elements.

2:36 If we can maintain this invariant at any point in time, it means we can always add more elements uh because the capacity grows with the number of elements. But uh what I haven't told you so far is how we can maintain this invariant. And the a conventional easy way to do it is as follows. Before we push a new element, we check if we've reached the current capacity. And if so, we allocate a new array of twice the size of the current size. And we copy over all elements. So that was the current capacity C. Now we double it and we make sure that this lower part is copied over from here. That's quite expensive but uh we'll see that it pays off in that whenever we have this expensive operations there's many cheap operations after that.

2:51 Doubling trick

3:33 The same thing if we remove an element and that brings us below our capacity bound. We do the very same thing. Interestingly we allocate a new array of twice the size of the current stack and copy all elements. Uh and that's it. It's simple to simple to implement and program. Um, but I want to make sure that you understand what this is about. So, uh, let's do this little question. Uh, which of the following statements is true about a resizable array uh, when it currently stores n elements?

3:52 Clicker Question

4:22 And again, read very very carefully. There's nitpicks in the formulation. What I mean by nitpicks is uh pick the statements that are always true. um not those that sound just reasonable but those that are really clearly true.

4:52 In a sense this question is my my way to see have they seen resizing arrays? Yes. But have they seen it and totally internalized it? Uh that's that's what this question gets at and uh from from a theoretical perspective if you like.

5:46 Okay, I think most people have voted. So, let's see what he came up with. and I'll show you my my answer and want to briefly tell you a little bit about why I think the others are not as true as I would like them for this question. Oops, that was not what I wanted. Um um okay. I didn't want to reveal the answer right here before we do the analysis, but because most people have seen this, maybe I'll do this anyway. Um I think this is the the correct statement and uh I'll justify the statement for you in a minute. Um the first statement is not really true because the number of elements that are currently stored that might fluctuate up and down and uh it's not always exactly 2n nitpick. As I said adding and deleting an element at the end takes constant time. So here the nitpick is if I say constant time this means worst case constant time. If if there's no other qualifier you have to assume it's worst case. And that's not true because in a resizable array if we have to resize it's expensive takes linear time as we'll discuss.

7:11 H and the last point is inserting and deleting any element takes order to one amortized time. If this was combined with the second answer it would be true. The last element can be deleted in amortized constant time. I cannot take out any element in the entire array. I would have to shift the rest over. Okay, that was maybe a bit of a mean question, but I wanted to see if you can follow along with this. Uh, but let's let's briefly do this amortized analysis of the resizing arrays because amortized analysis will come up later in in the class in a more complicated setting. So, it's useful to get this uh sorted once and for all here in in this simple setup that is probably familiar to you guys. Okay, what is what is amortized analysis about? Um, it's a it's a common term in in algorithms and data structures. So, um, definitely you should be able to recognize what it means. Uh, it's the concept that any individual operation in our sense of the um array implemented with res sorry in the stack implemented with resizable arrays. Any individual execution of push and pop can be very expensive. if we have to copy the elements to the new array at precisely that time.

7:43 Amortized Analysis

8:36 Uh but the observation is because we always double the array right away, we create enough empty space so that one expensive operation pays for a lot of the future operations to be cheap. So that if you average them out, uh each is cheap on average. That's what amortization um means. And um in our case uh we have um the there's a a widely used there's there's different proof techniques and templates that you can use to prove amortized bounds. I will focus on the one that I find most versatile. It's maybe not the most intuitive one but it's the one that uh that works for all the problems that we will encounter. So I I want to introduce the general uh top the general version here right away and the idea is uh we define a potential function and that's some magic definition that you have to come up with. Uh so uh this is reminiscent a little bit about the loop invariant. You have a proof template that's fairly simple but you have a a creative step where you have to understand the problem to see what you have to fill in. um for this for this step and that was the loop invariance and here it's here's the potential function.

9:59 Okay. Um let's look at what the um what the the proof template works like. It defines an amortized cost for an operation which is the actual cost and in this case minus2 times the change in this potential. And this two is a is a constant that you usually work out after the fact when you've done the analysis you find that two is the right word is the right constant in this case and so that's that's what you use. Um for other applications it might be um that you need a different constant.

10:44 Okay. Uh but that's that's a definition. Now let's look at what happens with push and pop. If we have a cheap operation that means there is space in the array. The actual cost is just one array access. So by cost here we count the number of array accesses that is um again a quick comment from the off. uh we used to talk in the last in the previous unit we talked about uh elementary operations the dominating operations um for a certain task and here um for this for this simple application of a resizing array how often do I access read or write a cell in the array that's what we pick as an elementary operation so our cost is the number of these array accesses a cheap push and pop has exactly one of these array accesses That's the actual cost but the uh amortized cost has to add the change in potential and um here if you look at this uh potential now I should give you a little bit of an intuition um there's the the bounds of 14 C and C and N can be anywhere in this range. So n could be here and n can move up and down via push and pops. So it can it can wiggle around here.

12:16 And what this potential function does the fi is just the distance to the closest boundary. And in this case we're um we're getting closer to the lower bound. So uh in this case fi is this distance. If n moves further up it becomes this distance. Now if you do a cheap push or pop that means you move around with one inside this range. You're not at the boundary. So you go from here either to here or to here. If you go away from the boundary, you actually gain a credit. But we can't really uh use that because um what we have to say here about the amortized cost has to be true in in every case. If you move closer to the boundary, you lose one credit, which I mean by which I mean uh you lose one in five. And because we doubled that, the amortized cost is three of such an operation. That's at most three. It can be one if you really move away from the boundary.

13:36 But that's the the worst case. If you have one of these expensive operations, uh say a push. So that's the situation where your n reached the capacity and you have to double the array. Um then you have to copy the n elements from the previous array to the new. So that means n times you read and n times you write an array cell uh plus the new element that you add in. So that's the 2 n + one array accesses for the expensive push.

14:14 But it creates n credits in um in the potential function. Well, I would say that's actually n minus one, right? Uh if we're strict. So the amortized cost is is two. Uh I think I just forgot that we also add one element at the same time. Might be the same here. If you add those two up, you multiply this by two and you add those two up, then you have the 2n cancels with that 2n and then it's + one minus 2. Um, it's actually three. Is that right?

15:03 Let's do the calculation in slow-mo to not screw it up. No, I was I was right. It's uh it's more expensive and it's three because I I didn't double this. So that's uh the two end cancels and here we have the minus.

15:28 All right. So it works out to three. Um if you have the copying pop that's similar but now you reach the the lower range of your capacity then again you have to copy elements. Um I think I screwed this one up badly. I think you also have two n + one copies because n is the current size. And um but you only get half n credits.

16:09 So this is the case where you notice that your constant here was not big enough. Uh we have to change this to four. Otherwise this doesn't work out. we need that the uh the factor here is big enough to cancel the actual cost. Now if if we add the four here that will change the amortized cost of these operations but it will only uh will only increase the constants. So this goes up to five. And uh here again we have the four + 1. So that goes up to five. And then um similarly here, but let's do it in slow-mo again. Um - 4 * the 12 n -1. So those cancel and then we have 1 + 4. So this is also five. Sorry for that confusion. Uh I should have caught that mistake earlier. I'll I'll fix the slides, but I think it it was also insightful for you to see how these proofs are usually constructed.

17:21 You start out with a constant here and and see if it was big enough. And if not, you make it a little bigger. And usually um either it works then or you keep increasing the constant, which means uh your proof is is flawed and something's wrong.

17:42 Okay, let's um I'll erase the uh site calculations. We have shown that in each of the cases we have an amortized cost of five. Now what does that mean for a sequence of m operations? The total cost of that is uh at most this so this is something I want to show. If we say I AI is the amortized cost for the E operation. So that's the actual cost plus the change in the potential. Um in our case we say it's minus4 and then the new potential minus the old potential.

18:25 So by this fi I just mean the potential after step I. Now we want a bound on the total actual cost but what we have is that um our amortized cost is at most five for all the operations.

18:47 So what we can say is if we sum up the amortized costs for m sequence for for a sequence of m operations that's at most 5 m.

19:01 Uh but we also know that this sum is telescoping in the sense that if you insert the definition you get the sum over all the CIS and then we have minus4 and then this sum where well let me write it down but uh you can probably see this uh in this in this sum there's always one term that cancels the contribution from the previous one. So the the only thing that remains from this is the total actual cost and then we have minus4 and what remains from this sum uh what's not canceled is the last term the fm and we have a minus uh f0 at the beginning the initial um the initial potential and all the other terms in the middle cancel. And now we have a nice um a nice inequality uh where you can solve for the total cost of the the total actual cost and you just bring this to the other side. So the total actual cost is the total is the sum of the advertised costs that's 5 m and then uh we have to add the four and uh subtract the four by zero.

20:48 Uh but we can drop the this is um this is always just making it smaller. So we can as an upper bound do the four 5mm and uh so here another little mistake uh we get about the total cost that's the total cost sum of the CI is at most the total amortized cost which is 5 * m uh plus the final credits that's 5 m. Now let's see how we can fix that part. The total amortized cost was 5 m and uh okay I switched between N and M. Um let's let's keep it with N.

21:37 Uh okay let's M M operations. So I should have I should have written an should have written M here all the way. Uh how big can the final credits be? Um the phi is always at most uh half n. So that part's correct. But we increase that constant to four. And uh sorry this was a lot of a lot of corrections Okay, that was a lot of work. But finally we've shown this bound and that of course is theta of n + m um which is the result we claimed here.

22:33 So um to wrap this up if you have a resizing array and any number of operations m and the final size n uh the total cost will be bounded in this in this way. um the total cost is n plus m and if you start with an empty array the final size will never be bigger than m. So it's it's linear in the number of operations which means each individual operation on average can only cost a constant time. That was amvertised analysis of resizing arrays. Um, that's probably a good point to check if uh if you have any questions about this part. Um, again, I apologize for the for the confusion on the slides.

23:33 Well, if if questions arise later, we can address them then. Um if not uh I'd like to conclude this part with uh cues which are like the uh the the sister of stacks. They're um like uh if you if you have to queue for getting into some shop you can inq at the end hopefully only there if it's a fair queue and uh dq at the front. So you add new people here that's in Q and you DQ at the front by taking the first person off and allowing them into the store. Implementation wise it's exactly the same as for stacks. You can use linked lists and you can use arrays. Um you have to be a little bit more careful because of the two ends but it's um it's it's not really a big difference for a fixed size array. you have to deal with the the wraparounds in the queue. But you you might have seen this before and if not it's not relevant for our class.

24:43 Um and a final a final abstract data type that I want to mention is that of a bag. Um and it it comes from the question what do you what do stacks and cues have in common? Um they're essentially special cases of just a collection. So this is um also the Java name. It's roughly roughly the same as a bag. Um a collection is just anything you can put items in and you can get items out. And uh I called this here delete any because you don't really have control over which item you get. You just remove any of the items in the back.

25:19 Um is sometimes useful. It's not it's not that you can implement a back more efficiently than a stack or a queue. It's just sometimes useful to specify. I don't care about the order. Use whatever is convenient for you.

25:38 And um yeah, that concludes the part of the very elementary basic data structures. explicitly um I made this a bit longer than necessary because of the amortized analysis that we will uh reuse for different algorithms.