EECS 376: Foundations of Computer Science

The University of Michigan
Fall 2021
Looking for the notes?

This is an archive of the Fall 2021 site. The current site is available here.

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 2021!

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 30 Aug L01 Introduction MM: 1, 2-2.2, Sip 7.1
Wed 1 Sep 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 6 Sep No Class - Labor Day
Wed 8 Sep L03 Divide and Conquer 2
8pm ET
Discussion D02 Divide and Conquer
Mon 13 Sep L04 Dynamic Programming MM: 3.3-3.4
Wed 15 Sep L05 Dynamic Programming 2 and Greedy Algorithms
8pm ET
MM: 3.5
Discussion D03 Dynamic Programming and Greedy
Mon 20 Sep L06 Formal Languages and Finite Automata 1 2 Sip: 0.1, 1.1, 1.3
Wed 22 Sep L07 Turing Machines and Decidability
8pm ET
Sip: 3.1, 3.2
Discussion D04 Finite Automata and Turing Machines
Mon 27 Sep L08 Diagonalization Sip: 4.2
Wed 29 Sep L09 The Acceptance and Halting Problems
8pm ET
Sip: 5.1, 5.3
Discussion D05 Diagonalization and Acceptance
Mon 4 Oct L10 Reducibility Sip: 5.2
Wed 6 Oct L11 Recognizability
8pm ET
Discussion D06 Reducibility and Undecidability
Mon 11 Oct L12 Rice's Theorem and Kolmogorov Complexity 1 2
Wed 13 Oct L13 Material Review
8pm ET
Discussion D07 Rice's Theorem and Material Review
Mon 18 Oct No Class - Fall Break
Wed 20 Oct Midterm
7pm ET
Discussion No Class - Midterm
Mon 25 Oct L14 The Classes P and NP Sip: 7.2, 7.3
Wed 27 Oct L15 The Cook-Levin Theorem Sip: 7.4
Discussion D08 NP Overview
Mon 1 Nov L16 Reductions and NP-Completeness Sip: 7.5
Wed 3 Nov L17 NP-Complete Problems 2
8pm ET
Discussion D09 NP-Completeness
Mon 8 Nov L18 Search and Approximation Algorithms Sip: 10.1
Wed 10 Nov L19 Approximation Algorithms 2
8pm ET
Discussion D10 Search and Approximation
Randomness in Computation
Mon 15 Nov L20 Probability, Randomness in Computation
Wed 17 Nov L21 Randomness in Computation 2
8pm ET
Discussion D11 Randomness and Modular Arithmetic Review
Mon 22 Nov L22 Chernoff Bounds and Polling 1 2
Wed 24 Nov No Class - Thanksgiving
Discussion No Class - Thanksgiving
Mon 29 Nov L23 One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2 Sip: 10.6
Wed 1 Dec L24 RSA and Factoring
8pm ET
Discussion D12 Fast Modular Exponentiation, Diffie-Hellman, and RSA
Special Topics
Mon 6 Dec Special Topics (Untested Material)
Final Exam
Wed 8 Dec L25 Wrap-up
8pm ET
Discussion D13 Wrap-up and Material Review
Wed 15 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 Amir Kamil
Amir Kamil

12pm-1:30pm MW

Stamps Auditorium

4:30pm-6pm MW

220 Chrysler

Photo of Euiwoong Lee
Euiwoong Lee

10:30am-12pm MW

1670 Beyster

Photo of Seth Pettie
Seth Pettie

1:30pm-3pm MW

1610 IOE

Photo of Ankith Udupa
Ankith Udupa

1:30pm-2:30pm Th

185 EWRE

Photo of Anzhelika Iugai
Anzhelika Iugai

11:30am-12:30pm Th

1006 Dow

Photo of Claire McDermott
Claire McDermott

2:30pm-3:30pm Th

1005 Dow

Photo of Cooper Stevens
Cooper Stevens

1:30pm-2:30pm F

3150 Dow

Photo of Dingyu Wang
Dingyu Wang

2:30pm-3:30pm F

1690 Beyster

Photo of Hrudit Shah
Hrudit Shah

4:00pm-5:00pm Th

104 EWRE

Photo of Isabella Qiao
Isabella Qiao

3:00pm-4:00pm Th

138 NAME

Photo of Jiahe Shang
Jiahe Shang

12:30pm-1:30pm Th

185 EWRE

Photo of Julie Shah
Julie Shah

2:30pm-3:30pm F

1018 Dow

Photo of Junghwan Kim
Junghwan Kim

2:30pm-3:30pm Th

2150 Dow

Photo of Lingxiao Guan
Lingxiao Guan

11:30am-12:30pm F

133 Chrysler

Photo of Mollie Bakal
Mollie Bakal

12:30pm-1:30pm F

1024 FXB

Photo of Owen Goebel
Owen Goebel

5:00pm-6:00pm Th

3150 Dow

Photo of Peter Ly
Peter Ly

9:30am-10:30am F

104 EWRE

Photo of Sam Zayko
Sam Zayko

10:30am-11:30am F

104 EWRE

Photo of Yuze Dai
Yuze Dai

3:30pm-4:30pm F

2150 Dow

4:30pm-5:30pm F

2150 Dow