EECS 376: Foundations of Computer Science

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.

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