Princeton University Computer Science Department

Computer Science 423 Theory of Algorithms Kevin Wayne

Spring 2005

Course Summary

This course is designed to provide students with an understanding of the principles and techniques used in the design and analysis of computer algorithms. The course is primarily theoretical and does not require programming, but it does require understanding of the notion of a mathematical proof, some knowledge of elementary discrete mathematics, and mathematical problem-solving skills. We shall discuss and analyze a variety of data structures and algorithms chosen for their importance and their illustration of fundamental concepts. We shall emphasize analyzing the worst-case running time of an algorithm as a function of input size. We shall also spend some time exploring the boundary between feasible (polynominal-time) computations and infeasible computations. This will include discussion of the notorious P=NP? question.

Administrative Information

Lectures:   MW 11-12:20 · CS 104

Problem solving session:   M 8-9pm · COS 102.

Instructor:   Kevin Wayne · CS 207 · 258-4455 · wayne@cs

Teaching Assistant: Amit Agarwal · CS 313 · 258-6126 · aagarwal@cs

Teaching Assistant: Joshua Podolak · CS 103B · 258-0944 · jpodolak@cs

Course mailing list:   All students should sign up for the COS 423 mailing list.

Syllabus:   [pdf]

Office hours:

• Kevin: M 4-5, T 2:30-3:30, Th 3-4, or stop by CS 207.
• Amit: M 2-4pm in CS 313.
• Josh: T 4-6pm in CS 103B.

Announcements

• 3/27. No precept on 3/29.

• 2/15. You can use Whiteboard to check your grades. You will need to login using your OIT login and password. Note that the statistics whiteboard reports are for the entire class. When determining course grades, we will separate out undergrads and grads.

• 2/3. A copy of the Kleinberg-Tardos textbook is on reserve in the Engineering Library.