Design and Analysis of Algorithms 5. In year 2264 the twenty-third starship came
ID: 3742784 • Letter: D
Question
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.5Explanation / Answer
Answering the question from the beginning
Background knowledge: Stack and Queue and abstract data structures which were made to implement certain functions quickly. Stack works on the principle of Last In First Out (LIFO) and Queue works on the principle of First In First Out (FIFO).
(a). Worst case running time of enqueue function - This uses in_stack.push(value), which is constant time. Whenever we push an element in the stack, the pointer which is pointing to the last element which was inserted, increments it's value by one and then adds the new value in the stack. Hence, in Big-Oh notation, it is O(1) - constant time.
Enqueue: function()
//this value points to the last value inserted in the stack
top++;
// create a new Node and enter the newValue
newNode = newNode.insert(newValue);
top = newNode;
(b). 2n enqueue operations is going to take O(n) time, since a single enqueue operation takes O(1) time even when the 2n enqueue and n dequeue operations are done in the worst case order.
The worst case possible order in the case of dequeue will also take O(n) time when all the enqueue operations are done first and then the dequeue operation is done. In this case, all the values will pop from the in_stack and go to the out_stack before returning the value.
(c). The most number of operations are for n^2 atRank which means in order to reduce the time taken for this operation, we need random-accessibility. It can be achieved only through array-based ADT. For the remove and insertAt operations, in the array it is going to be O(n) time complexity since for every insertAt or remove operation, the remaining values will need to be shifted to the right and left respectively.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.