Create a PDF with your solutions to the following problems. You may scan handwritten pages, or create a digital document with LaTeX or a word processor. Your math should be formatted with TeX math mode or an equation editor.

Please Read !!!!!!! and answer the question

1. Consider a superstack data structure which supports four operations: Create, Push, Pop, and MultiPop. The new MultiPop operation is given a non-negative integer k and array A, pops the top K elements, and stores them in A. MultiPop throws an exception if k is greater than the number of elements on the stack, or the size of A. All four operations are implemented using an underlying standard stack as shown below.

SS_Create(): S = Stack.Create() SS_Push(x): S.Push(x) SS_Pop(): return S.pop() SS_MultiPop(k, A): if (k > S.Size()) or (k > A.Size()): throw exception for (i = 0; i < k; i++) A[i] = S.pop()

Argue that each of these operations takes O(1) amortized time. Your argument should

• define a potential function , and
• state, for each operation, the operation's actual time, change in potential, and amortized time.

2. Download Queue

Design a data structure for managing a download queue, such as the ones used in web browsers like Firefox and Chrome. These queues work like a standard FIFO queue, but with two differences. First, browsers can download up to three files at a time, so the queue supports an operation to peek at the first three elements of the queue. Second, the queue prevents duplicate downloads. If an URL is already in the queue, it cannot be enqueued again. Design a dqueue (download queue) that supports the following operations.

// Initialize an empty dqueue. DQUEUE_INIT() // Enqueue URL u at the end of the queue, unless u is already // present in the queue. DQUEUE_ADD(u) // Return the number of elements currently in the queue. DQUEUE_SIZE() // Return a list of the first three elements at the front of // the queue. If the queue currently contains fewer than three // elements, return the entire contents of the queue. DQUEUE_PEEK3() // Remove and return the element at the front of the queue. DQUEUE_POP()

Design a data structure that implements all these operations. Write clear pseudocode that shows how each operation works. You should build upon the data structures we have already covered in class. Aim to have each operation run in O(1) time (worst-case, expected, or amortized).

Please Read !!!!!!! and answer the question