EECS 376: Foundations of Computer Science

The University of Michigan
Winter 2025

An introduction to Computer Science theory, with applications. Design and analysis of algorithms, including paradigms such as divide-and-conquer and dynamic programming. Fundamentals of computability and complexity -- learn to identify what problems a computer cannot solve at all, what problems are unlikely to be efficiently solvable, and how to apply approximations to such problems. Introduction to randomness in computation, including how algorithms can benefit from randomness and how to analyze randomized algorithms. Applications of computational hardness to cryptography, including specific algorithms that are essential to the internet.

See the syllabus for all the details.

Welcome to EECS 376, Winter 2025!

We're glad you're here. This semester all instruction will be in person.

Make sure to have a laptop and a reliable internet connection.

More details in the syllabus.

Calendar   Regular Calendar OH Calendar

Schedule

Day # Material and Readings in Notes Deadline
Design and Analysis of Algorithms
Mon 6 Jan No Class
Wed 8 Jan L01 Introduction, The Potential Method
Discussion D01 Review: Proofs, Asymptotic Notation, Induction
Mon 13 Jan L02 Divide and Conquer 1
Wed 15 Jan L03 Divide and Conquer 2 1 2
HW1
8pm ET
Discussion D02 Divide and Conquer
Mon 20 Jan No Class - MLK Day
Wed 22 Jan L04 Dynamic Programming 1
HW2
8pm ET
Discussion D03 Divide and Conquer & Dynamic Programming
Mon 27 Jan L05 Dynamic Programming 2
Wed 29 Jan L06 Dynamic Programming 3
HW3
8pm ET
Discussion D04 Dynamic Programming
Mon 3 Feb L07 Greedy Algorithms
Computability
Wed 5 Feb L08 Formal Languages and Finite Automata 1 2
HW4
8pm ET
Discussion D05 Greedy and Finite Automata
Mon 10 Feb L09 Turing Machines and Decidability
Wed 12 Feb L10 Diagonalization
HW5
8pm ET
Discussion D06 Turing Machines and Diagonalization
Mon 17 Feb L11 The Acceptance and Halting Problems
Wed 19 Feb L12 Reducibility
Discussion D07 Acceptance and Reducibility
Midterm
Mon 24 Feb Midterm Review
HW6
8pm ET
Wed 26 Feb Special Topcs (Untested Material)
Thu 27 Feb Midterm, 7-9pm ET
Midterm
7pm ET
Discussion No Class
Mon 3 Mar L13 No Class - Spring Break
Wed 5 Mar L14 No Class - Spring Break
Discussion No Class - Spring Break
Complexity
Mon 10 Mar L15 The Classes P and NP
Wed 12 Mar L16 The Cook-Levin Theorem
Discussion D08 NP Overview
Mon 17 Mar L17 Reductions and NP-Completeness
Wed 19 Mar L18 NP-Complete Problems 2
HW7
8pm ET
Discussion D09 NP-Completeness
Mon 24 Mar L19 Search and Approximation Algorithms
Wed 26 Mar L20 Approximation Algorithms 2
HW8
8pm ET
Discussion D10 Search and Approximation
Randomness in Computation
Mon 31 Mar L21 Probability, Randomness in Computation
Wed 2 Apr L22 Randomness in Computation 2
HW9
8pm ET
Discussion D11 Randomness and Modular Arithmetic Review
Mon 7 Apr L23 Randomness in Computation 3
Cryptography
Wed 9 Apr L24 One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2
HW10
8pm ET
Discussion D12 Randomized Algorithms
Mon 14 Apr L25 RSA and Factoring
Wed 16 Apr L26 Zero-knowledge proofs
HW11
8pm ET
Discussion D13 Intro to Cryptography
Special Topics
Mon 21 Apr L27 Special Topcs (Untested Material)
Final Exam
Tue 22 Apr End of Semester
HW12
8pm ET
Wed 30 Apr Final Exam 7:00 - 9:00 PM
Final
7pm ET

People

Photo of Michal Derezinski
Michal Derezinski

derezin@umich.edu

4:30-6pm MW

1571 GGBL

Photo of Emily Graetz
Emily Graetz

graetzer@umich.edu

1:30-3pm MW

Stamps Auditorium

Photo of Seth Pettie
Seth Pettie

pettie@umich.edu

12-1:30pm MW

1013 Dow

Photo of Ishaan Arya
Ishaan Arya

iarya@umich.edu

4:30-5:30pm Th

2166 Dow

Photo of Yeyuan Chen
Yeyuan Chen

yeyuanch@umich.edu

3:30-4:30pm Th and 9:30-10:30am F

1005 EECS and 1003 EECS

Photo of Kaitlyn Fa
Kaitlyn Fa

kxfa@umich.edu

2:30-3:30pm F

2150 Dow

Photo of Eric Khiu
Eric Khiu

erickhiu@umich.edu

12:30-1:30pm Th

1005 EECS

Photo of Uma Kulkarni
Uma Kulkarni

umaku@umich.edu

3:30-4:30pm F

2150 Dow

Photo of Katherine McGraw
Katherine McGraw

katemcg@umich.edu

11:30am-12:30pm F

1018 Dow

Photo of Vikram Raghu
Vikram Raghu

vvraghu@umich.edu

5:30-6:30pm Th and 1:30-2:30pm F

1200 EECS and 1017 Dow

Photo of Jett Rosen
Jett Rosen

jettr@umich.edu

11:30am-12:30pm F

1008 FXB

Photo of Nikhil Shagrithaya
Nikhil Shagrithaya

nshagri@umich.edu

4:30-5:30pm Th and 10:30-11:30am F

1303 EECS and 2166 Dow

Photo of Michael Wang
Michael Wang

mitwang@umich.edu

12:30-1:30pm F

1017 Dow