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 .
Changed To: 1060 East Hall
Monday, Wednesday, Friday, 10am-11am
My office is room 3067 East Hall.
The phone number is 763 2309
Email adress: email@example.com.
Or by appointment (call or email me)
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.