Course Notes .pdf file, Not complete and contains some typos/errors

Notes for 2nd semester algorithms course May cover some of this material in 4400 [in postscript]

Fall 2004 final Due 12/9 5pm

Fall 2005 final Due 5pm 12/8/05

Fall 2008 final Due 5pm 12/11/08

UPDATE 8/6/02. Primality testing has been proved to be solvable in (deterministic) polynomial time!!! Such an algorithm has been sought for hundreds of years. The algorithm is simple and the 9 page paper describing it can be found on the web (http://www.cse.iitk.ac.in/users/manindra/index.html).

Schedule: (all dates tentative until announced). Other assignments may be given in class.

Problems 0-2 Due T week 2: Sept 1

Problems 3-4 Due T week 3: Sept 8

Problems 5-10 Due T week 4: Sept 15

Problems 11-14 (problem 12 is optional) Due Th week 4: Sept 17

Problems 15-20 Due T week 5: Sept 22 (you can use Master Theorem if possible rather than induction or unfolding)

Problems 21-23 Due T week 6: Sept 29

Program 2 Due 5pm Fri week 6 10/2

EXAM 1 (do review problems!) T week 7: Oct 6

Problems 1-5 Due Th week 8: 10/15

Problems 6-7 Due T week 9: 10/20

Problems 10-12 Due Th week 9: 10/22

Problems 13-14 Due Th week 9: 10/22

Problems 16, 19-22, 24 T week 10: Due 10/27

EXAM 2 Th week 11: November 5 (do review problems!)

Problems 0, 0.1, 2, 4, 8, 10 Due: T week 13: 11/17

Program 14 Due 5pm Fri week 12, 11/13

Mini-paper Due Th of week 15: Dec 3

Graduate Paper due last class before finals

Final Exam: will either be take-home (in which case it is due by 5pm on the date of the scheduled final exam) or will be held at the time of the scheduled final exam.

Reading Schedule

Chazelle's essay

Appendix A of text by 9/1

Appendix B by 9/3

Sections 3.1-3.2 by 9/8