# 010101101010011101010110101010010101010000001101110101010110

## Computer Science 428A/528, Spring 2014

Announcements | | Schedule | | Projects | | Presentations

# Combinatorial Algorithms

Donald Knuth published Volume 4A of his "classic" book The Art of Computer Programming in 2011, and is currently working on Volume 4B. Volume 4 is entitled Combinatorial Algorithms, and is to be split into at least 3 smaller volumes, 4A, 4B and 4C. In this course we will cover a carefully selected set of topics from Volume 4, skipping those parts where the mathematics is too deep.

The idea of this course is to introduce students to the most recent of Knuth's writings, concentrating on those topics that are most likely to be of interest to aspiring programmers and algorithm designers. Reading Knuth can be a daunting and humbling task, and my aim is to make it as painless as possible, and reveal some of the treasures that lie therein. If you want to see what I wrote about the predecessors to this course, take a look at: Teaching the Art of Computer Programming. Here's a class photo of the first incarnation of the course: ClassPhoto; note that some students are holding Knuth checks (some others forgot to bring theirs).

The text for this course:

• The Art of Computer Programming, Volume 4A, Addison-Wesley, 2011.
• As of December 10, this book is selling for $52.91 on amazon.ca (and you can get all 4 volumes for an amazing$157.49).
• A list of errata for the book may be found at: TAOCP (look for "Errata for Volume 4A").
• The pre-fascicle for the material on SAT solvers is here: www-cs-faculty.stanford.edu/~knuth/fasc6a.ps.gz.
Other sources of useful and interesting information related to this book:
• Some of Don's "Computer Musings" are directly related to material that we will be covering in this course.
• Hacker's Delight by Henry Warren: This book contains a collection of programming tricks at the bit level. There is an associated website: www.hackersdelight.org.

• Instructor: Frank Ruskey
• Office: ECS 564.
• Office hours: TBA.
• Email: hidden.
• Official Outlines: csc528, csc428A.

## Outline of Section 7.1

• 7.1. Zeros and Ones.
• 7.1.1. Boolean Basics. [history, truth tables, operators, normal forms, satisfiability, Horn clauses, median algebra and median graphs, symmetric boolean functions]
• 7.1.2. Boolean Evaluation. [Boolean circuits, Boolean chains, asymptotic facts, synthesis, decomposition, lower bounds]
• 7.1.3. Bitwise Tricks and Techniques. [bitwise operations, packing and unpacking, big-endian and little-endian, working with the right bits, working with the left bits, broadwords, lower bounds, applications to graphs and data structures]
• 7.1.4. Binary Decision Diagrams. [BDD virtues, Boolean programming, synthesis of BDDs, zero-supressed BDDs]

Nice topics we will cover from this section: (a) the linear time algorithm for 2SAT (pg 60-62), (b) sideways heaps, (c) the 3-register algorithm for drawing lines and circles in bit-mapped graphics.

## Outline of Section 7.2.2.2

• 7.2.2.2. Satisfiability.

Nice topics we will cover from this section: (a) using SAT solvers to solve problems about the game of "life", (b) Don's simple SAT solver implementations.

## Outline of Section 7.2.1

• 7.2.1. Generating Basic Combinatorial Patterns.
• 7.2.1.1. Generating all n-tuples.
• 7.2.1.2. Generating all permutations.
• 7.2.1.3. Generating all combinations.
• 7.2.1.4. Generating all partitions
• 7.2.1.5. Generating all set partitions
• 7.2.1.6. Generating all trees

Nice topics we will cover from this section: (a) generating necklaces, (b) a linear time algorithm to determine whether two strings are rotationally equivalent, (c) bubble languages.

## Pre-requisites

The pre-requisites for an undergraduate wishing to enroll in this course are: a minimum grade of B+ in both CSC 225 and Math 222, and 4th year standing. The courses CSC 320 and CSC 326 are recommended pre-requisites. However, if you wish to take this course and do not satisfy the pre-requisites then please contact me since it would be good to get a few more students in the course.

## Projects

In general the projects may be on any research topic that is closely related to the material presented in the course or that is found in the book (even if we don't cover it).. Open problems in the text (those rated 45 and higher) are suitable, but of course, they are very difficult.

## In the spirit of TeX

You should learn enough TeX (or LaTeX) in order to write up your homework and prepare your presentations. If there is sufficient demand then I will schedule some lectures about preparing LaTeX documents and web pages. In a Windows environment, I recommend the editor winedt (http://www.winedt.com) and the (free) Miktex distribution (http://www.miktex.org/). For all things TeX related, consult the TeX users group (http://www.tug.org/). For making webpages that use LaTeX you will want to use mathjax (See www.mathjax.org/).

## Knuth's programs

We will also try to examine some of the programs on Knuth's site. To do that we will have to learn a little about "literate programming" and CWEB.

# Announcements

The University of Victoria is committed to promoting, providing and protecting a positive, and supportive and safe learning and working environment for all its members.

• Nomination pdf, tex.