This schedule is subject to change, and is mainly a record of what happened.

CSC 428A/528, Fall 2015 - Schedule

Oct 7
Date Topic Reading
or Title
What's due
(announcements)
Week 1
Sep 9 Intro, Knuth nomination, Zhagalkin expansion. 7.1.1 .
Sep 11 Zhagalkin trees, LaTeX intro. 7.1.1 .
Week 2
Sep 15 Boolean terminology, Krom and Horn clauses. 7.2.1.1. .
Sep 16 Horn core computation, Solving 2SAT. 7.1.1.
Sep 18 Horn core computation, Solving 2SAT. 7.1.1.
Algorithm C pseudo-code
onlineCLRS (for SCC and topological sort.
Also in the 225/226 Algorithms text.
Week 3
Sep 22 Horn core computation, Finish up 7.1.1. . .
Sep 23 Boolean Evaluation. 7.1.2. Mabon, Yom Kippur, Eid-al-Adha (no work/exam).
Sep 25 Boolean evaluation. 7.1.2. .
Week 4
Sep 29 Boolean evaluation, addition chains, binary powering. 7.1.1.
onlineCLRS: See the "Powers of an element" section in the Number-Theoretic Algorithms chapter.
Addition chains are covered in Volume 2 of TOACP also (that's where the in-classtree comes from).
.
Sep 30 Bitwise tricks and techniques. 7.1.2. .
Oct 2 Prep for talks next week. . .
Week 5
Oct 6 SAT problems and solvers. First part of 7.2.2.2.
Class slides.
Lecture given by Alejandro Erickson.
Frank at IWOCA.
SAT problems and solvers. First part of 7.2.2.2.
Class slides.
Lecture given by Alejandro Erickson.
Frank at IWOCA.
Oct 8 Generating Permutations, Sims tables. 7.2.1.2. Lecture given by Bill Bird.
Frank at IWOCA.
Week 6
Oct 12 Bitwise tricks and techniques. . 7.1.2. .
Oct 13 De Bruijn sequences, Eulearian digraphs. Notes .
Oct 16 Bitwise tricks and techniques. 7.1.2. .
Week 7
Oct 20 Finish bitwise tricks and techniques. 7.1.2. Birth of the Bab (no work/exam). .
Oct 21 MIDTERM. MIDTERM.
Oct 23 Backtracking ala Ruskey. Backtracking notes. .
Week 8
Oct 27 Backtracking ala Ruskey, cont. . .
Oct 28 . . .
Oct 30 Generating all n-tuples. 7.2.1. .
Week 9
Nov 3 The Binary Reflected Gray Code. . .
Nov 4 The Binary Reflected Gray Code. . .
Nov 6 Gray codes. . .
Week 10
Nov 10 READING BREAK READING BREAK READING BREAK
Nov 11 READING BREAK READING BREAK READING BREAK
Nov 9 De Bruijn Cycles. 7.2.1.1. .
Week 11
Nov 17 Generating De Bruijn cycles, prime strings, necklaces. 7.2.1.1 and Ruskey notes.
DeBruijnChpt.pdf.
.
Nov 18 Generating De Bruijn cycles, prime strings, necklaces. 7.2.1.1. .
Nov 20 . 7.2.1.6. .
Week 12
Nov 24 . 7.2.1.6. .
Nov 25 . 7.2.1.6. .
Nov 27 Steinhaus-Johnson-Trotter (plain changes). 7.2.1.2.
Some code.
.
Week 13
Dec 1 Generating Topological Sortings (linear extensions). 7.2.1.2. .
Dec 2 . . .
Dec 4 Grad Student Presentations. 9:30: Yudi.
9:45: Fabrizio. Thinning Algorithms.
10:00: Frank, Magic and Universal Cycles.
.
Week 15-16
Dec 6 EXAMS BEGIN GOOD LUCK Homework #5 due.
GOOD LUCK
Dec 20 EXAMS END HAVE A GREAT HOLIDAY! HAVE A GREAT HOLIDAY!