Computer Science 31: Algorithms.    Fall 2008

Course Information

Course Overview

Computer scientists have developed beautiful and rich methods for designing algorithms and analyzing their performance. This course covers famous algorithms, algorithm design methods, and mathematical techniques for their analysis. We will look at algorithms for sorting and selecting, problems on graphs, and algorithm design paradigms. We will learn about the Theory of NP-Completeness and its implications.


Here is approximately week-by-week list of topics to be covered.  Expect changes, though: this schedule evolves according to student learning rates and interest levels.
  1. (Week of Sept 1). Algorithm analysis: definitions and notation. Sorting: Insertion Sort and perhaps Bubble Sort.

  2. (S8) Analysing recursion and induction; the Master Theorem. Sorting: Heapsort, Mergesort and Quicksort. Comparison of 4 sorting algorithms.

  3. (S15) Lower bounds on sorting.. Linear time sorting. Here are some sorting resources. The selection problem. Seletion in O(n) average case time; Selection in O(n) worst-case time.

  4. (S22) Divide and conquer algorithms. Multiplying large integers; Strassen's algorithm; Polynomial Multiplication and the FFT.

  5. (S29) More Divide and Conquer: The closest pair problem. Dynamic programming. Maximum sum subvector.

  6. (O6) Dynamic programming. Longest Common Subsequence. Optimal binary search trees. 0/1 Knapsack, Making Change greedily vs with dynamic programming.

  7. (O13) Fall Break. Practice designing algorithms according to paradigms. The optimal substructure property. Review for test. TEST FRIDAY on asymptotic analysis, sorting and searching, divide and conquer, dynamic programming.

  8. (O20) Greedy algorithms: Huffman's algorithm. Graph data structures; greedy algorithms on graphs: MST, SSSP.

  9. (O27) Dynamic programming algorithms for graphs: Bellman-Ford, Floyd's algorithm. Graphs and matrix operations (matrix multiplication and reachability/distance).

  10. (N3) Decorating graph traversal trees: BFS, DFS, topological sorting, strongly connected components, articulation points, biconnected components.

  11. (N10) Amortization. Simple examples. The Disjoint Set problem.

    (N17) Thanksgiving break

  12. (N24) Finish up graphs: applications, problem abstraction. Test this week on graphs, trees and amortization.

  13. (D1) Intractable problems. Definitions of P, NP, NP-complete, NP-Hard. Solving a problem vs verifying a problem. Problem transformations. Implications of NP-Completeness. Example problems and their status.

  14. (D8) Coping with NP-Hard problems: Constructive algorithms (for example for TSP); approximation algorithms; branch and bound; heuristic search; linear programming.

    Final Exam