back to cs312-syllabus

CS312 - Teaching Material - Winter 2006

Lectures

  1. 1/4/06: Basic definitions: algorithm, computational problem, problem solution. The analysis of algorithms: correctness and complexity. Models of computation. Example: multiplication of arbitrary integers and the calculation of the integer powers of a rational number.


  2. 1/9/06: Mathematical preliminaries: summation formulae, logarithms, binary representation of integers. Analysis of algorithms: modular exponentiation and sorting. Repeated squaring method and Insertion Sort.


  3. 1/11/06: Timing Java methods. Parameter estimation: the Least Squares Method. Asymptotic notation.


  4. 1/18/06: The Divide-and-Conquer design technique. Mergesort. Analysis of Mergesort. The master method.

    Textbook: cp 2.



  5. 1/23/06: Graphs. BFS. The coloring problem. Backtracking algorithms.

    Textbook: cp 2 (all).



  6. 1/25/06: MT1.


  7. 1/30/06: Review of MT1. Bounding summations: the method of the integral. Harmonic numbers. Exercises on the Master method.


  8. 2/1/06: Eulerian graphs, Hamiltonian graphs, graph isomorphisms, graph colorings, vertex covers, independent sets, cliques. Trees.


  9. 2/6/2006: In-class test.


  10. 2/8/2006: Review of the exam. A greedy approximation solution and its analysis.


  11. 2/13/2006: A close view of the VC problem. The class NP. Many-one polynomial time reductions. The Satisfiability (SAT) problem. NP-completeness. The P vs NP question. Adt's: specification and implementation. Java interfaces and Java classes.


  12. 2/15/2006: Priority Queues. Heaps. HeapSort.


  13. 2/20/2006: Graduate Studies Workshop.


  14. 2/22/2006: More on NP-completeness. Decision problems and languages. Statement of Cook's Theorem. Polynomial time reductions. Proofs of NP-completeness: SAT <=p 3-SAT and 3-SAT <=p IndependentSet.


  15. 2/27/2006: IndependentSet and Clique. Coping with NP-Completeness: Vertex Cover revisited. Design techniques: Greedy Programming. The Minimal Spanning Tree problem. The Kruskal's algorithm. Correctness of the Kruskal's algorithm. Introduction to the Union-Find data structure.


  16. 3/1/2006: MT2.


  17. 3/6/2006: Review of MT2.


  18. 3/8/2006: Union-Find Data Structures. Path compression. Sorted and unsorted Dictionaries. Hashtables and Binary Search Trees. The issue of balancing.


  19. 3/13/2006: Dynamic Programming. Principle of Suboptimality. The Matrix-chain multiplication problem. Analysis of the solution.

Packages

  1. ModularExponentiation
  2. graph
  3. backtracking
  4. sequences
  5. VertexCover
  6. priorityq
  7. disjointsets
  8. balancedtrees

Assignments

  1. 1/11/2006: cs312-w06-hw1, due Wed, Jan 18, 2006 before class.

Important Deadlines

  1. 1/25/2006: MT1. Topics: analysis of algorithms, loop invariants, asymptotic notation, master method, backtracking algorithms, graphs, basic searching and sorting. Sample MT1.


  2. 2/6/2006: In-class test.


  3. 3/15/06: Final. See mt2.