**Theory of Algorithms · Math 416**

This course focuses on the design and analysis of algorithms from a mathematical perspective. We will begin with the basics of algorithm analysis, including proofs of correctness and running time, and some basic graph theory. We will discuss in depth three strategies for algorithm design: greedy algorithms, divide and conquer, and dynamic programming. The topics in the second half of the course may include network flow, NP-completeness and complexity, randomized algorithms, strategies for dealing with NP-hard problems, or other topics.

** · course information ·**

**location ·** Mason Hall 1437
**class time ·** Mon/Wed 11:30AM-1:00PM
**instructor ·** Dr. David Stapleton (he/him)
**call me ·** David or Professor Stapleton
**email ·** dajost@umich.edu
**office ·** East Hall 4839
**office hours ·** Tues 9:00AM-11:30AM
**syllabus**

**· worksheets ·**

WS1 · WS2 · WS3 · WS4 · WS5 · WS6 · WS7 · WS8 · WS9 · WS10 · WS11 · WS12· WS13· WS14· WS15· WS16· WS17· WS18· WS19· WS20· WS21· WS22· WS23· WS24

**· homework assignments ·**

HW1+Sols · HW2+Sols · HW3+Sols · HW4+Sols · HW5+Sols · HW6+Sols

**· calendar ·**

Monday | Wednesday |
---|---|

·1/2· No class. |
·1/4· First day of class. Overview of
class. Introduction to pseudocode and the long division
algorithm. (WS1) |

·1/9· Preferential
Matching and the Gale-Shapley Algorithm(WS2) |
·1/11· Preferential
Matching and the Gale-Shapley Algorithm
(WS2) |

·1/16· No class. MLK Day. |
·1/18· Basics of algorithm analysis (WS3) |

·1/23· Sorting things(WS4,HW1+Sols due at 5pm) (Add/Drop
without W
deadline!) |
·1/25· Divide and Conquer I(WS5) |

·1/30· D&C II: The
Master Theorem(WS6) |
·2/1· Generating functions and
recurrence relations (WS7,HW2+Sols due at 5pm) |

·2/6· Closest pairs of points (WS8) |
·2/8· Roots of Unity and Polynomial Multiplication(WS9) |

·2/13· The discrete Fourier transform(WS10,HW3+Sols due at 5pm) |
·2/15· Exam 1 |

·2/20· The fast Fourier transform(WS11) |
·2/22· FFT review and intro to graphs(WS12) |

·2/27· No class. Spring break. |
·3/1· No class. Spring break. |

·3/6· Intro to graph search(WS13) |
·3/8· Applications of DFS(WS14,HW4+Sols due Thurs at 5pm) |

·3/13· Dijkstra's Algorithm(WS15) |
·3/15· Min-Cost Spanning Trees(WS16) |

·3/20· Greedy scheduling(WS17,HW5+Sols due at 5pm) |
·3/22· Exam 2 |

·3/27· Dynamic Programming I(WS18) |
·3/29· Dynamic Programming II(WS19) |

·4/3· Dynamic Programming III(WS20) |
·4/5·Intro to Probabilistic Algorithms(WS21) |

·4/10· Random Variables
and Selection(WS22,HW6+Sols due at 5pm) |
·4/12·P = NP?(WS23) |

·4/17· Last day of class. Hamiltonian Cycles(WS24) |
·4/19· |

·4/27· Final Exam · Thursday · 1:30-3:30pm. |

**· course information ·**

**prerequisites**

Math 312 and 412 OR EECS 280 and Math 465.

**recommended textbooks**

Algorithms by Jeff Erickson. Freely available here.

**supporting textbooks**

Introduction to Algorithms, 3rd Edition by
Cormen, Leiserson, Rivest, and Stein.

**grades**

Your grade will be determined as follows.

• 10% engagement

• 10% quizzes

• 20% homework

• 15% exam 1

• 15% exam 2

• 30% final exam

**homework**

Homework will be assigned
weekly/biweekly and handed in on gradescope.