**1a.**Suppose that a client performs an intermixed sequence of (stack) push and pop operations.The push operations put the integers 0 through 9 in order onto the stack ; the pop operations print out return values.Which of the following sequence(s) could not occur?

a.4 3 2 1 0 9 8 7 6 5

b.4 6 8 7 5 3 2 9 0 1

c.2 5 6 7 4 8 9 3 1 0

d.4 3 2 1 0 5 6 7 8 9

e.1 2 3 4 5 6 9 8 7 0

f.0 4 6 5 3 8 1 7 2 9

g.1 4 7 9 8 6 5 3 0 2

h.2 1 4 3 6 5 8 7 9 0

**b.**Suppose that a client performs an intermixed sequence of (queue) enqueue and dequeue operations.The enqueue operations put the integers 0 through 9 in order onto the queue;the dequeue operations print out the return value which of the following sequence(s) could not occur?

a.0 1 2 3 4 5 6 7 8 9

b.4 6 8 7 5 3 2 9 0 1

c.2 5 6 7 4 8 9 3 1 0

d.4 3 2 1 0 5 6 7 8 9

**2.** Show the various steps of Insertion-Sort, Merge-Sort and Quick-Sort on the example array, {5, 7, 0, 3, 4, 2, 6, 1}. For Quick-Sort, assume that the first element of the array is picked as pivot.

**3.** In any array A, an inversion is a pair of entries that are out of order in A. That is, an inversion is a pair (i, j) such that i < j and A[i] > A[j]. Develop a algorithm for computing the number of inversions in a given array. The running time of your algorithm should be O(n + k) where k is the number of inversions in the input array.

**4.** Consider an implementation of a stack using an extendible array. That is, instead of giving up with a “StackFullException” when the stack becomes full, we replace the current array S of size N with a larger one of size f(N) and continue processing the push operations. Suppose that we are given two possible choices to increase the size of the array: (1)f(N) = N + c (for convenience, we start with an initial array of size 0) (2) f(N) = 2N (we start with an initial array of size 1). Compare the two strategies and decide which one is better. To analyse the two choices, assume the following cost model: A “regular” push operation costs one unit of time. A “special” push operation, when the current stack is full, costs f(N) + N + 1 units of time. That is, we assume a cost of f(N) units to create the new array, N units of time to copy the N elements and one unit of time to copy the new element.

**5.**The span si of a stock’s price on a certain day i is the maximum number of consecutive days (up to and including the current day) that the price of the stock has been less than or equal to its price on day i. You are given as input an array P of size n containing numbers such that P[i] is the price of the stock on day i. Your goal is to output an array S of size n such that S[i] is the span of the stock on day i.

Observe that the naive algorithm for this problem runs in time O(n²). Show how to use a stack to design an algorithm to compute the span in O(n) time. Describe your algorithm using pseudo-code and explain why its running time is O(n).

## Reviews

There are no reviews yet.