back to cs512-syllabus

CS512 - Teaching Material - Fall 2006

Lectures

  1. 9/26/06: Presentation of the course. Decision Problems: 3-SAT, VC, SS, CLIQUE, COL, PARTITION, IS. Deterministic and nondeterministic Turing Machines. Configurations. Deciders. Review on asymptotic notation. The classes P and NP. The generalized Church thesis.

  2. 10/02/06: Analysis of algorithms: integer powers of a real number and the repeated squaring method. Experimental analysis and curve fitting: the LS method. The class of languages efficiently verifiable. Many-one polynomial time reductions. Reducing SAT to 3-SAT. Notion of NP-completeness. Statement of Cook's Theorem. NP-complete problems and the P vs NP question.

  3. 10/09/06: Proof of Cook's theorem. NP-completeness of IS, VC and CLIQUE.

  4. 10/16/06: Analysis of the repeated squaring method algorithm. NP-completeness of 3-COL and SubsetSum. Evaluating polynomials: the Horner method. Applications to the computation of hash codes. Evaluation and interpolation. The Vandermonde matrix and the Vandermonde transform. Convolution theorem.

  5. 10/23/06: The Discrete Fourier Transform. The FFT.

  6. 10/30/06: Discussion on the class project. In-bin sampling. The Nyquist frequency and the problem of aliasing. Multiplying large integers with the DFT.

    Linear time computation of the median.


  7. 11/6/06: The Akra-Bazzi method. Solving the equation of Select using the Akra-Bazzi theorem. Randomized algorithms. RandomizedSelect. Review of probability theory: probability spaces, random variables, distributions and densities, expectations, stochastic independence. Indicator Random Variables. Analysis of RandomizedSelect.

  8. 11/13/06: RandomizedQuickSort. The QuickSort equation. Chernoff Bound. Efficiency of RQS with high probability.

  9. 11/20/06: Approximation ratio and Approximation Algorithms. MinVC. APX, PTAS and FPTAS. Nonapproximability of TSP. The GAP technique. Min-weight VC. Randomized Approximation Algorithms. Max3SAT.

  10. 11/27/06: Review of MT. Markov Chains and Hidden Markov Models. Dynamic Programming. Principle of suboptimality. The Viterbi algorithm.

Downloads

  1. 10/17/06: Topics List

  2. 11/20/06: Schedule of the Fall 2006 final presentations (update 11/20 at 11:30pm).

Announcements

  1. 10/9/06: Today's lecture will be held in room A332.

  2. Wednesday, November 15, OH will be held from 10am to 12am.

Assignments

  1. cs512-f06-hw1. Due Monday, October 16, 2006, before class.
  2. cs512-f06-pj. Due Thursday, November 30, 2006 (before 8:00pm).
  3. Midterm. Due Monday, November 20, 2006, before 6:00pm (upload only ps or pdf files).

Additional References

  1. Rajeev Motwani, Prabhakar Raghavan. Randomized Algorithms. Cambridge International Series on Parallel Computation (Hardcover). (Chernoff Bound, Randomized Algorithms)
  2. Approximability Theory. (PCP)
  3. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of Np-Completeness. W.H. Freeman & Company (June 1979). (NP-completeness and Cook's theorem)
  4. Christos Papadimitriou. Computational Complexity. Addison Wesley; 1ST edition (November 30, 1993). (complexity theory)
  5. Hidden Markov Models.

CSNS - Computer Science Network Services

Assignments and exams should be uploaded by the due date through the CSNS - Computer Science Network Services website. If you have never used this system before then follow the instructions for students.