CPS 130: Introduction to the Design and Analysis of Algorithms

Lectures - Homework - Teaching Assistant - Forum

This course introduces algorithms that are of theoretical interest and of practical importance. It also discusses design paradigms, such as randomization and dynamic programming, and analysis techniques, such as probabilistic counting and amortization. The main topics are

Sorting
Searching
Paradigms
Advanced Data Structures
Graph Algorithms
String Algorithms
NP-Completeness

Prerequisites for this course are CPS 100 or equivalent and three semesters of college mathematics.

Lectures:		Mondays and Wednesdays 1:15 - 2:30 PM in room D106 LSRC Building.
Recitations:		Fridays 1:30 pm - 2:20 pm, 3:05 pm - 3:55 pm in room A155 LSRC Building.

Instructor:

	Professor Herbert Edelsbrunner
	Office:		D203 LSRC Building
	Phone:		(919) 660-6545
	Email:		edels@cs.duke.edu
	Web page:		www.cs.duke.edu/~edels
	Office hours:

There is a TA (Dmitriy Morozov) and a UTA (Larissa West) for this course. For details (office hours, etc.) see the TA page.

Course material:

Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms. McGraw Hill, second edition, 2001. Be sure to get the second edition!

The first two of the following books are recommended references on algorithms and the second two are recommended if you need help in refreshing your background in basic mathematics.

Tarjan. Data Structures and Network Algorithms. SIAM, 1983.
Aho, Hopcroft and Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Matousek and Nesetril. Invitation to Discrete Mathematics. Oxford University Press, 1998.
Graham, Knuth and Patashnik. Concrete Mathematics. A Foundation for Computer Science. Addison-Wesley, 1989.

CPS130 Forum is available for questions, announcements, and general discussion.

Anonymous comments

Last Modified: Monday, 30-Aug-2004 14:17:10 EDT