CSC 428/528 projects F2015
Below is a list of project ideas for this course.
You are free to make up your own project, so long as it is
in the spirit of the course material. It could even be on
a topic in the book that was not covered in class.
I put a person's name next to a project if they have expressed
interest in doing it.
Some project ideas

[Frank Yang]
There are some nice magic tricks that are based on
generalizations of the De Bruijn cycle idea,
called universal cycles. Investigate some of these.
Of course, if you pick this project,
you will have to give us a demonstration. The recently
published book "Magical Mathematics"
by Diaconis and Graham should be your starting reference.

[Charles Magnuson]
Install the MMIX simulator. Translate some interesting algorithm
into MMIX and demonstrate its behavior in the simulator.

[Alice Gibbons]
Read and implement Knuth's "Dancing Links" paper, and
apply it to some appropriate backtracking problem.
She will apply the dancing links to solve Sudoku puzzles.

[Shayla Redlin]
In exercise 7.1.1.52 Knuth asks you to investigate certain
Boolean games for $1 \le n \lt 10$. Pick one or more of these and
try to figure out what happens for general $n$. One approach
would be to write a program, generate some conjectures from
the observed outputs, and then try to prove one of your
conjectures.

[Haggai Liu]
Counting boolean functions of various types.
Using both mathematics and computation.
Suggestion: classify them further in some way; e.g., by
number of 1s in their truth table.

[Richard May]
Develop algorithms for exhaustively listing "foldings" of various
types; for example, foldings of stamps or 2 by $n$ "maps".

[Riley Motus]
Investigate the problem posed in the following email
from Don Knuth (June 29, 2013):
DonLifeMessage.txt.

[Brendan Heal]
Investigation of optimal strategies for "Mastermind", using
Knuth's paper as a starting point.

Investigate De Bruijn torii (2dimensional De Bruijn cycles).
As part of the project you could explain the connection with
digital paper.

Investigate universal cycles for bitstrings of length $n$ which
contain exactly $k$ 1s. See papers of Ruskey, Sawada and Williams.

Understand and implement algorithm T for drawing conic sections, which
is to be found in Section 7.1.3. Your implementation should be capable
of taking as input any quadradic form and producing a rasterized
drawing of it.

Explore the use of coroutines in producing exhaustive lists of combinatorial
objects, perhaps using the "Spiders" program on Knuth's website as a starting
point.

There are lots of indications that broadword computation can be used to
produce visually interesting patterns. E.g., pages 136 and 185.
Investigate, and then produce some new interesting patterns.

Investigate "orderly algorithms" for producing exhaustive lists of
combinatorial objects. Start the the paper "Every One a Winner"
by Ronald C. Read. See me if you can't find a copy of this paper.

Investigate the Takagi function, particularly exercises 82 and 82 from
Section 7.2.1.3. To me, this function looks related to the
Blancmange function (from the ConwayHofstadter sequence). Are they related?

Read and implement Knuth's "Dancing Links" paper, and
apply it to some appropriate backtracking problem.

In Section 7.1.2, Knuth computes the number of functions
with given complexity for 4variable 1output and
5variable 1output. Try to veryify his numbers.
Or if you want to attempt something new, then try to
give the tables for 4variable 2output functions.

There are a number of interesting topics in 2d graphics
in Section 7.1.3 that we did not cover and that could make
an interesting project. E.g., the stuff on bitmap graphics
beginning on page 171, or trying to generate interesting
patterns using broadword operations in the spirit of
Exercise 7.1.3.17.

Exercise 7.1.3.8 and the following exercises give some
interesting information about the game Nim and the
SpragueGrundy solution to it, as well as extensions
and ramifications. Read understand and explain some of this.

Find an implementation of the SavageWinkler monotone Gray
code construction (or some other monotone Gray code) that uses
only $O(P(n))$ space for some polynomial $P(n)$ of small degree.

Implement the Pruesse/Ruskey ideal generator so that it runs
looplessly  assuming that n <= 64 and storing each ideal in
a computer word. The original construction is in the paper
"Gray codes from antimatroids" but a more accessible version
may be found in the paper "Gray codes for polyominoes"
(Theorem 4.4).

Implement some of the proofs in the Ruskey/Sawada paper on
Bent Hamilton cycles in $d$dimensional grid graphs. Or try
to find some other examples that extend the beautiful symmetric cycle
that was found for $Q'(3,3,3)$.

The solution to 7.2.1.1.83 leaves the open problem of finding
a symmetric solution. Try to find one, or at least some different
solutions to those provided.

In the Mathematics Magazine paper by Chow and Ruskey the question
of finding a fixed polyomino that can be used to form a Venn
diagram is posed and solved, up to $n=5$. Can you do better, or
at least find some other solutions?