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)

syllabus

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 12, Intro. to graphs (Wednesday, March 6)

Worksheet 13 Graph search (Monday, March 11)

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

HW 1 (due Monday Jan. 29, at 11:59pm on Gradescope)

HW 2 (due Wednesday Feb. 7, at 11:59pm on Gradescope)

Bonus -- Proving the Master Theorem (due Feb. 23 at 11:59pm on Gradescope)

HW 3 (due Monday, March 4, at 11:59pm) 

HW 4 (due Wednesday, March 13, at 11:59pm)

HW 5 (due Wednesday, April 3 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