EECS 376: Foundations of Computer Science

The University of Michigan
Fall 2022
Looking for previous terms?

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, Fall 2022!

We're glad you're here. We are planning for a primarily in-person semester. More details in the syllabus.

Make sure to have a laptop and a reliable internet connection. More details in the syllabus.

Open calendar in new window


Day # Material and Readings in Notes Deadline Optional Readings*
Design and Analysis of Algorithms
Mon 29 Aug L01 Introduction MM: 1, 2-2.2, Sip 7.1
Tue 30 Aug
Wed 31 Aug L02 The Potential Method and Divide and Conquer 1 2 MM: 2.3, 3-3.1, 3.2.1 (Mergesort)
Discussion D01 Review: Proofs, Asymptotic Notation, Information
Mon 5 Sep No Class - Labor Day
Tue 6 Sep
8pm ET
Wed 7 Sep L03 Divide and Conquer 2
Discussion D02 Divide and Conquer
Mon 12 Sep L04 Dynamic Programming MM: 3.3-3.4
Tue 13 Sep
8pm ET
Wed 14 Sep L05 Dynamic Programming 2 and Greedy Algorithms MM: 3.5
Discussion D03 Dynamic Programming and Greedy
Mon 19 Sep L06 Formal Languages and Finite Automata 1 2 Sip: 0.1, 1.1, 1.3
Tue 20 Sep
8pm ET
Wed 21 Sep L07 Turing Machines and Decidability Sip: 3.1, 3.2
Discussion D04 Finite Automata and Turing Machines
Mon 26 Sep L08 Diagonalization Sip: 4.2
Tue 27 Sep
8pm ET
Wed 28 Sep L09 The Acceptance and Halting Problems Sip: 5.1, 5.3
Discussion D05 Diagonalization and Acceptance
Mon 3 Oct L10 Reducibility Sip: 5.2
Tue 4 Oct
8pm ET
Wed 5 Oct L11 Recognizability
Discussion D06 Reducibility and Undecidability
Mon 10 Oct L12 Rice's Theorem and Kolmogorov Complexity 1 2
Tue 11 Oct
8pm ET
Wed 12 Oct L13 Material Review
Discussion D07 Rice's Theorem and Material Review
Mon 17 Oct No Class - Fall Break
Tue 18 Oct
Wed 19 Oct Midterm
7pm ET
Discussion No Class - Midterm
Mon 24 Oct L14 The Classes P and NP Sip: 7.2, 7.3
Tue 25 Oct
Wed 26 Oct L15 The Cook-Levin Theorem Sip: 7.4
Discussion D08 NP Overview
Mon 31 Oct L16 Reductions and NP-Completeness Sip: 7.5
Tue 1 Nov
8pm ET
Wed 2 Nov L17 NP-Complete Problems 2
Discussion D09 NP-Completeness
Mon 7 Nov L18 Search and Approximation Algorithms Sip: 10.1
Tue 8 Nov
8pm ET
Wed 9 Nov L19 Approximation Algorithms 2
Discussion D10 Search and Approximation
Randomness in Computation
Mon 14 Nov L20 Probability, Randomness in Computation
Tue 15 Nov
8pm ET
Wed 16 Nov L21 Randomness in Computation 2
Discussion D11 Randomness and Modular Arithmetic Review
Mon 21 Nov L22 Chernoff Bounds and Polling 1 2
Tue 22 Nov
Wed 23 Nov No Class - Thanksgiving
Discussion No Class - Thanksgiving
Mon 28 Nov L23 One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2 Sip: 10.6
Tue 29 Nov
8pm ET
Wed 30 Nov L24 RSA and Factoring
Discussion D12 Fast Modular Exponentiation, Diffie-Hellman, and RSA
Special Topics
Mon 5 Dec Special Topics (Untested Material)
Tue 6 Dec
8pm ET
Final Exam
Wed 7 Dec L25 Wrap-up
Discussion D13 Wrap-up and Material Review
Wed 14 Dec Final Exam
7pm ET
MM: The Nature of Computation by Cris Moore and Stephan Mertens, available online
Sip: Introduction to the Theory of Computation by Michael Sipser, 2nd or 3rd edition


Photo of Nikhil Bansal
Nikhil Bansal

1:30pm-3pm MW

2505 GGBL

Photo of Amir Kamil
Amir Kamil

12pm-1:30pm MW

Stamps Auditorium

3pm-4:30pm MW

1060 FMCRB

Photo of Leqi (Jimmy) Zhu
Leqi (Jimmy) Zhu

12pm-1:30pm MW

2505 GGBL

Photo of Daniel Choo
Daniel Choo

10:30am-11:30am F

G906 Cooley

Photo of Nikki Dillmann
Nikki Dillmann

Photo of Yile Gu
Yile (Michael) Gu

5:30pm-6:30pm Th

2150 Dow

Photo of Junghwan Kim
Junghwan Kim

11:30am-12:30pm F

1050 FMCRB

Photo of Samantha Liu
Samantha Liu

2:30pm-3:30pm F

2153 GGBL

Photo of Frankie Lizcano
Frankie Lizcano

11:30am-12:30pm Th

1005 EECS

Photo of Liz Loeher
Liz Loeher

9:30am-10:30am F

1200 EECS

Photo of Peter Ly
Peter Ly

3:30pm-4:30pm F

2150 Dow

Photo of Siddharth Parmar
Siddharth Parmar

Photo of Ajay Pillay
Ajay Pillay

9:30am-10:30am F

1050 FMCRB

🇸🇬 🪖
Photo of Aditya Singhvi
Aditya Singhvi

1:30pm-2:30pm Th

2147 GGBL

Photo of Cooper Stevens
Cooper Stevens

11:30am-12:30pm F

133 Chrysler

Photo of Zhixiang Teoh
Zhixiang Teoh

12:30pm-1:30pm F

1024 FXB

Photo of Daphne Tsai
Daphne Tsai

4:30pm-5:30pm Th

2153 GGBL

Photo of Ankith Udupa
Ankith Udupa

1:30pm-2:30pm F

3150 Dow

Photo of Ben Stensen
Ben Stensen

2:30pm-3:30pm F

1018 Dow

Photo of Lily Yang
Lily Yang

3:30pm-4:30pm Th

1014 Dow

Photo of Sam Zayko
Sam Zayko

2:30pm-3:30pm Th

1005 Dow