EECS 376

EECS 376: Foundations of Computer Science

The University of Michigan

Fall 2024

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.

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

Make sure to have a laptop and a reliable internet connection.

More details in the syllabus.

Calendar Regular Calendar OH Calendar OH Schedule

Schedule

Day	#	Material and Readings in Notes	Deadline
Design and Analysis of Algorithms
Mon 26 Aug	L01	Introduction, the Potential Method 1 2
Wed 28 Aug	L02	Divide and Conquer 1
Discussion	D01	Review: Asymptotic Notation, Proofs, Induction
Mon 2 Sep		No class — Labor Day
Wed 4 Sep	L03	Divide and Conquer 2	HW1 8pm ET
Discussion	D02	Divide and Conquer
Mon 9 Sep	L04	Dynamic Programming 1 1 2 3
Wed 11 Sep	L05	Dynamic Programming 2 1 2	HW2 8pm ET
Discussion	D03	Dynamic Programming
Mon 16 Sep	L06	Dynamic Programming 3 (graph algorithms)
Wed 18 Sep	L07	Greedy Algorithms	HW3 8pm ET
Discussion	D04	Greedy Algorithms and Graph DP
Computability
Mon 23 Sep	L08	Formal Languages and Finite Automata 1 2 3
Wed 25 Sep	L09	Turing Machines and Decidability	HW4 8pm ET
Discussion	D05	Finite Automata and Turing Machines
Mon 30 Sep	L10	Diagonalization
Wed 2 Oct	L11	"Natural" Undecidable Problems	HW5 8pm ET
Discussion	D06	Diagonalization and Intro to Turing Reductions
Mon 7 Oct	L12	Turing Reductions and More Undecidable Problems
Wed 9 Oct	L13	Recognizability	HW6 8pm ET
Discussion	D07	Reductions and Recognizability
Midterm
Mon 14 Oct		No class — Fall Break
Wed 16 Oct	L14	Midterm review
Thu 17 Oct			HW7 8pm ET
Discussion	D08	Midterm Review
Mon 21 Oct		No class — Midterm 7-9pm	Midterm 7pm ET
Complexity
Wed 23 Oct	L15	The Classes P and NP, Satisfiability 1 2
Discussion	D09	P and NP Overview
Mon 28 Oct	L16	NP-Completeness and P vs NP
Wed 30 Oct	L17	More NP-Complete Problems
Discussion	D10	NP-Completeness
Mon 4 Nov	L18	The Cook-Levin Theorem
Wed 6 Nov	L19	Search and Approximation Algorithms 1	HW8 8pm ET
Discussion	D11	Cook-Levin, Search and Approximation
Mon 11 Nov	L20	Approximation Algorithms 2
Randomness in Computation
Wed 13 Nov	L21	Probability, Randomness in Computation 1	HW9 8pm ET
Discussion	D12	Approx Algs and Randomness Intro
Mon 18 Nov	L22	Randomness in Computation 2
Wed 20 Nov	L23	Randomness in Computation 3	HW10 8pm ET
Discussion	D13	Randomness and Modular Arithmetic Review
Cryptography
Mon 25 Nov	L24	One-time Pad, Discrete Logarithm, and Diffie-Hellman 1 2
Wed 27 Nov		No class — Thanksgiving	HW11 8pm ET
Discussion		No discussion — Thanksgiving
Mon 2 Dec	L25	Factoring and RSA
Wed 4 Dec	L26	Zero Knowledge
Discussion	D14	Cryptography
Special Topics
Mon 9 Dec	L27	Special Topics (Untested Material)	HW12 8pm ET
Final Exam
Fri Dec 13		Final Exam, 7–9pm	Final 7pm ET

Day

Material and Readings in Notes

Deadline

Design and Analysis of Algorithms

Mon 26 Aug

L01

Introduction, the Potential Method 1 2

Wed 28 Aug

L02

Divide and Conquer 1

Discussion

D01

Review: Asymptotic Notation, Proofs, Induction

Mon 2 Sep

No class — Labor Day

Wed 4 Sep

L03

Divide and Conquer 2

HW1
8pm ET

Discussion

D02

Divide and Conquer

Mon 9 Sep

L04

Dynamic Programming 1 1 2 3

Wed 11 Sep

L05

Dynamic Programming 2 1 2

HW2
8pm ET

Discussion

D03

Dynamic Programming

Mon 16 Sep

L06

Dynamic Programming 3 (graph algorithms)

Wed 18 Sep

L07

Greedy Algorithms

HW3
8pm ET

Discussion

D04

Greedy Algorithms and Graph DP

Computability

Mon 23 Sep

L08

Formal Languages and Finite Automata 1 2 3

Wed 25 Sep

L09

Turing Machines and Decidability

HW4
8pm ET

Discussion

D05

Finite Automata and Turing Machines

Mon 30 Sep

L10

Diagonalization

Wed 2 Oct

L11

"Natural" Undecidable Problems

HW5
8pm ET

Discussion

D06

Diagonalization and Intro to Turing Reductions

Mon 7 Oct

L12

Turing Reductions and More Undecidable Problems

Wed 9 Oct

L13

Recognizability

HW6
8pm ET

Discussion

D07

Reductions and Recognizability

Midterm

Mon 14 Oct

No class — Fall Break

Wed 16 Oct

L14

Midterm review

Thu 17 Oct

HW7
8pm ET

Discussion

D08

Midterm Review

Mon 21 Oct

No class — Midterm 7-9pm

Midterm
7pm ET

Complexity

Wed 23 Oct

L15

The Classes P and NP, Satisfiability 1 2

Discussion

D09

P and NP Overview

Mon 28 Oct

L16

NP-Completeness and P vs NP

Wed 30 Oct

L17

People

sdexter@umich.edu

Workshop: 4:30-6pm Tue/Thu

cpeikert@umich.edu

10:30am-12pm and 12-1:30pm Mon/Wed

220 Chrysler

nswein@umich.edu

3-4:30pm MW

1013 Dow

iarya@umich.edu

2:30-3:30pm F

2153 GGBL

kxfa@umich.edu

2:30-3:30pm F

1014 Dow

mjjiang@umich.edu

vrkannan@umich.edu

2:30-3:30pm Th

1005 Dow

erickhiu@umich.edu

12:30-1:30pm Th

1690 Beyster

umaku@umich.edu

9:30-10:30am F

1690 Beyster

liebmanr@umich.edu

11:30am-12:30pm F

185 EWRE

anthliu@umich.edu

4:30-5:30pm Th and 3:30-4:30pm F

2153 GGBL and 2150 Dow

emilymaa@umich.edu

10:30-11:30am F

1206 Dow

katemcg@umich.edu

9:30-10:30am Th

1017 Dow

teomi@umich.edu

4:30-5:30pm Th

2147 GGBL

muskaan@umich.edu

11:30am-12:30pm F

1303 EECS

nalamsai@umich.edu

vvraghu@umich.edu

11:30am-12:30pm F

1024 FXB

jettr@umich.edu

9:30-10:30am F

1013 Dow

mitwang@umich.edu

1:30-2:30pm F

3150 Dow

zhixuanw@umich.edu

5:30-6:30pm Th

3150 Dow

johnxie@umich.edu

3:30-4:30pm Th

1018 Dow