back to cs312-syllabus

CS312 - Teaching Material - Spring 2005

Lectures

  1. 3/28/05: Generalities on algorithms, models of computation, cost criteria and complexity analysis. An example: Bubble Sort, a quadratic algorithm for the sorting problem.

    Textbook: cp. 1.



  2. 3/30/05: Test.


  3. 4/4/05: Summation formulae. Logarithms. Binary representation of integers.

    Textbook: cp. 2.1. 2.2.



  4. 4/6/05: Loop invariants. Examples. Computing integer powers of a number. Analysis and implementation of the repeated squaring method.

    Textbook: cp. 2.2 (all).



  5. 4/11/05: Modular Exponentiation. A comparative experimental analysis of the repeated squaring method versus the naive exponentially slower method.

    Textbook: cp. 2.2 (all).



  6. 4/13/05: Analysis of algorithms and asymptotic notation.

    Textbook: cp. 2.3.



  7. 4/18/05: More on asymptotic notation. Parameter estimation. The Least Squares method.

    Textbook: cp. 2.3. (all)



    8. 4/20/05: Midterm 1.

  8. 4/25/05: Review of the Midterm Examination. Divide and Conquer. Mergesort.

    Textbook: cp. 2.4



  9. 4/27/05: Analysis of Mergesort. Divide-and-conquer recurrence relations. The master method.

    Textbook: cp. 2.4 (all), 5.2



  10. 5/2/05: Data Structures: specification and implementation. Use of Java interfaces. Stacks and Queues: Array and Linked List implementation. Circular buffers. DEQueues.

    Textbook: cp. 3.1,3.2,3.3.



  11. 5/4/05: Review on loop invariants. The Priority Queue Adt.

    Textbook: cp. 3.5



  12. 5/9/05: Binary min-heaps and max-heaps. Heap-based implementation of the Priority Queue Adt.

    Textbook: cp. 3.5 (all)



  13. 5/11/05: Graphs and Trees. Adjancency matrix representation. Adjacency lists. Rooted trees. The Dictionary Adt. Array implementation and binary search.

    Textbook: cp. 2.5,2.6,4.1



  14. 5/16/05: Midterm 2 (part I). Binary Search Trees (BST). BST implementation of the Dictionart Adt. Insertion in BST. Discussion on balancing issues.

    Textbook: cp. 3.4



  15. 5/18/05: Midterm 2, Part II.


  16. 5/23/05: Review of the Midterm. Cancellation in BST.


  17. 5/25/05: Greedy Programming. The Single source-All destinations Shortest Paths Problem. The Dijkstra Algorithm. Determining a Minimal Spanning Tree in a graph. The Kruskal's algorithm. The DisjointSets Adt.


  18. 1/1/05: The DisjointSets Data Structure. Path Compression implementation. Application to the implementation of the Kruskal's algorithm. Dynamic Programming. The principle of suboptimality. The matrix chain multiplication problem and its solution.

Packages

  1. timer
  2. CompModexp
  3. priorityq
  4. balancedtrees
  5. disjointsets

Assignments

  1. hw1
  2. test (old)
  3. hw2
  4. hw3 (due Monday, Apr 18, before class)
  5. hw4 (due Wednesday, May 4, before class)

Important Deadlines

  1. Midterm 1:Wednesday, Apr 20th, 2005. Topics: up to 2.3 (inclusive): analysis of algorithms, loop invariants, asymptotic notation.

  2. Midterm 2 (part 1, theory): Monday, May 16th, 2005. Topics: cp.1-3, mathematical preliminaries, analysis of algorithms, loop invariants, asymptotic notation, master method.

  3. Midterm 2 (part 2, programming): Wednesday, May 18th, 2005. Topics: cp 1-3. Data Structures: stacks, queues, priority queues, binary search trees.

  4. Final: Part I: asymptotic notation, master method, heaps. Part II: dynamic programming, memoization, graphs, bfs.

    Solutions: graph (updated) and matrixchain