Models of sequential computation ( handout and overhead presentation). I do not have a definite reference for Turing machines. If anything my description follows Elements of the Theory of Computation (Lewis and Papadimitriou, second edition, call number QA 267 .L49 1998). I am not aware of any previous reference to the definition of nondeterministic algorithms using the Guess operation. Generally algorithms people prefer to replace nondeterminism with different (but equivalent) concepts; we will meet those later.
Do not linger too much on Turing machines; we will mostly use the random access machine throughout
the course. You may want 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. Check out the Moodle page of the course for downloadable material.
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.
Approximation algorithms ( handout and overhead presentation). Most (but not all) of the material is discussed according to Chapter 35 from Introduction to Algorithms by Cormen et. al. Check out the Moodle page of the course for downloadable material.
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.
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. Downloadable material can be found on Moodle as usual.
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 (original no longer up, but available through the Way Back Machine). This document present 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.
Models of parallel computation ( handout and overhead presentation). These lectures cover most of Chapters 1 and 2 from Parallel Computation: Models and Methods by S. Akl (downloadable resources available on Moodle). Various painstaking details of the innards of the PRAM and interconnection networks presented in Chapter 2 are intentionally glossed over and will be discussed later on an as-needed basis.
As a motivating example of parallel approaches to algorithm design these lectures also cover Chapter 4 up to Section 4.8 (inclusive). Some downloadable material on this matter can be found on Moodle.
My lectures are recorded, as follows:
Note: Lecture 12 did not happen (show day); lecture 15 was the mid-term examination.