CSC482A/528 - Knuth 4A (Fall 2011)
Assignment 4
Due: November 4, 2011, at the beginning of class.
Write a program in Java or C that takes as input two integers
s and t and produces all bitstrings of length s+t that
contain s 0s and t 1s in lexicographic order.
Do this using broadword computation;
the strings are to be stored in one computer word.
Prove the existence of a Gray path for the set of all binary
strings of length n with no 00 substring. How many such strings are there?
Why didn't I ask for a Gray cycle? Are there any values of n
for which Gray cycles exist?
From 7.2.1.1: If Algorithm F is used to generate a De Bruijn
cycle when m=3 and n=9, where does the string
A = 220121012 occur? I.e., what is the minimal
sequence of prime strings output by
Algorithm F that contain A as a substring?
For example, if m=3 and n=4 the answer
for the string 2211, referring to Equation (62), is 0222,1,1112.
Try to answer the question without implementing
the algorithm.
What is the De Bruijn cycle output by Algorithm A (Almost linear
bit-shift generation) when n = 5?
From 7.2.1.2: Solve question 4, but using 271828182 instead
of 314159265. The answer to the first part of the
question is in the solutions. You should carefully explain
the equation you find there.
Explain why the btc2c2ctbbt magic card trick works.
Here, b = move top to bottom; t = turn over top;
2 = turn over top 2;
c = cut the deck anywhere. Recall that we start with 4 cards, and
the aim is to identify the (hidden) bottom card.
This is done by picking, at the end, the single card that
is oppositely oriented (face-up or face-down) to the other
three cards.
Hand in a one-page explanation of what your project is, and what
you hope to accomplish with it when it is finished.