Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

/Discuss this assignment. /Solutions are available.

# 1. Up/down CounterHenge

After the catastrophic Year of the Five High Priests, where the builders of CounterHenge deposed four high priests who each suggested decrementing the menhir-based counter just after mistakenly incrementing it from 0111111111 to 1000000000, Nooma the Stonecutter suggested a modified representation that would allow cheap decrements even after an expensive increment. The idea is that instead of just representing 1 by a standing stone and 0 by a lying stone, the henge would also represent -1 (or "-" for short) by an upside-down standing stone. This would allow counting backwards from 1000000000 by turning stones upside-down: 100000000-, 10000000-0, 10000000--, etc., where each 0 is changed to a -1 only when necessary. It also permits incrementing again by changing minuses to zeroes.

Suppose that it costs one unit of labor to change either a 1 or -1 to a 0 or vice versa. Prove that the amortized cost of any sequence of increments and decrements on an instance of Up/down CounterHenge with n stones is O(1) per increment or decrement operation, or give a counterexample that shows that the henge-builders must pay an ω(1) amortized cost in some execution.

Assume that the initial state of CounterHenge is always 000...0.

# 2. A solitaire game

Consider a card game for one player with the following rules:

1. Deal out all cards face-up in a row. One of the cards has a star on it; the rest have numbers in the range 1 to N for some N.
2. Starting with the leftmost card, look at the number k on the card, turn it face down, and then count to the k-th face-up card to the right (wrapping around if you get to the end of the row. Repeat the process starting with the k-th card you reached, until you reach the star card.
3. If there are any other cards that are face up when you reach the star card, you lose. Otherwise you win.

An example of the game being played might look like this, where the current card is marked with square brackets and turned-over cards are replaced with Xs:

```[3] 1  2  7  4  *  6  5
X  1  2 [7] 4  *  6  5
X  1  2  X [4] *  6  5
X [1] 2  X  X  *  6  5
X  X [2] X  X  *  6  5
X  X  X  X  X  * [6] 5
X  X  X  X  X [*] X  5```
1. Suppose the game is played using the naive algorithm specified by the rules, where counting to the k-th face-up card requires constant time for each face-up or face-down card you pass over. Suppose further that the cards are numbered 1 to n-1 and *, where n is the total number of cards. Compute the best upper bound you can on the worst-case asymptotic time to complete the game, as a function of n.

2. Give an algorithm that takes the initial state of the game as input and returns whether you win or lose in O(n log n) time, under the assumption that the cards have the numbers 1, 2, 3, ..., n-1 and *.

3. Give an algorithm that takes the initial state of the game as input and returns whether you win or lose in O(n) time, under the assumption that the non-star cards have arbitrary numbers in the range 1..k, where k = O(1).

2014-06-17 11:58