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 ·
office · East Hall 4839
office hours · Tues 9:00AM-11:30AM

· 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 ·

·1/2· No class. ·1/4· First day of class. Overview of class. Introduction to pseudocode and the long division algorithm.
·1/9· Preferential Matching and the Gale-Shapley Algorithm
·1/11· Preferential Matching and the Gale-Shapley Algorithm
·1/16· No class. MLK Day. ·1/18·
Basics of algorithm analysis
·1/23· Sorting things
(WS4,HW1+Sols due at 5pm)
(Add/Drop without W deadline!)
·1/25· Divide and Conquer I
·1/30· D&C II: The Master Theorem
·2/1· Generating functions and recurrence relations
(WS7,HW2+Sols due at 5pm)
·2/6· Closest pairs of points
·2/8· Roots of Unity and Polynomial Multiplication
·2/13· The discrete Fourier transform
(WS10,HW3+Sols due at 5pm)
·2/15· Exam 1
·2/20· The fast Fourier transform
·2/22· FFT review and intro to graphs
·2/27· No class. Spring break. ·3/1· No class. Spring break.
·3/6· Intro to graph search
·3/8· Applications of DFS
(WS14,HW4+Sols due Thurs at 5pm)
·3/13· Dijkstra's Algorithm
·3/15· Min-Cost Spanning Trees
·3/20· Greedy scheduling
(WS17,HW5+Sols due at 5pm)
·3/22· Exam 2
·3/27· Dynamic Programming I
·3/29· Dynamic Programming II
·4/3· Dynamic Programming III
·4/5·Intro to Probabilistic Algorithms
·4/10· Random Variables and Selection
(WS22,HW6+Sols due at 5pm)
·4/12·P = NP?
·4/17· Last day of class. Hamiltonian Cycles
·4/27· Final Exam · Thursday · 1:30-3:30pm.

· course information ·


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.


Your grade will be determined as follows.

• 10% engagement
• 10% quizzes
• 20% homework
• 15% exam 1
• 15% exam 2
• 30% final exam


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