Design and Analysis of Algorithms

5. In year 2264 the twenty-third starship came off the assembly lines at NASA. This starship was called the USS Enterprise. Unfortunately, the core libraries of the Enterprise were corrupted during an exploration mission. The only uncorrupted data structure left was a simple stack. A team of engineers set out to reimplement all other data structures in terms of stacks, and they started out with queues (a) (5 points) The following are parts of their original implementation of queue using two stacks (in stack and out_stack). Analyze the worst-case running times of its enqueue and dequeue methods, and express them using "Big-Oh" notation 1: function ENQUEUE(o 2: nstack.push(o) 4: function DeQUEUEO 5 while not in stack.isEmpty do 6 out stack.push(in stack.pop)) 7: out stack.isEmpty then throw QueueEmptyException 9 return.objout stack.pop) 10 hile not out stack.isEmpty) do in stack.push(out stack.pop)) 12: return return.obj (b) (5 points) Later in the 23rd century, a new chief engineering officer named Montgomery Scott took over. He set out to optimize the old code. Thus a new implementation of a queue (still using two stacks) was born. What is the worst-case total running time of performing a series of 2n enqueue operations and n dequeue operations in an unspecified order? Express this using "Big-Oh" notation. Hint: Try using techniques presented in section 1.5