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:

Other sources of useful and interesting information related to this book:

Administrative details

Outline of Section 7.1

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

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

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.