Donald Knuth has just published Volume 4 of his "classic" book The Art of Computer Programming. We will attempt to at least skim much of the material in this book, skipping those parts where the mathematics is too deep. Volume 4 is entitled Combinatorial Algorithms, and is to be split into 3 smaller volumes, 4A, 4B and 4C. Volume 4A is published and he continues working on 4B and 4C.

The text for this course:

• The Art of Computer Programming, Volume 4A, Addison-Wesley, 2011.
• As of August 5, this book is selling for $63.19 on amazon.ca.
• A list of errata for the book may be found at: TAOCP (look for "Errata for Volume 4A").
• There is some chance that Knuth will produce another pre-fascicle before or during the course and, if so, we may try to cover some of that instead of all the topics mentioned on this page.

• 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

• Office: ECS 564.
• Office hours: TWTh 3-4.
• Email: hidden.

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]

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 permuatations.
  • 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

Pre-requisites

Projects

In the spirit of TeX

Announcements

• Dec 2: Here is a solution to Demaine's "Algorithm Puzzle": ALGORITHMpuzzle.pdf (thanks Nishat!).
• Nov 28: Here are sample solutions for the midterm: csc528midterm2ans.pdf.
• Nov 17: For the midterm make sure you know: Ideal and linear extension concepts; The sign-reversing involution given in class; combinations and representations, Gray codes for combinations; The Varol-Rotem algorithm; binary trees, well-formed parentheses, Catalan numbers, Remy's algorithm; numerical partitions; what is a Venn diagram.
• Nov 17: Dates of grad student presentations:
  • Tue, Nov 29:
    12:30-12:55: Veronika Irvine.
    12:55-01:20: Chris Duffy.
  • Tue, Nov 30:
    12:30-12:55: Nishat:
    12:55-01:20: Bill Bird:
  • Fri, Dec 2:
    12:30-12:55: Tom Spreen:
    12:55-01:20: Jenn Debroni:
• Nov 12: Assignment #5 posted.
• Oct 22: Good things to review for the midterm: Krom and Horn clauses; delta sequences; 2-adic numbers; sideways heaps; Lyndon (prime) factorization.
• Oct 21: Assignment #4 posted.
• Oct 5: Assignment #3 posted.
• Oct 5: Here's a formatted version of Algorithm V: algV.pdf.
• Sep 30: Solution to Assignment #1 posted.
• Sep 20: Assignment #2 posted.
• Sep 9: Assignment #1 posted.