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

Announcements

Schedule

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    

References

[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


Herbert Edelsbrunner (edels@cs.duke.edu) April 2008