Computer Science 482A/528
Announcements | |
| Projects |
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:
Other sources of useful and interesting information related to this book:
The Art of Computer Programming, Volume 4A,
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:
(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:
- 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.
126.96.36.199. Generating all n-tuples.
188.8.131.52. Generating all permuatations.
184.108.40.206. Generating all combinations.
220.127.116.11. Generating all partitions
18.104.22.168. Generating all set partitions
22.214.171.124. Generating all trees
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.
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.
In a Windows environment, I recommend the editor winedt
and the (free) Miktex distribution
For all things TeX related, consult the TeX users group
Here is a solution to Demaine's "Algorithm Puzzle":
Here are sample solutions for the midterm:
For the midterm make sure you know:
Ideal and linear extension concepts;
The sign-reversing involution given in class;
combinations and representations, Gray codes
The Varol-Rotem algorithm; binary trees,
well-formed parentheses, Catalan
numbers, Remy's algorithm; numerical partitions;
what is a Venn diagram.
Dates of grad student presentations:
Tue, Nov 29:
Tue, Nov 30:
Fri, Dec 2:
Assignment #5 posted.
Good things to review for the midterm:
Krom and Horn clauses; delta sequences; 2-adic numbers;
sideways heaps; Lyndon (prime) factorization.
Assignment #4 posted.
Assignment #3 posted.
Here's a formatted version of Algorithm V: algV.pdf.
Solution to Assignment #1 posted.
Assignment #2 posted.
Assignment #1 posted.
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.