CS 261, Spring 2025, Practice Problem Set 1

1. The lecture includes the description of an implementation of stacks using a linked list, with a value and a next pointer in each list node, and with a top pointer from the stack to the first node in the list. If we use the same node structure and also store an additional bottom pointer to the last node in the list, it is possible to implement a queue, whose dequeue operation is the same as the pop operation of a stack, but with a different enqueue operation.

   Describe (in English or pseudocode) how to perform an enqueue operation in constant time with this modified structure. Be sure to properly handle the case when the queue is empty (its top pointer is a null pointer).

2. It is possible to implement a queue using two stacks, without knowing how the stacks are implemented. Let's call the two stacks the input stack and the output stack. To enqueue a value, push it onto the input stack. To dequeue a value, first check whether the output stack is non-empty. If it is non-empty, pop it and return what you get as the result of the dequeue. But if the output stack is empty, instead do the following more complicated dequeue operation: repeatedly pop the input stack and push the result onto the output stack, until the input stack is empty. Then, pop the output stack and return the result.

   Find a potential function $\mathrm{\Phi }$ for which each enqueue and dequeue operation performs a constant amortized number of stack operations.

3. Let's modify the linked-list stacks in a different way. Modify the push operation so that it returns the node in which the pushed value is stored, and add a new delete operation that takes one of these nodes as its argument, and replaces the value in that node with a special deleted flag value (without removing the node from the stack). Then, modify the pop, top, and isempty operations so that they first call a subroutine to "clean" the stack, by repeatedly removing any deleted values on the top of the stack (leaving in place deleted values that are not at the top of the stack). After cleaning, pop, top, and isempty perform the rest of their operation as before.

   Find a potential function $\mathrm{\Phi }$ for which all operations, including the new clean operation, take amortized time $O(1)$.

4. Suppose we increase the length of a dynamic array $n$ times, adding one to the length each time, starting from an array with length = 0 and available = 1. Each time we increase the length, we store the new length into the last cell of the array (so the first value we store is 1, the second value is 2, etc). As in the basic form of the dynamic array, whenever an increase-length operation overflows (causing length to exceed capacity) we double the capacity of the array and copy all its values into a new block of memory of the new capacity. Through the course of these actions, different values in the array will be copied different numbers of times. Which value is copied the most times, and how many times is it copied, as a function of $n$? Which values are stored into the array but never copied, as a function of $n$? (It may be easier to express your answer to this part in English rather than trying to write a formula for it.)