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

Schedule

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
HW1
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
HW2
8pm ET
Wed 14 Sep L05 Dynamic Programming 2 and Greedy Algorithms MM: 3.5
Discussion D03 Dynamic Programming and Greedy
Computability
Mon 19 Sep L06 Formal Languages and Finite Automata 1 2 Sip: 0.1, 1.1, 1.3
Tue 20 Sep
HW3
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
HW4
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
HW5
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
HW6
8pm ET
Midterm
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
Midterm
7pm ET
Discussion No Class - Midterm
Complexity
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
HW7
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
HW8
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
HW9
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
Cryptography
Mon 28 Nov L23 One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2 Sip: 10.6
Tue 29 Nov
HW10
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
HW11
8pm ET
Final Exam
Wed 7 Dec L25 Wrap-up
Discussion D13 Wrap-up and Material Review
Wed 14 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 Nikhil Bansal
Nikhil Bansal

bansaln@umich.edu

1:30pm-3pm MW

2505 GGBL

Photo of Amir Kamil
Amir Kamil

akamil@umich.edu

12pm-1:30pm MW

Stamps Auditorium

3pm-4:30pm MW

1060 FMCRB

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

lezhu@umich.edu

12pm-1:30pm MW

2505 GGBL

Photo of Daniel Choo
Daniel Choo

dchoo@umich.edu

10:30am-11:30am F

G906 Cooley

Photo of Nikki Dillmann
Nikki Dillmann

dillmann@umich.edu

Photo of Yile Gu
Yile (Michael) Gu

yilegu@umich.edu

5:30pm-6:30pm Th

2150 Dow

Photo of Junghwan Kim
Junghwan Kim

kimjhj@umich.edu

11:30am-12:30pm F

1050 FMCRB

Photo of Samantha Liu
Samantha Liu

samzliu@umich.edu

2:30pm-3:30pm F

2153 GGBL

Photo of Frankie Lizcano
Frankie Lizcano

flizcano@umich.edu

11:30am-12:30pm Th

1005 EECS

Photo of Liz Loeher
Liz Loeher

loeher@umich.edu

9:30am-10:30am F

1200 EECS

Photo of Peter Ly
Peter Ly

pmly@umich.edu

3:30pm-4:30pm F

2150 Dow

Photo of Siddharth Parmar
Siddharth Parmar

sidpar@umich.edu

Photo of Ajay Pillay
Ajay Pillay

apillay@umich.edu

9:30am-10:30am F

1050 FMCRB

🇸🇬 🪖
Photo of Aditya Singhvi
Aditya Singhvi

singhvi@umich.edu

1:30pm-2:30pm Th

2147 GGBL

🪵
Photo of Cooper Stevens
Cooper Stevens

coopstev@umich.edu

11:30am-12:30pm F

133 Chrysler

Photo of Zhixiang Teoh
Zhixiang Teoh

zhteoh@umich.edu

12:30pm-1:30pm F

1024 FXB

Photo of Daphne Tsai
Daphne Tsai

dvtsai@umich.edu

4:30pm-5:30pm Th

2153 GGBL

Photo of Ankith Udupa
Ankith Udupa

ankithu@umich.edu

1:30pm-2:30pm F

3150 Dow

Photo of Ben Stensen
Ben Stensen

bstensen@umich.edu

2:30pm-3:30pm F

1018 Dow

🇸🇪
Photo of Lily Yang
Lily Yang

lilyang@umich.edu

3:30pm-4:30pm Th

1014 Dow

Photo of Sam Zayko
Sam Zayko

szayko@umich.edu

2:30pm-3:30pm Th

1005 Dow