Homework 1 Solution

NOTE: Homeworks for this class are provided both as a pdf le and as a LaTeX template. You may use the template to produce your answers as a pdf le (for instance by using a local LaTeX installation or by copying the template onto overleaf.com) or you may produce the answers as a pdf le in any other way (including writing them by hand and then scanning them, as long as your handwriting is legible).







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 rst 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 di erent enqueue operation.
how to make sure


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

























Suppose we modify the binary counter data structure described in the lecture to include an additional \decrement" operation, that subtracts one from the binary counter. Its implementation is almost the same as the \increment" operation: change low-order bits from 0 to 1 until nding the lowest-order 1 and changing it to 0, then stop.



??meaning?Describe how to nd, for any n, a sequence of operations that causes this operation to make at least (n log n) changes to the bits that it stores. (This is big-Omega notation, used just like O-notation but for lower bounds.) Use your sequence to argue that it is not possible for this structure to have constant amortized time per operation.
















The dynamic array analysis from the lecture (in its most basic form, with the allocated array increasing in size by a factor of two each time and never decreasing) used the potential function






= j2 length availablej:




Explain why the amortized analysis doesn’t work if we forget the absolute value signs and try to use the function




= 2 length available




instead.








































1



Suppose that we need to implement a circular list of items (each item has an item clockwise from it in the list and another item counterclockwise of it, and these clockwise and counterclockwise links connect the items into a single cycle), with one item designated as the current item, and the following four operations:



Move the current item one position clockwise and return its new value




Move the current item one position counterclockwise and return its new value Insert a new item clockwise of the current item and move the current item to it Remove the current item and move to the item that was clockwise from it




You have available a library that implements a deque data structure, which maintains a linear (not circular) sequence of items and lets you add or remove items at either the left or right end of the sequence. Describe how to represent the circular list as a deque, in such a way that all four circular list operations can be performed using a constant number of deque operations. Give the details of how to implement the move-clockwise circular list operation using deque operations. (You do not need to describe the details of the other three circular list operations, but your representation should allow them all to be performed using a constant number of deque operations.)





































































































































2