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 (2-dimensional 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 Conway-Hofstadter 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 4-variable 1-output and 5-variable 1-output. Try to veryify his numbers. Or if you want to attempt something new, then try to give the tables for 4-variable 2-output functions.

• There are a number of interesting topics in 2-d 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 Sprague-Grundy solution to it, as well as extensions and ramifications. Read understand and explain some of this.

• Find an implementation of the Savage-Winkler 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?