back to cs512-syllabus

CS512 - Teaching Material - Spring 2006

Lectures

1. 3/27/06: Three computational problems: Vertex Cover, 3-SAT and Subset-Sum. Decision Problems. Classes P and NP. Polynomial time many-one reductions. Statement of Cook's theorem. NP-completeness.



2. 3/29/06: Review: deterministic and nondeterministic Turing machines (DTM and NTM). Instantaneous descriptions. Moves and Sequences of computation. Language accepted by a DTM. Deciders. Time complexity of a DTM and of an NTM. Exponential time simulation of an NTM with a DTM. Characterization of NP using NTMs.



3. 4/3/06: Proof of Cook's Theorem. Proving the NP-completeness of problems in NP by reduction from an NP-complete problem. 3-SAT is NP-complete.



4. 4/5/06: Proofs of NP-completeness: VC, CLIQUE, IS, 3-COLORABILITY, SubsetSum, Knapsack.



5. 4/10/06: Linear Programming vs Integer Linear Programming. Analysis of algorithms: the Master method and the Akra-Bazzi method.



6. 4/12/06: Proof of the Akra-Bazzi method. Efficient computation of the median.



7. 4/17/06: Analysis of Select.



8. 4/24/06: RandomizedSelect. Basic introduction to probability spaces and random variables. Expectations. Indicator random variables.



9. 4/26/06: Review on probability theory and random variables. Analysis of the expected running time of RandomizedSelect.



10. 5/1/06: Randomized Quicksort. Analysis of the expected running time. The Quicksort equation. Ordinary Generating Functions (OGF). Solving recurrences using OGFs. The OGF of the Fibonacci Numbers.



11. 5/3/06: Properties of OGFs. The OGF of the Harmonic numbers. Solution to the Quicksort equation using OGFs.



12. 5/8/06: Markov inequality. Chebyshev inequality. The Sample Mean RV. Weak Law of Large Numbers. Chernoff bound.



13. 5/10/06: Analysis of Randomized QuickSort. Application of the Chernoff bound to show that the number of comparisons is O(nlogn) with high probability.



14. 5/15/06: Approximation algorithms. The approximation ratio. A polytime 2-approximation algorithm for MinVC and for the Euclidean TSP. The GAP technique. Nonapproximability within a constant approximation ratio of the general TSP.



15. 5/17/06: Approximation classes. Statement of the PCP theorem. PCP and the GAP technique. Nonapproximability of MAX-CLIQUE.



16. 5/22/06: Randomized Approximation Algorithms. The Max-3SAT Problem. Approximation through LP relaxation: the Min-Weight-VC Problem.



17. 5/24/06: A 2-approximation algorithm for the Min-Weight-VC Problem.



18. 5/30/06: Presentations.



19. 5/31/06: Presentations.



20. 6/1/06: Presentations.

Announcements

• Student Presentations schedule for week 10:

  TR 4:20-6:20 conference room, ECST II floor.

  W 4:20-6:00 C-159 as usual.

Downloads

• Latex Template.
• Median.
• On the Karmarkar Algorithm. Linear Programming.
• Topics List
• sorting
• Class Project. Due Wed, May 24, by 4:20.

References

1. Herbert Wilf. Generatingfunctionology. Academic Press, 1994. A book on Generating Functions available on line (please read copyright note).
2. R. Sedgewick and Philippe Flajolet. Analysis of Algorithms. Addison-Wesley, 1996. (OGF, QuickSort equation, Catalan Numbers)
3. Rajeev Motwani, Prabhakar Raghavan. Randomized Algorithms. Cambridge International Series on Parallel Computation (Hardcover). (Chernoff Bound, Randomized Algorithms)
4. Approximability Theory (PCP).

Assignments

1. Class Project. Due Wed, May 24, by 4:20.
2. MT. Due Sunday, May 14, by 11pm.

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.