back to cs312-syllabus

CS312 - Teaching Material - Winter 2007

Lectures

  1. 1/3/07: Generalities on computational problems, models of computation and algorithms. The sorting problem. Decision Trees. Lower bound to the number of comparisons in the comparisons-based sorting problem. BubbleSort and MergeSort.


  2. 1/8/07: Loop invariants. The factorial algorithm. Proof of correctness and analysis of the computational complexity. Logarithms. Length of the representation of integer numbers.


  3. 1/10/07: Asymptotic notation.


  4. 1/17/07: The Divide-and-Conquer method. Recurrence relations of the Divide-and-Conquer type. Master Method. Linear recurrence relations of arbitrary order, homogeneous and inhomogeneous.


  5. 1/22/07: Summation formulas. Proofs by induction. Rooted trees. Binary trees. More on Sorting. Proof of the lower bound on the number of comparisons for the Sorting problem. Exercises on Linear recurrence relations.


  6. 1/24/07: The Horner method. Binary-to-decimal conversion. Exponentiation. The repeated squaring method.


  7. 1/29/07: Modular Exponentiation. Applications: the RSA cryptosystem and the Diffie-Hellman key exchange protocol. The sieve of Eratosthenes. The factoring problem. Graphs: basic definitions.

    Reading assignment: up to chapter 3.5.


  8. 1/31/07: The adjacency matrix of a graph. Graph isomorphisms. Paths and cycles. Hamiltonian and Eulerian cycles. The clique and the chromatic number. NP-complete problems.

    Preparation to the MT: Sample MT


  9. 2/5/07: Preparation to the MT

  10. 2/7/07: MT1

  11. 2/12/07: Review of MT1. Graph representations. Adjacency matrices and adjacency lists. Trees. Greedy Programming: the Kruskal Algorithm for the computation of Minimal Spanning Trees.

  12. 2/14/07: Disjoint Sets. Path Compression implementation. Union-Find implementation of the Kruskal's algorithm. Introduction to Heaps.

  13. 2/19/07: Heaps. Heapsort. Priority Queues.

  14. 2/21/07: DFS, testing connectivity of a graph, BFS, single-source multiple-destination shortest path. Backtracking algorithms.

  15. 2/26/07: Divide-and-conquer: closest pair.

  16. 2/28/07: MT2.

  17. 3/5/07: Review of MT2. Dynamic Programming. Matrix-Chain multiplication.

  18. 3/7/07: All-pairs shortest paths. The Floyd's algorithm. Transitive closure of a relation. The Warshall's algorithm.

  19. 3/12/07: Class summary. Note: the time of the final exam is 4:30-7:00pm.

Important Deadlines

  1. 2/7/2007: MT1. Sample MT
  2. 2/28/2007: MT2. Chapters 2-4, 5.2, 6.1-6.3, 7.2 (posted 2/21/07)

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.