CPS 230: Design and Analysis of Algorithms


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

August 26: our first class meeting.
October 7: the midterm is open books.
October 28: due date for Homework IV extended to Tuesday, November 4.
November 18: the final exam has been scheduled on Wednesday, December 10, from 2 to 5pm in the usual room. it is open book, same as the midterm.
November 25: here is a file that collects all lectures and homeworks in one document, Collection.pdf

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

[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.