Analysis of Algorithms

 1. Describe how one can implement each of the following operations on an array so that the time it takes does not depend on the array’s size n. a. Delete the ith element of an array (1 ≤ i ≤ n).

 b. Delete the ith element of a sorted array (the remaining array has to stay sorted, of course). 

2. If you have to solve the searching problem for a list of n numbers, how can you take advantage of the fact that the list is known to be sorted? Give separate answers for

 a. lists represented as arrays.

 b. lists represented as linked lists.

 3. a. Show the stack after each operation of the following sequence that starts with the empty stack: push(a), push(b), pop, push(c), push(d), pop

 b. Show the queue after each operation of the following sequence that starts with the empty queue: enqueue(a), enqueue(b), dequeue, enqueue(c), enqueue(d), dequeue