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?