Assignment #5

Theme: Circular strings and De Bruijn cycles

Assigned: November 13, 2015.

Due: November 25, 2015.

Reminder: homework should be handed in should be in latex (or tex) at the beginning of class on the due date.

• Write a program to generate the binary strings from the no 00 problem (the Gray path) from the previous assignment. Analyze your program. This will be easier to do if you write your program recursively. If you can't do the analysis mathematically, then at least do it experimentally (e.g., graph of the amortized running time). If you didn't get the correct answer on the last assignment, see exercises 88 and 89. Strive for an algorithm that uses a constant amount of computation per string (CAT), in an amortized sense; i.e., so that the ratio (total work)/(number of strings) is a constant. Note that an algortihm need not be loopless to have the CAT property. Your solution might involve Fibonacci numbers, and you can use any known bounds or asymptotics of Fibonacci numbers in your solution (but let me know where you found the bound).

• (a) Write a program to generate all prime binary strings with no substring 00. Analyze your program using the same criteria as in the previous problem. If you can't do this mathematically, then at least do it experimentally. (b) How many strings are computed by your program for $n = 1,2,\ldots,20$? Look up this number in the OEIS. Prove the formula that you find there.

• On page 221 of my book, in the first paragraph, there is an implicit question about where two strings appear in their respective De Bruijn cycles. Answer that question by showing the successive primes that contain the strings as they would be output by our De Bruijn cycle algorithm.