Princeton University Computer Science Department |
Computer Science 423
Theory of Algorithms Spring 2007 |
| COURSE INFORMATION | LECTURES | ASSIGNMENTS | |
|
COURSE INFORMATION
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. 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. Prerequisites: COS 226 and COS 341 or permission of the instructor Lectures: MW 11:00-12:20, Room: 105 Precept: Thurs 5:00-6:00 and Fri 10:00-11:00 (Pick one), Room: 105 Coursework: There will be about six problem sets based on material in the book or covered in lectures. The problems will range from easy to challenging. You should not necessarily expect to solve all parts of all problems, but you should read, think about, and try hard to solve all of them, allowing yourself plenty of time before the problems are due to think about and work on them. I reserve the right to give a mid-term, and /or a final project, each possibly for extra credit. Recommendations: Attend class. Much material covered will not be in the book, and I will present much material differently from the book. I will try to provide additional handouts on material not in the book. Read the Book. It is a basic source. Do the problem sets. Give yourself plenty of time for this. ADMINISTRATIVE INFORMATION Instructor: Robert Tarjan Office: 324 CS Building, 258-4797 Office Hours: 12:30-2:00pm and other times by appt Email: ret AT cs ... Teaching Assistant Wolfgang Mulzer Office: 417 CS Building, 258-6324 Office Hours: TTH 2:00-3:00 Email: wmulzer AT cs ... Teaching Assistant Janet Yoon Office: 223 CS Building , 258-0254 Office Hours: M 3:30-4:30 F 2:30-3:30 Email: jsyoon AT cs ... Secretary: Mitra Kelly Office: 323 CS Building, 258-4562 Email: mkelly AT cs... USEFUL LINKS Previous semester(s): Spring 2006 USEFUL SOURCES Sedgewick, Algorithms in C, Third Edition, Addison-Wesley. 1998. 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. Cupillari, The Nuts and Bolts of Proofs, PWS Publishing, 1993. Polya, How to Solve It, Princeton University Press, 1945. |
|