010101101010011101010110101010010101010000001101110101010110
Computer Science 428A/528, Fall 2015
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,
as well as some of Knuth's other writings.
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,
AddisonWesley, 2011.

As of July 21, this book is selling for $83.99 ($59.19 for
Kindle version) on amazon.ca.
You can get all 4 volumes for an amazing $16.79.

A list of errata for the book may be found at:
TAOCP
(look for "Errata for Volume 4A").

The prefascicle for the material on SAT solvers is here:
wwwcsfaculty.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.
Administrative details
 Instructor: Frank Ruskey
 Office: ECS 564.
 Office hours: TBA.
 Email: hidden.
 Official Outlines:
csc528,
csc428A.
Outline of Section 7.1
We will be concentrating on 7.1.3.

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, bigendian and littleendian, 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, zerosupressed BDDs]
Nice topics we will cover from this section: (a) the linear time algorithm
for 2SAT (pg 6062), (b) sideways heaps, (c) the 3register algorithm for
drawing lines and circles in bitmapped graphics.
Outline of Section 7.2.2.2
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 ntuples.

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.
Prerequisites
The prerequisites 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 (or CSC 226) are recommended prerequisites.
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.