Math 416, Theory of Algorithms

Fall 2002

Harm Derksen

The FINAL exam is on Monday, December 16, 4pm (until approx. 5pm). You are allowed a crib-sheet (or a cheat-sheet as I prefer to call it). The crib-sheet should be at most half a page (half of a single sided letter size piece of paper). You can bring a calculator as long as it is only used for addition, multiplication etc. You cannot use a calculator if it inverts a matrix for you. All rules are enforced. Problems will be similar to homework problems and problems in the book.

The topics of the final are essentially all topics discussed in class. To be precise, here is an overview: Chapter 2: everything, Chapter 3: everything except the part on iterated functions and iterated logarithm, Chapter 4: everything except section 4.4, Chapter 28: everything except section 28.5, Chapter 30: everything except section 30.3, Chapter 31: everything except 31.4. Chapter 22, Chapter 23, Chapter 26: up to 26.3, Chapter 34: up to Lemma 34.1 .

Place:
Changed To: 1060 East Hall

Time:
Monday, Wednesday, Friday, 10am-11am

My office is room 3067 East Hall.
The phone number is 763 2309
Email adress: hderksen@umich.edu.

Office hours:
Monday, 3-4pm
Thursday, 1-2pm
Or by appointment (call or email me)
You're Welcome!!!!!!!

Text: Introduction to Algorithms, second edition.
By:Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
The MIT Press/McGraw-Hill Book Company
ISBN 0-262-03293-7 (hardcover, MIT press)
ISBN 0-262-53196-8 (softcover)
(ISBN 0-07-013151-1 (Mc-Graw-Hill))
The book has about 1200 pages. Of course, only a fraction of the book will be discussed.

I intend to cover the following areas (not necessarily in this order):
growth of function, recurrences, some (but not all) sorting algorithms, dynamic programming, greedy aloorithms, some (but not all) graph algorithms, strassen matrix multiplication, fast fourier transform for polynomials, number theory algorithms such as prime testing, RSA cryptography and GCD, NP-completeness, traveling salesman problem.

Handouts/Problem Sets


12/2/2002