CS 212
|
Course Outline:
| Date | Lecture | Topics | Links/Notes |
|---|
| Jan 11, 2010 | Lecture 1 | Basic Principles of Algorithm Design and Analysis |
L1 Slides
L1 Handouts |
| Jan 18, 2010 | No class | MLK Day. |
HW1: PPTX PDF |
| Jan 25, 2010 | Lecture 2 | Data Structures: Stacks, queues, linked lists, graphs, trees, binary search trees, heaps |
L2 Slides
L2 Handouts |
| Feb 1, 2010 | Lecture 3 | Divide and Conquer Method: Overall technique, mergesort, quicksort, quickselect, (matrix multiplication), etc. |
HW1 Solution Excel
L3 Slides
L3 Handouts |
| Feb 8, 2010 | No class | Snowmeggedon. HW2 is available now (Due March 8th). Makeup day is April 27th, 2010. | HW2 PDF |
| Feb 15, 2010 | No class | President's Day. |
| Feb 22, 2010 | Lecture 4 | Greedy Method: Overall technique, the knapsack problem, optimal merge pattern, Union Find, minimum spanning tree, Huffman coding. |
L4 Slides
L4 Handouts |
| March 1, 2010 | Lecture 5 | Dynamic Programming: Overall technique, matrix chain problem, all-pairs shortest path problem, etc. |
L5 Slides
L5 Handouts |
| March 8, 2010 | | Mid Term Exam | HW2 Due |
| March 15, 2010 | | Spring break |
| March 22, 2010 | Lecture 6 | Graph Traversal Techniques: Tree traversal and applications, depth-dirst search, bread-first search, connectivity algorithms, biconnectivity algorithms, etc. | New links and new files will all appear on the course website, under the "File Storage" section. |
| March 29, 2010 | Lecture 7 | Graph Traversal Techniques (cont.), graph colorings, cliques, Hamiltonian cycles, etc. |
| March 31, 2010 | Lecture 8 | Branch and Bound method: Overall method, the 0/1 knapsack problem, the job assignment problem, the traveling salesman problem, etc. |
| April 5, 2010 | Lecture 9 | Introduction to the Theory of NP-completeness: Nondeterministic algorithms, complexity classes, NP-completeness, problem reduction, Specific NP-complete problems. |
| April 12, 2010 | Lecture 10 | Lower bound theory: Techniques for determining complexity lower bounds of problems, algorithm modeling, application to lower bound on sorting, searching, and merging. |
| April 19, 2010 | Lecture 11 | Facility Location problem and other overflow topics |
| April 26, 2010 | Lecture 12 | Union Find, B-Tree and other overflow topics |
| April 27, 2010 | Lecture 13 | Other overflow topics |
| May 3, 2010 | | Final Exam (Cumulative) |
|
|
|