CME 352, Molecular algorithms, Winter 2007-08. HW Set 1. Handed out 1/20/2008, due 1/31/2008. ATTEMPT ANY TWO: Problem 1: A geometric spiral is one where each successive arm is a constant factor (say two) larger than the previous. An arithmetic spiral is one where each successive arm is a constant (say one) longer than the previous. Describe how you can make an infinite arithmetic or geometric spiral. The spiral should not be a convex body. i.e. there should be a gap between two successive arms that go east. Problem 2: Prove that a log(n) X N binary counter is combinatorially equivalent to a log N bit de-multiplexer (i.e. there is a one to one mapping from bits to simple circuit gates which will turn the counter into a de-multiplexer). Draw the circuit corresponding to a simple computer memory and comment on how (in theory) this could be self-assembled using binary counters with some simple augmentations. Assume that N is a power of 2. Problem 3: Analyze the assembly time of a Chinese remainder counter which has K columns, one corresponding to each of the first K primes. You can assume that the K-th prime is Theta(K log K). Your analysis must be tight up to constant factors. How many tiles does the counter use as a function of K? As a function of the height of the counter?