Princeton University
Computer Science Department

Computer Science 423
Theory of Algorithms

Bernard Chazelle

Spring 2012

COURSE INFORMATION | ASSIGNMENTS


COURSE DESCRIPTION

Description: This course is designed to provide students with an understanding of the principles and techniques used in the design and analysis of computer algorithms. 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 (polynomial-time) computations and infeasible computations.

Prerequisites: COS 226 and COS 340 or permission of the instructor

Lectures: MW 11:00-12:20, Room: FC 006

AI: Aman Dhesi, COS003, E-mail: adhesi AT cs..., office hours: Friday 4-5:30pm
AI: Omri Weinstein, COS416, E-mail: oweinste AT cs..., office hours: Thursday to 1:30-3:00pm
AI: Rajsekar Manokaran, COS417, E-mail: rajsekar AT cs...R, office hours: Wednesday 3-4:30pm



ADMINISTRATIVE INFORMATION

Instructor: Bernard Chazelle
Office: 404 CS Building, 258-5380
Office Hours: by arrangement
chazelle AT cs ...

Administrative Assistant: Mitra Kelly
Office: 323 CS Building, 258-4562
mkelly AT cs...

Undergraduate Coordinator: Colleen Kenny-McGinley
Office: 210 CS Building - 258-1746
ckenny AT cs ...

USEFUL SOURCES

CLRS: Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Third Edition, Addison-Wesley, 2009.

R. Sedgewick and K. Wayne, Algorithms, (Preliminary) Fourth Edition, Addison-Wesley, Fall, 2010, and previous editions, in particular R. Sedgewick, Algorithms in C, Third Edition, Parts 1-4, and Part 5, Addison-Wesley, 2002. (on reserve in the Engineering Library for COS 226)

Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., 1979.

Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, 1983.

Kleinberg and Tardos, Algorithm Design, 2005.



LECTURE MATERIALS

Fractional Cascading: I. A Data Structuring Technique, Algorithmica 1 (1986), 133-162.

Fractional Cascading: II. Applications, Algorithmica 1 (1986), 163-191.

Random lectures notes on FC: here and here.

Conjugation tree.

Low-cutting polygons.

Probability theory: pages 430-441.

Convex hull.

Polygon triangulation. (Notes by Jeff Erickson)

Voronoi diagrams. (Notes by Barr et al.)

Fortune's algorithm. (Notes from www.skynet.ie/~sos/mapviewer/docs/Voronoi_Diagram_Notes_1.pdf )

Markov chains.