Computer Science 428A/528, Fall 2015
Announcements | |
| Projects |
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
(some others forgot to bring theirs).
The text for this course:
Other sources of useful and interesting information related to this book:
The Art of Computer Programming, Volume 4A,
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:
(look for "Errata for Volume 4A").
The pre-fascicle for the material on SAT solvers is here:
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:
- Instructor: Frank Ruskey
- Office: ECS 564.
- Office hours: TWF 2-3.
- Email: hidden.
- Official Outlines:
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 220.127.116.11
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.
18.104.22.168. Generating all n-tuples.
22.214.171.124. Generating all permutations.
126.96.36.199. Generating all combinations.
188.8.131.52. Generating all partitions
184.108.40.206. Generating all set partitions
220.127.116.11. 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.
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 (or CSC 226) are recommended pre-requisites.
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
and the (free) Miktex distribution
For all things TeX related, consult the TeX users group
For making webpages that use LaTeX you will want to use
mathjax (See www.mathjax.org/).
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.
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.