# 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**

- Syllabus (pdf,
ps,
dvi)
- Insert-Sort Handout
(pdf,
ps,
dvi)
- Problem Set 1 (pdf,
ps,
dvi),
Solutions (pdf,
ps,
dvi)
- Problem Set 2 (pdf,
ps,
dvi),
Solutions (pdf,
ps,
dvi)
- Problem Set 3 (pdf,
ps,
dvi),
Solutions (pdf,
ps,
dvi)
- Problem Set 4 (pdf,
ps,
dvi),
Solutions (pdf,
ps,
dvi)
- Problem Set 5 (pdf,
ps,
dvi)
Solutions (pdf,
ps,
dvi)
- Problem Set 6 (pdf,
ps,
dvi)
- Midterm exam(pdf,
ps,
dvi)
Solutions (pdf,
ps,
dvi)
- Problem Set 7 (pdf,
ps,
dvi)
Solutions (pdf,
ps,
dvi)
- Problem Set 8 (pdf,
ps,
dvi)
Solutions (pdf,
ps,
dvi)
- Problem Set 9 (pdf,
ps,
dvi)
- Problem Set 10 (pdf,
ps,
dvi)

12/2/2002