CS 261, Spring 2013 Homework 1, due at the start of class on Tuesday, April 16 1. Suppose that we want to maintain collections of items, and support the following operations: - report the number n of items in the collection - add an item to the collection - report the i'th item in the collection, for an argument i with 0 <= i < n - remove the i'th item from the collection, for an argument i with 0 <= i < n The ordering of the items in the collection is arbitrary, and is allowed to change after an addition or removal (for example item that was the 3rd item in a collection prior to removing something else may become the 5th item in the collection afterwards) as long as each index from 0 to n-1 is associated with a unique item. Describe how to use one or more arraylists to implement each of these operations. For the purposes of this problem, an arraylist can only perform the following operations: - set the item at position i of the arraylist - get the item at position i - find the length of the arraylist - increase the length of the arraylist by one - decrease the length of the arraylist by one. Each of the operations of your collection data structure should translate into a a constant number of the arraylist operations. Your answer should include both a description of how the collection is represented, and how the collection operations are to be performed. You may use either pseudocode or English text to describe how to perform each collection operation. 2. Suppose that we maintain a binary counter as described in class, but with a decrement operation as well as the increment operation that was described. The decrement operation should be the opposite of the increment operation, in that it subtracts one from the binary value stored in this counter. (a) Describe how to perform the decrement operation in time proportional to the amount of information within the counter that gets changed by the operation. (b) Does the data structure with both increment and decrement operations still take constant amortized time per operation? If so, provide a potential function for which the amortized time is constant, and explain why it is constant. If not, explain why there does not exist a suitable potential function. 3. A stack data structure can be implemented by an arraylist (as described in class), but it can also be implemented by a collection of "stack node" objects, each of which has a "value" pointer and a "next" pointer, as follows: def push(stack s, value x): create a new stack node object q q.value = x q.next = s.top s.top = q def pop(stack s): x = s.top.value s.top = s.top.next In terms of actual time, both of these operations obviously take constant time. Find a potential function Phi for which the amortized time per push is still constant, but for which the amortized time per pop is zero. Explain why the operations have these amortized times for your choice of Phi.