Lecture Notes and Further Readings

- Some models of sequential computation
(handout
and
overhead presentation). Do not
linger too much on Turing machines; we will mostly use the random
access machine throughout the course. You may need to remember
these machines though for at least two reasons: (a) they offer the
simplest definition for nondeterminism, and (b) computations on
Turing machines are defined as graphs of configurations, which has
the merit of allowing the use of typical graph algorithms (such as
traversal) to analyze computations.
- NP-complete problems
(handout
and
overhead presentation). The main
resource for this section is Chapter 34 from Introduction to
Algorithms by Cormen et. al.
The path to proving that SAT is NP complete (through Bounded tiling) is taken from Elements of the Theory of Computation (Lewis and Papadimitriou, second edition, call number QA 267 .L49 1998). Note that Cormen et. al. use satisfiability of Boolean circuits (CIRCUIT-SAT) instead. The proof that Bounded tiling is NP-complete is simpler and more intuitive (hence my choice for this course). This being said, CIRCUIT-SAT is interesting in practice (as opposed to Bounded tiling) and the reduction presented in Cormen et. al. starts from the RAM rather than the Turing machine so it is all well worth reading. It is worth mentioning that Cook proved that SAT is NP-complete from scratch (without going through any intermediate problem).

The second part of the notes discusses a number of proofs of NP-completeness which are taken from Cormen et. al. The authoritative source of NP-complete problems is Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson (available in the library).

The original paper by S. A. Cook is available directly from its author here. Here is a version retyped using a modern typesetting system and so much more readable.

- Student contributions: Here are further examples of NP-complete problems as presented by your fellow students; independent set (Chengxiao Yan, Rachel Berube, and Srikant Damodara Venkata Mohana), set cover (Richmond Osei, Wasif Jami Khan, and Pooja Doshi), graph coloring (Zhao Zhang, Qichuan Shi, and Shiji Jiang), two-machine scheduling (Baichuan Lian, Wentao Lu, and Yi Ren), knapsack (Xinyang Wang, Yuncheng Jia, and Simin Li), subset sum (Maxime Foltz, Guillaume Denoncourt. Nicholas Lafleur), partition (Hamoon Falakfarsa, Sara Eskandarirad, and ZhaoXuan Qin), bin packing (Bhuvaneshwaran Ravi, Serlin Tamilselvam, and Kameswaran Rangasamy), and dominating set (Prashant Singh, Yunxiu Zhang, and Bill Morrisson Talla Jr.). Note that the student papers are given in no particular order, except that the problems are enumerated such that each problem is reduced from either a problem presented in class or from a problem that appears earlier in the enumeration.

- Approximation algorithms
(handout
and
overhead presentation). Most of
the material is discussed according to Cormen et. al.
A much more detailed presentation of approximation schemes can be found in Approximation Schemes - A Tutorial by Schuurman and Woeginger. Many other papers on the matter exist (Google is your friend). It is worth noting that most presentations on the matter start from the Knapsack problem.

I do not have a definite reference for backtracking or branch and bound, but virtually all AI textbooks cover them. Here are some references: Chapter 2: Backtracking from Algorithms by J. Erickson for backtracking and Branch and Bound Algorithms - Principles and Examples by J. Clausen for branch and bound.

Applying backtracking on the kind of problems already discussed in class can also be seen in Algorithms and Complexity by H. S. Wilf. His Chapter 5 covers the whole matter discussed so far in the course so it may be interesting as an alternate point of view to the whole section on NP-completeness and approximation algorithms.

- Linear programming
(handout
and
overhead presentation). This
material is presented according to Cormen et. al., though in a
substantially abbreviated manner.
- Computational geometry
(handout
and
overhead presentation). The
basic processing algorithms (cross product, etc.) and also the
many-segment intersection algorthm are taken from Cormen et. al.,
which also covers the Graham scan and gift wrapping convex hull
algorithms.
An excellent overview of convex hull algorithms is Lecture 3: More Convex Hull Algorithms by David M. Mount, which also includes a detailed discussion on lower bounds (only available through the Way Back Machine these days; a somehow simplified version is shown in (the second part of) Lecture 3 and Lecture 4 from CMSC 754: Computational Geometry by the same David M. Mount). These document presents Quickhull directly with the Akl-Toussaint optimization. Quickhull is introduced in The quickhull algorithm for convex hulls by C. Barber Bradford, D. P. Dobkin, and H. Huhdanpaa (ACM Transactions on Mathematical Software, 22:4 (1996), 469-483). The Akl-Toussaint heuristic is introduced in A fast convex hull algorithm by (you guessed it) S. G. Akl and G. T. Toussaint (Information Processing Letters, 7 (1978), 219-222) which unfortunately does not appear to be available on line. The original paper actually presents a complete algorithm for finding the convex hull. The performance of the algorithm is further studied in A note on linear expected time algorithms for finding convex hulls by L. Devroye and G. T. Toussaint, (Computing, 26 (1981), 361-366).

The Wikipedia pages for gift wrapping, Graham scan, Quickhull, and Chan's algorithm are not bad at all and also provide cute animated demonstrations of the respective algorithms.

- Parallel models and algorithms
(handout) Recall that
this section is to be handled as a reading course (hence the
different format for the handout). You are better off with the
handout, with only occasional (if any) reference to the textbook.
Section 1 and 2 from the handout cover most of Chapters 1 and 2 from Parallel Computation: Models and Methods by S. Akl. Various painstaking details of the innards of the PRAM and interconnection networks presented in Chapter 2 are intentionally glossed over since they are not relevant to the matter at hand.

Section 3 covers part of Chapter 4 from Akl namely, Sections 4.1 to 4.4 and also 4.6.

Section 4 covers most of Chapter 5 from Akl. Merging is presented according to The Design and Analysis of Parallel Algorithms (by S. G. Akl, Prentice Hall, 1989), though the resulting algorithm is similar (but not quite identical) to the one shown in Chapter 5. Becoming familiar with one of these two variants is more than enough.

Finally, Section 5 comes from the beginning of Akl's Chapter 7 and roughly the first half of Chapter 9.

My lectures are recorded, as follows:

- The introduction (Lecture 1) was not captured.
- Models of computation: Lecture 2 (camera/screen)
- NP-complete problems: Lecture 3 (camera/screen), Lecture 4 (camera/screen), Lecture 5 (camera/screen), most of Lecture 6 (camera/screen), Lecture 11 (student presentations, not recorded)
- Approximation algorithms: a bit of Lecture 6 (camera/screen), Lecture 7 (camera/screen), Lecture 8 (camera/screen)
- Linear programming: Lecture 9 (camera/screen), Lecture 10 (camera/screen), Lecture 12 (camera/screen)
- Computational geometry: Lecture 13 (mic failure, not recorded), Lecture 14 (camera/screen), Lecture 15 (camera/screen)

There are two videos for each lecture, one featuring the camera feed and the other featuring a capture of the front desk screen. The audio track is the same for both videos. It is difficult to recommend one stream over another generally, since depending on the lecture things may happen on the screen or on the whiteboard. You may want to run both streams simultaneously (one of them muted).