in this week's homework you're going to experiment with amortized analysis using the double ended q problem as an example i'm going to give you an alternative implementation of a double ended queue it works but the performance isn't great your job is to simply change one method to improve the performance when it starts off you're going to get a typical sort of quadratic style performance let me just show you when you run this thing it works just fine but i'm going to do a doubling test here starting with 4 000 elements then 8 000 elements and i'm going to get some pretty dreadful numbers in this case i'm doing a video export in the background on my laptop so the numbers are particularly bad but i've got about four times the work for double the input so characteristic of a quadratic algorithm this is what i got when i ran it without the video export going on in the background so your goal is to transform this algorithm from one which is quadratic time for in operations to one that's linear time for in operations of course the output that you're going to get will have noise in it from systems effects and things like that but you should see this basic improvement in the performance and you should see this general convergence toward doubling the time for doubling the size of the input so let's look at the problem the problem here is to implement a double ended queue and if you think about it it's quite straightforward to do this using two stacks what i'm going to do is put one stack on my left that's my left stack one stack on my right that's my right stack and i can then push from the left onto the left stack push from the right onto the right stack that's pretty great um is empty well are they both empty what's the size it's just the sum of the sizes of the two stacks this is obviously correct as long as i pop all the things from the left hand side that i pushed on the left hand side and similarly on the right it gets trickier to know what's going on in the case that i mix pushes on one side with the other side the idea of this algorithm is to think of the two stacks as being opposed to each other so what i'll do is i'll let's suppose i push on my left stack i'll push one and then two and then three now if i want to pop from the right of course the number that i should get on the right is one well unfortunately that's at the bottom of my left stack how can i get it out well a simple idea is to simply push everything from the left stack over to the right stack at that point my left stack is empty and i can simply take the top element of the right stack yeah that's great how much work did i do well it took time proportional to the number of elements that happened to be here right now so this is the idea of the implementation of the double-ended queue using stacks the key method for accomplishing this is called move and what move does is it takes all of the elements from one stack and puts them on the other so we have a from stack and a two stack and we're simply going to take all of the elements on the from stack pop them off and push them onto the two stack we can use the move method then to implement pop pop left we'll check to see if the left stack is empty if it is we just move everything from right to left and then pop symmetrically when we pop right we just look to see if the right stack is empty if it is we move everything from the left and then pop to understand the worst case complexity of this approach we need to understand the worst thing that could happen if i start off with all of my elements on one side and then try to access them from the other well i'll have to move everything to the other side and in general the worst thing that can happen is to alternate from one side to the other so moving everything from left to right then right to left etc let's just look at an example of that so if i have one two three on the left and then i want to pop from the right well i need to move all of those things over so i'll end up with three two 1 and then an empty stack at this point i can pop the element but let's suppose then i try to get from the left hand side which is now empty well i have to move everything over so i'll put the 2 and then the 3 then i can actually pop from the left at this point my right hand side is empty so if i want to get from the right i have to move everything over and then i can pop it from the right and you can see going back and forth what's happening is that at each iteration the size of the remaining elements is decreasing by one and if we start within elements we'll start off with in then in minus one then n minus two etc down to 0 or 1 and you can see that that sum is a familiar sum it's the triangular sum which is giving us a quadratic total the test that i've written is testing precisely this load on the data structure let's just look at the main method real quick and the tests in it so the main method here has a correctness test which should be sufficient to ensure that you do not disrupt the functionality of the data structure by improving the performance of the move method and then it has a performance test the performance test is going to uh do this time trial repeatedly here the time trial is pushing two to the n elements on to the left and then popping them by alternating right left right left right left so this is precisely the worst case load for this algorithm that i've given you so how are you going to make it work better how are you going to get this to work in linear time well the key to realizing this is to note that we're moving too much stuff we're just doing too much moving so in particular the problem here is that i'm moving everything from one stack to the other wouldn't it be nice if instead of moving everything i just moved like half the things so that would mean that instead of moving three two and one over here let's say i just would move one over here and that means that 2 and 3 would have stayed behind if you can achieve something like this it would be a lot better but note that that's difficult to do directly with a stack because in a stack i can't just take the bottom element off what have i got to do well i've got to somehow take off these top elements first then i can move the bottom element and then perhaps put these things back where they were so overall that sounds like i'm doing more work not less but this is the funny thing about amortized analysis by doing more work in one method i may improve the performance overall so this is the area you need to explore unlike previous homework assignments there's not a huge amount of code to write here this is mostly a thought experiment you'll find that you don't need to do very much the the answer here will be three or four lines of code at max i've written out what you need to do you need to make it perform better and i've given you a little bit of a hint here which is that you can use a temporary stack to help you do this i've also said maybe you need to do some debugging while you're getting things to work you could uncomment these print messages you might add more print messages in here if you're going to be printing and debugging you'll probably want to comment out the performance test so that you can just zero in on correctness to begin with and then try to get the performance back good luck with the homework