EECS 376: Foundations of Computer Science

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

We're glad you're here. This semester all instruction will be live.

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


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

12pm-1:30pm MW

Chrys 220

Photo of Michal Derezinski
Michal Derezinski

4:30-6:00pm MW

DOW 1013

Photo of Ben Fish
Ben Fish

1:30pm-3:00pm MW

GGBL 2505

Photo of Seth Pettie
Seth Pettie

9:00-10:30am, 10:30am-noon MW

DOW 1013, FXB 1109

Photo of Yousif Askar
Yousif Askar

12:30pm F

IOE 1680

Photo of Nikki Dillmann
Nikki Dillmann

9:30am F

1017 Dow

Photo of Kaitlyn Fa
Kaitlyn Fa

4:30pm Th

GGBL 2153

Photo of Rose Gerson
Rose Gerson

9:30am F

GGBL 2153

Photo of Siddharth Parmar
Siddharth Parmar

9:30am F


Photo of Venkat Kannan
Venkat Kannan

9:30 F

DOW 2150

Photo of Junghwan Kim
Junghwan Kim

2:30pm Th

1005 Dow

Photo of Bryan Li
Bryan Li

10:30am F


Photo of Reese Liebman
Reese Liebman

2:30am F

GGBL 2153

Photo of Katherine McGraw
Katherine McGraw

11:30am Th

3150 Dow

Photo of Noah Peters
Noah Peters

12:30pm F

FXB 1024

Photo of Vikram Raghu
Vikram Raghu

11:30am F

CSRB 2246

Photo of Krithika Sethi
Krithika Sethi

5:30pm Th

3150 DOW

Photo of Eric Song
Eric Song

1:30pm F

3150 Dow

Photo of Elanor Tang
Elanor Tang

2:30pm F

DOW 1014

Photo of Daphne Tsai
Daphne Tsai

11:30am F

NAME 138

Photo of Jesse Tuglu
Jesse Tuglu

3:30pm Th

1018 Dow

Photo of Dingyu Wang
Dingyu Wang

3:30pm F

DOW 2150

Photo of John Xie
John Xie

4:30pm Th

GGBL 2147

Photo of Lily Yang
Lily Yang

12:30pm Th

EWRE 185