back to cs512-syllabus

CS512 - Teaching Material - Fall 2007

Lectures

  1. 9/25/07: Presentation of the course. Review: asymptotic notation, recurrences and the master method (cp. 2,3). Efficient computation of the median: the algorithm select (cp. 9).

  2. 10/01/07: Analysis of algorithm select. The substitution method. The Akra-Bazzi method. Discussion on the variations of the select algorithm. Introduction to Randomized Algorithms and Probabilistic Analysis. Algorithm Randomized-Select.

  3. 10/08/07: The Hire-Assistant problem. Indicator random variables. Analysis of Algorithm Randomized-Select. Experimental Analysis. Parameter Estimation: the Least-Squares Method. Discussion on the project.

  4. 10/15/07 (notes revised 11/16/07): Probability Spaces, Random Variables, Expectation and Variance. The Markov inequality and the Chebyshev inequality. The LazySelect Algorithm. Analysis of LazySelect.

  5. 10/22/07: Review on the analysis of the LazySelect algorithm. The Sorting problem. Lower bound to the number of comparisons for comparisons-based sorting methods. A quadratic method: SelectionSort. RandomizedQuickSort. Average number of comparisons. Chernoff bound. Strong bounds for QuickSort. QuickSort and Binary Search Trees.

    Note: MT1 will be announced tomorrow, Tuesday, 23, 2007.


  6. 10/29/07 (notes revised 10/31): Multiplication of large integers. Sequences and polynomials. Multiplication and Convolution. Evaluation of a polynomial on a point. The Horner's method. Evaluation and Interpolation. The Vandermonde Transform. The Convolution Theorem.

  7. 11/5/07: MT Part II. Review of MTP2. DFT and FFT. Overview on design techniques.

  8. 11/19/07: The Closest Pair problem. Introduction to Dynamic Programming. Fibonacci revisited. Problem overlapping. Memoization. The matrix-chain multiplication problem. Optimal Substructure. Shortest path. The Floyd-Warshall algorithm.

  9. 11/26/07: Markov Chains and Hidden Markov Models.

Downloads

  1. Sorting
  2. orderstats
  3. topics list
  4. Least Squares Method
  5. MT

Announcements

  1. 10/15/2007: Today, Monday 15, office hours are canceled.

  2. 10/23/2007: The MT exam will be posted on Thursday morning before noon. It will be due on Monday before class.

  3. 11/08/2007: The topics list has been updated with the individual assignments.

  4. 11/12/2007: Today the campus is closed. There will be no class.

  5. 11/19/2007: calendar of presentations

  6. 11/19/2007: The deadline for HW and PJ is extended to next Monday.

  7. 11/25/2007: Tomorrow, Monday 26, office hours will be canceled.

  8. 11/27/2007: Location of Monday Presentations starting at 5pm: conference room, second floor.

  9. 11/30/2007: Location of Thursday Presentations starting at 5pm: room 220.

Assignments

  1. 10/12/07: cs512-f07-pj. Due Monday November 19, before class.

  2. 11/08/07: cs512-f07-hw. Due Monday, November 19, 2007, before class.

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.
  6. The Akra-Bazzi method.

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.