Advanced Data Structures

Fall 2003

Try your hand at some loop invariant problems!
(from "Problem-Solving Strategies" by Arthur Engel, Springer)

On an 8 x 8 checkerboard, we are allowed to switch colors in a single row or column (call the operation switch). Can we obtain a single Black square (and 63 White squares) by repeatedly applying switch?
A clock has six "hours" labeled 1, 0, 1, 0, 0, 0. An operation add changes the labels of two adjacent hours by adding 1 to each. Can we arrive at the clock with all six hours labeled by the same integer by repeatedly applying add?
A 4 x 4 grid has location (1,2) marked -1 and the other 15 locations marked +1. An operation negate changes signs of all locations of a column, a row, a diagonal, a sub-diagonal of the grid. Can we arrive at all locations marked +1 by repeatedly applying negate?
For an odd positive integer n, write the numbers 1, ..., 2n. Repeatedly replace two arbitrary integers, a and b, in the list by the absolute value of their difference, |a-b|. What can you say about the last remaining integer (after 2n-1 replacements)?
Define a sequence of numbers {x_n, y_n} by
- x_0=a, y_0=b (a, b > 0)
- x_{n+1}=(x_n+y_n)/2; y_{n+1}=2(x_n)(y_n)/(x_n+y_n).
Does the sequence converge? If so, what is the limit?