Computer Science 31

`www.cs.amherst.edu/ccm/cs31/`

Computer Science 31: Algorithms. Fall 2008

Course Information

The course instructor is Catherine McGeoch. My office is Room 401, Seeley Mudd Building. My phone number is x7913.
You can send me email at .
We meet MWTF at 9 am in Seeley Mudd 203.
Office hours: I am available for drop-in conversations Tuesday, Thursday at 1pm. You can set up an appointment for another time.
The required text is Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein. The book is available at the Jeffrey Amherst Bookshop. A copy is on reserve at the Science Library.
There will be two tests and a final exam, plus a small number of graded homework sets. In addition, there will be regular homework assignments, which will be reviewed in class but not formally graded. Your participation and effort with homework will be considered when making decisions about ``borderline'' final grades.
I will use CMS for sending email and grades, but you should visit this page (not CMS) for current syllabus 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.

Topics

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.

(Week of Sept 1). Algorithm analysis: definitions and notation. Sorting: Insertion Sort and perhaps Bubble Sort.
(S8) Analysing recursion and induction; the Master Theorem. Sorting: Heapsort, Mergesort and Quicksort. Comparison of 4 sorting algorithms.
(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.
(S22) Divide and conquer algorithms. Multiplying large integers; Strassen's algorithm; Polynomial Multiplication and the FFT.
(S29) More Divide and Conquer: The closest pair problem. Dynamic programming. Maximum sum subvector.
(O6) Dynamic programming. Longest Common Subsequence. Optimal binary search trees. 0/1 Knapsack, Making Change greedily vs with dynamic programming.
(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.
(O20) Greedy algorithms: Huffman's algorithm. Graph data structures; greedy algorithms on graphs: MST, SSSP.
(O27) Dynamic programming algorithms for graphs: Bellman-Ford, Floyd's algorithm. Graphs and matrix operations (matrix multiplication and reachability/distance).
(N3) Decorating graph traversal trees: BFS, DFS, topological sorting, strongly connected components, articulation points, biconnected components.
(N10) Amortization. Simple examples. The Disjoint Set problem.
(N17) Thanksgiving break
(N24) Finish up graphs: applications, problem abstraction. Test this week on graphs, trees and amortization.
(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.
(D8) Coping with NP-Hard problems: Constructive algorithms (for example for TSP); approximation algorithms; branch and bound; heuristic search; linear programming.
Final Exam