CPS 230: Design and Analysis of Algorithms | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Term:
Fall 2008
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Time: Tue Thu 1:15 - 2:30 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Location: D106 LSRC | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Instructor: | Herbert Edelsbrunner |
Teaching Assistant: | Zhiqiang Gu |
announcements | schedule | references |
Date | Lecture Topic | Notes | Assignments |
Aug 26 Tue | 1 Introduction | Information [pdf] | |
I. DESIGN TECHNIQUES | |||
Aug 28 Thu | 2 Divide-and-Conquer | Lecture [pdf] | |
Sep 02 Tue | 3 Prune-and-Search | Lecture [pdf] | |
Sep 04 Thu | 4 Dynamic Programming | Lecture [pdf] | |
Sep 09 Tue | 5 Greedy Algorithms | Lecture [pdf] | Homework [pdf] |
II. SEARCHING | |||
Sep 11 Thu | 6 Binary Search Trees | Lecture [pdf] | |
Sep 16 Tue | 7 Red-black Trees | Lecture [pdf] | |
Sep 18 Thu | 8 Amortized Analysis | Lecture [pdf] | |
Sep 23 Tue | 9 Splay Trees | Lecture [pdf] | Homework [pdf] |
III. PRIORITIZING | |||
Sep 25 Thu | 10 Heaps and Heapsort | Lecture [pdf] | |
Sep 30 Tue | 11 Fibonacci Heaps | Lecture [pdf] | |
Oct 02 Thu | 12 Solving Recurrence Relations | Lecture [pdf] | Homework [pdf] |
Oct 07 Tue | midterm | Exam [pdf] | |
IV. GRAPH ALGORITHMS | |||
Oct 09 Thu | 13 Graph Search | Lecture [pdf] | |
Oct 16 Thu | 14 Shortest Paths | Lecture [pdf] | |
Oct 21 Tue | 15 Minimum Spanning Trees | Lecture [pdf] | |
Oct 23 Thu | 16 Union-find | Lecture [pdf] | Homework [pdf] |
V. TOPOLOGICAL ALGORITHMS | |||
Oct 28 Tue | 17 Geometric Graphs | Lecture [pdf] | |
Oct 30 Thu | 18 Surfaces | Lecture [pdf] | |
Nov 04 Tue | 19 Homology | Lecture [pdf] | Homework [pdf] |
VI. GEOMETRIC ALGORITHMS | |||
Nov 06 Thu | 20 Plane-Sweep | Lecture [pdf] | |
Nov 11 Tue | 21 Delaunay Triangulations | Lecture [pdf] | |
Nov 13 Thu | 22 Alpha Shapes | Lecture [pdf] | Homework [pdf] |
VII. NP-COMPLETENESS | |||
Nov 18 Tue | 23 Easy and Hard Problems | Lecture [pdf] | |
Nov 20 Thu | 24 NP-complete Problems | Lecture [pdf] | |
Nov 25 Tue | 25 Approximation Algorithms | Lecture [pdf] | Homework [pdf] |
Dec 10 Wed | final exam, 2-5pm |
[1] R. E. Tarjan. Data Structures and Network Algorithms. SIAM, Philadelphia, Pennsylvania, 1983. [2] J. Kleinberg and E. Tardos Algorithm Design. Pearson Education, Addison Wesley, Boston, Massachusetts, 2006. [3] R. L. Graham, D. E. Knuth and O. Patashnik. Concrete Mathematics. A Foundation for Computer Science. Addison-Wesley, Reading, Massachusetts, 1989.
announcements | schedule | references |