EECS 376: Foundations of Computer Science

The University of Michigan
Winter 2023
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, Winter 2023!

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

Office Hours Schedule

Open calendar in new window

Schedule

Day # Material and Readings in Notes Deadline Optional Readings*
Design and Analysis of Algorithms
Mon 2 Jan No Class
Wed 4 Jan L01 Introduction MM: 1, 2-2.2, Sip 7.1
Discussion D01 Review: Proofs, Asymptotic Notation, Information
Mon 9 Jan L02 The Potential Method and Divide and Conquer 1 2 MM: 2.3, 3-3.1, 3.2.1 (Mergesort)
Wed 11 Jan L03 Divide and Conquer 2
HW1
8pm ET
Discussion D02 Divide and Conquer
Mon 16 Jan No Class - MLK Day
Wed 18 Jan L04 Dynamic Programming
HW2
8pm ET
MM: 3.3-3.4
Discussion D03 Dynamic Programming
Mon 23 Jan L05 Dynamic Programming 2 and Greedy Algorithms MM: 3.5
Computability
Wed 25 Jan L06 Formal Languages and Finite Automata 1 2
HW3
8pm ET
Sip: 0.1, 1.1, 1.3
Discussion D04 Greedy Algorithms and Finite Automata
Mon 30 Jan L07 Turing Machines and Decidability Sip: 3.1, 3.2
Wed 1 Feb L08 Diagonalization
HW4
8pm ET
Sip: 4.2
Discussion D05 Turing Machines and Diagonalization
Mon 6 Feb L09 The Acceptance and Halting Problems Sip: 5.1, 5.3
Wed 8 Feb L10 Reducibility
HW5
8pm ET
Sip: 5.2
Discussion D06 Acceptance and Reducibility
Mon 13 Feb L11 Rice's Theorem
Midterm
Wed 15 Feb L12 Midterm Review
HW6
8pm ET
Discussion DMR Midterm Review
Mon 20 Feb Midterm
Midterm
7pm ET
Wed 22 Feb No Class
Discussion No Class
Mon 27 Feb No Class - Spring Break
Wed 1 Mar No Class - Spring Break
Discussion No Class - Spring Break
Complexity
Mon 6 Mar L13 The Classes P and NP Sip: 7.2, 7.3
Wed 8 Mar L14 The Cook-Levin Theorem Sip: 7.4
Discussion D07 NP Overview
Mon 13 Mar L15 Reductions and NP-Completeness Sip: 7.5
Wed 15 Mar L16 NP-Complete Problems 2
HW7
8pm ET
Discussion D08 NP-Completeness
Mon 20 Mar L17 Search and Approximation Algorithms Sip: 10.1
Wed 22 Mar L18 Approximation Algorithms 2
HW8
8pm ET
Discussion D09 Search and Approximation
Randomness in Computation
Mon 27 Mar L19 Probability, Randomness in Computation
Wed 29 Mar L20 Randomness in Computation 2
HW9
8pm ET
Discussion D10 Randomness and Modular Arithmetic Review
Mon 3 Apr L21 Randomness in Computation 3
Cryptography
Wed 5 Apr L22 One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2
HW10
8pm ET
Sip: 10.6
Discussion D11 Randomness and Intro to Cryptography
Mon 10 Apr L23 RSA and Factoring
Special Topics
Wed 12 Apr Special Topcs (Untested Material)
HW11
8pm ET
Final Exam
Discussion D12 RSA and Exam Review
Mon 17 Apr L24 Final Review
HW12
8pm ET
Wed 19 Apr No Class - End of Semester
Discussion No Class - End of Semester
Wed 26 Apr 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 Euiwoong Lee
Euiwoong Lee

euiwoong@umich.edu

12pm-1:30pm MW

1670 Beyster

Photo of Chris Peikert
Chris Peikert

cpeikert@umich.edu

3pm-4:30pm MW

1670 Beyster

Photo of Quentin Stout
Quentin Stout

qstout@umich.edu

4:30pm-6pm MW

1109 FXB

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

lezhu@umich.edu

12pm-1:30pm MW

Stamps Auditorium

Photo of Daniel Choo
Daniel Choo

dchoo@umich.edu

9:30am-10:30am F

1014 Dow

Photo of Nikki Dillmann
Nikki Dillmann

dillmann@umich.edu

5:30pm-6:30pm Th

2166 Dow

Photo of Junghwan Kim
Junghwan Kim

kimjhj@umich.edu

10:30am-11:30am F

2166 Dow

Photo of Samantha Liu
Samantha Liu

samzliu@umich.edu

2:30pm-3:30pm F

2150 Dow

Photo of Frankie Lizcano
Frankie Lizcano

flizcano@umich.edu

11:30am-12:30pm F

1018 Dow

Photo of Liz Loeher
Liz Loeher

loeher@umich.edu

3:30pm-4:30pm Th

1003 EECS

Photo of Peter Ly
Peter Ly

pmly@umich.edu

9:30am-10:30am Th

2153 GGBL

Photo of Claire McDermott
Claire McDermott

cemcd@umich.edu

12:30pm-1:30pm Th

1005 EECS

Photo of Siddharth Parmar
Siddharth Parmar

sidpar@umich.edu

Photo of Ajay Pillay
Ajay Pillay

apillay@umich.edu

3:30pm-4:30pm F

1010 Dow

🇸🇬 🪖
Photo of Samin Riasat
Samin Riasat

sriasat@umich.edu

Photo of Julie Shah
Julie Shah

jeshah@umich.edu

5:30pm-6:30pm Th

1017 Dow

Photo of Chad Sharp
Chad Sharp

cmlsharp@umich.edu

5:30pm-6:30pm Th

1200 EECS

Photo of Aditya Singhvi
Aditya Singhvi

singhvi@umich.edu

3:30pm-4:30pm F

1005 Dow

🪵
Photo of Ben Stensen
Ben Stensen

bstensen@umich.edu

4:30pm-5:30pm Th

1200 EECS

🇸🇪
Photo of Cooper Stevens
Cooper Stevens

coopstev@umich.edu

4:30pm-5:30pm Th

2166 Dow

Photo of Zhixiang Teoh
Zhixiang Teoh

zhteoh@umich.edu

1:30pm-2:30pm F

1017 Dow

Photo of Daphne Tsai
Daphne Tsai

dvtsai@umich.edu

3:30pm-4:30pm Th

1005 EECS

Photo of Ankith Udupa
Ankith Udupa

ankithu@umich.edu

12:30pm-1:30pm F

1017 Dow

Photo of Lily Yang
Lily Yang

lilyang@umich.edu

11:30am-12:30pm F

1008 FXB

Photo of Sam Zayko
Sam Zayko

szayko@umich.edu

4:30pm-5:30pm Th

1311 EECS