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.