EECS 376: Foundations of Computer Science

The University of Michigan
Fall 2021
Looking for the notes?

Winter 2022 Students: This is the Fall 2021 site. The Winter 2022 site is 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

Schedule

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
HW1
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
HW2
8pm ET
MM: 3.5
Discussion D03 Dynamic Programming and Greedy
Computability
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
HW3
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
HW4
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
HW5
8pm ET
Discussion D06 Reducibility and Undecidability
Mon 11 Oct L12 Rice's Theorem and Kolmogorov Complexity 1 2
Midterm
Wed 13 Oct L13 Material Review
HW6
8pm ET
Discussion D07 Rice's Theorem and Material Review
Mon 18 Oct No Class - Fall Break
Wed 20 Oct Midterm
Midterm
7pm ET
Discussion No Class - Midterm
Complexity
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
HW7
8pm ET
Discussion D09 NP-Completeness
Mon 8 Nov L18 Search and Approximation Algorithms Sip: 10.1
Wed 10 Nov L19 Approximation Algorithms 2
HW8
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
HW9
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
Cryptography
Mon 29 Nov L23 One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2 Sip: 10.6
Wed 1 Dec L24 RSA and Factoring
HW10
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
HW11
8pm ET
Discussion D13 Wrap-up and Material Review
Wed 15 Dec Final Exam
Final
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

People

Photo of Amir Kamil
Amir Kamil

akamil@umich.edu

12pm-1:30pm MW

Stamps Auditorium

4:30pm-6pm MW

220 Chrysler

Photo of Euiwoong Lee
Euiwoong Lee

euiwoong@umich.edu

10:30am-12pm MW

1670 Beyster

Photo of Seth Pettie
Seth Pettie

pettie@umich.edu

1:30pm-3pm MW

1610 IOE

Photo of Ankith Udupa
Ankith Udupa

ankithu@umich.edu

1:30pm-2:30pm Th

185 EWRE

Photo of Anzhelika Iugai
Anzhelika Iugai

aiugai@umich.edu

11:30am-12:30pm Th

1006 Dow

🪆
Photo of Claire McDermott
Claire McDermott

cemcd@umich.edu

2:30pm-3:30pm Th

1005 Dow

Photo of Cooper Stevens
Cooper Stevens

coopstev@umich.edu

1:30pm-2:30pm F

3150 Dow

Photo of Dingyu Wang
Dingyu Wang

wangdy@umich.edu

2:30pm-3:30pm F

1690 Beyster

Photo of Hrudit Shah
Hrudit Shah

hrudit@umich.edu

4:00pm-5:00pm Th

104 EWRE

Photo of Isabella Qiao
Isabella Qiao

xinyiq@umich.edu

3:00pm-4:00pm Th

138 NAME

Photo of Jiahe Shang
Jiahe Shang

jiahesh@umich.edu

12:30pm-1:30pm Th

185 EWRE

Photo of Julie Shah
Julie Shah

jeshah@umich.edu

2:30pm-3:30pm F

1018 Dow

Photo of Junghwan Kim
Junghwan Kim

kimjhj@umich.edu

2:30pm-3:30pm Th

2150 Dow

Photo of Lingxiao Guan
Lingxiao Guan

lxguan@umich.edu

11:30am-12:30pm F

133 Chrysler

Photo of Mollie Bakal
Mollie Bakal

bakalm@umich.edu

12:30pm-1:30pm F

1024 FXB

Photo of Owen Goebel
Owen Goebel

oagoebel@umich.edu

5:00pm-6:00pm Th

3150 Dow

Photo of Peter Ly
Peter Ly

pmly@umich.edu

9:30am-10:30am F

104 EWRE

Photo of Sam Zayko
Sam Zayko

szayko@umich.edu

10:30am-11:30am F

104 EWRE

Photo of Yuze Dai
Yuze Dai

yuzedai@umich.edu

3:30pm-4:30pm F

2150 Dow

4:30pm-5:30pm F

2150 Dow