EECS 376

EECS 376: Foundations of Computer Science

The University of Michigan

Winter 2024

Looking for Spring 2024 or 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.

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 Open Regular Calendar Open OH Calendar Open OH Schedule

Schedule

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

Day

Material and Readings in Notes

Deadline

Optional Readings*

Design and Analysis of Algorithms

Mon 8 Jan

No Class

Wed 10 Jan

L01

Introduction, The Potential Method 1 2

MM: 1, 2-2.2, Sip 7.1

Discussion

D01

Review: Proofs, Asymptotic Notation, Induction

Mon 15 Jan

No Class - MLK Day

Wed 17 Jan

L02

Divide and Conquer 1

HW1
8pm ET

MM: 2.3, 3-3.1, 3.2.1 (Mergesort)

Discussion

D02

Divide and Conquer

Mon 22 Jan

L03

Divide and Conquer 2

Wed 24 Jan

L04

Dynamic Programming 1

HW2
8pm ET

MM: 3.3-3.4

Discussion

D03

Divide and Conquer & Dynamic Programming

Mon 29 Jan

L05

Dynamic Programming 2

Wed 31 Jan

L06

Dynamic Programming 3

HW3
8pm ET

Discussion

D04

Dynamic Programming

Mon 5 Feb

L07

Greedy Algorithms

MM: 3.5

Computability

Wed 7 Feb

L08

Formal Languages and Finite Automata 1 2

HW4
8pm ET

Sip: 0.1, 1.1, 1.3

Discussion

D05

Greedy and Finite Automata

Mon 12 Feb

L09

Turing Machines and Decidability

Sip: 3.1, 3.2

Wed 14 Feb

L10

Diagonalization

HW5
8pm ET

Sip: 4.2

Discussion

D06

Turing Machines and Diagonalization

Mon 19 Feb

L11

The Acceptance and Halting Problems

Sip: 5.1, 5.3

Wed 21 Feb

L12

Reducibility

HW6
8pm ET

Sip: 5.2

Discussion

D07

Acceptance and Reducibility

Midterm

Mon 26 Feb

No Class - Spring Break

Wed 28 Feb

No Class - Spring Break

Discussion

No Class - Spring Break

Mon 4 Mar

L13

Midterm Review

Wed 6 Mar

L14

Midterm, 7-9pm ET

Midterm
7pm ET

Discussion

D08

TBD

Complexity

Mon 11 Mar

L15

The Classes P and NP

Sip: 7.2, 7.3

Wed 13 Mar

L16

The Cook-Levin Theorem

Sip: 7.4

Discussion

D09

NP Overview

Mon 18 Mar

L17

Reductions and NP-Completeness

Sip: 7.5

Wed 20 Mar

L18

NP-Complete Problems 2

HW7
8pm ET

Discussion

D10

NP-Completeness

Mon 25 Mar

L19

Search and Approximation Algorithms

Sip: 10.1

Wed 27 Mar

L20

Approximation Algorithms 2

HW8
8pm ET

Discussion

D11

Search and Approximation

Randomness in Computation

Mon 1 Apr

L21

Probability, Randomness in Computation

Wed 3 Apr

L22

Randomness in Computation 2

HW9
8pm ET

Discussion

D12

Randomness and Modular Arithmetic Review

Mon 8 Apr

L23

Randomness in Computation 3

Cryptography

Wed 10 Apr

L24

One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2

HW10
8pm ET

Sip: 10.6

Discussion

D11

Randomized Algorithms

Mon 15 Apr

L25

RSA and Factoring

Wed 17 Apr

L26

Zero-knowledge proofs

HW11
8pm ET

Discussion

D12

Intro to Cryptography

Special Topics

Mon 22 Apr

L27

Special Topcs (Untested Material)

Final Exam

Wed 24 Apr

No Class - End of Semester

Discussion

No Class - End of Semester

Wed 1 May

Final Exam, 7–9pm

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