Math 416, Winter 2024 homepage
Theory of algorithms
course information
location East Hall 3096
class time Monday & Wednesday, 11:30am-1pm
instructor Dr. Benjamin Gould (he/him)
call me Ben, or Prof. Gould
email brgould [at] umich [dot] edu
office East Hall 1859
office hours Tuesday 9:30-11:30am, Friday 1-2pm on zoom (see Canvas for the zoom link)
worksheets
Worksheet 1, Long division (Wednesday, Jan. 10)
Worksheet 2, Gale-Shapley (Monday, Jan. 15 & Wednesday, Jan. 22)
Worksheet 3, Algorithm analysis (Wednesday, Jan. 24)
Worksheet 4, Sorting (Monday, Jan. 29)
Worksheet 5, Divide & Conquer I (Monday, Feb. 5)
Worksheet 6, Divide & Conquer II (Wednesday, Feb. 7)
Worksheet 7, Generating functions (Wednesday, Feb. 7)
Worksheet 8, Closest pair of points (Monday, Feb. 12)
Worksheet 9, Polynomial multiplication (Monday, Feb. 19)
Worksheet 10, Discrete Fourier transform (Wednedsday, Feb. 21)
Worksheet 11, Fast Fourier transform (Monday, March 4)
Worksheet 14 Applications of DFS (Wednesday, March 13 & Monday, March 18)
Worksheet 15 Dijkstra's algorithm (Monday, March 25)
Worksheet 16 Min-cost spanning treees (Wednesday, March 27)
Worksheet 17 Greedy scheduling (Monday, April 1)
Worksheet 18 Dynamic Programming I (Wednesday, April 3)
Worksheet 19 Dynamic Programming II (Monday, April 8 & Wednesday, April 10)
Worksheet 20 Dynamic Programming III (Wednesday, April 10)
homework
Bonus -- Proving the Master Theorem (due Feb. 23 at 11:59pm on Gradescope)
HW 3 (due Monday, March 4, at 11:59pm)
HW 6 (due Wednesday, April 17, at 11:59pm)
calendar
Wednesday, Jan. 10 - Long divison (Worksheet 1)
Monday, Jan. 15 - No class, Martin Luther King Jr. Day
Wednesday, Jan. 17 - Gale-Shapley I (Worksheet 2)
Monday, Jan. 22 - Gale-Shapley II (Worksheet 2)
Wednesday, Jan. 24 - Intro to algorithm analysis (Worksheet 3)
Monday, Jan. 29 - Sorting (Worksheet 4) & Quiz 1
Wednesday, Jan. 31 - Divide & Conquer 1 (Worksheet 5)
Monday, Feb. 5 - Divide & Conquer 2 (Worksheet 6)
Wednesday, Feb. 7 - Generating functions (Worksheet 7)
Monday, Feb. 12 - Closest pairs (Worksheet 8)
Wednesday, Feb. 14 - Exam 1