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 340 or permission of the instructor
Lectures: MW 11:00-12:20 pm, Room: 105 CS Building
Precept: Tuesdays 7:00-8:30 pm, Room: 105 CS Building
Recommended text: CLRS: Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Second Edition, McGraw-Hill, 2001.
Recommendations: Attend class. Much material covered will not be in CLRS, and I will
present much material differently from CLRS. I will try to provide additional handouts on material not in CLRS.
Read CLRS. 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: MW 12:30-2:00pm and by Appt.
Email: ret AT cs ... or prof DOT tarjan AT gmail DOT com
Teaching Assistant: Siddhartha Sen
Office: 003 CS Building, 258-2072
Office Hours: Mon. 5:30-6:30pm, Tues. 6-7pm, and by Appt.
Email: sssix AT cs ...
Secretary: Mitra Kelly
Office: 323 CS Building, 258-4562
Email: mkelly AT cs ...
Sedgewick, Algorithms in Java, Third Edition, Parts 1-4, Addison-Wesley, 2003.
Sedgewick, Algorithms in Java, Third Edition, Part 5, Addison-Wesley, 2003.
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.
