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, Addison-Wesley, 2011.
• As of Sept 8, this book is selling for $77.74 ($59.19 for Kindle version) on amazon.ca. You can get all 4 volumes for an amazing $163.79.
• See Pearson Publishing for other options.
• 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.
• Neal Wagner kindly provides a list of prefascicles that can be downloaded for free: downloads. There are both links to Knuth's originals and pdf conversions.

• 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: TWF 2-3.
• 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, 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

Projects

In the spirit of TeX

Knuth's programs

Announcements

• Dec 10: Notes regarding the projects: Projects2015.html.
• Dec 10: Notes regarding the final exam: Final2015.html.
• Nov 26: Assignment #6: ass6_2015.html.
• Nov 13: Assignment #5: ass5_2015.html.
• Some links:
  • Pete Winkler's (first) puzzle book: Mathematical Puzzles.
  • Frank's floating point rho extractor program: RhoTest.c.
  • The "small odd number" rules: OddRules.pdf.
• Oct 27: Assignment #4: ass4_2015.html.
• Oct 22: Midterm solutions. (Marks are 15,15,20,21,23,24,24,26,28,29,30.)
• Oct 22: That book I mentioned in class: Hackers. Here is HAKMEM (see item 175 on page 82 for Gosper's hack).
• Oct 13: From the preliminary final exam schedule:

  CSC 428A/528 A01 Frank Ruskey Wednesday Dec-16 7:00 PM
  

• Oct 13: Here's an example of an old midterm: csc528midS2014.pdf.
• Oct 13: Assignment #3: ass3_2015.html.
• Oct 12: From now on, office hours will be 2:30-3:30. Too many department meetings are scheduled that overlap with the previous hours.
• Oct 1: A reminder that Frank is away next week. Turn in your homework as usual at the beginning of class.
• Oct 1: The MMIX book can be downloaded here if you are interested. I.e., from the link "First Fascicle".
• Sep 18: Assignment #2: ass2_2015.html.
• Sep 15: ACM Programming Contest Info. Note that the sign-up deadline is Sept 19 (I need to sign up the teams by then). If you are interested please organize your team, register, and let me know who is on the team.
• Sep 10: Assignment #1: ass1_2015.html.