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. Syllabus

Calendar   Open Regular Calendar Open OH Calendar

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		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		MM: 3.3-3.4
Discussion	D02	Divide and Conquer
Tue 14 May	L05	Dynamic Programming 2
Wed 15 May	L06	Dynamic Programming 3
Discussion	D03	Dynamic Programming
Thu 16 May	L07	Greedy Algorithms	HW1 8pm ET	MM: 3.5
Computability
Mon 20 May	L08	Formal Languages and Finite Automata 1 2		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		Sip: 4.2
Discussion	D05	Turing Machines and Diagonalization
Thu 23 May	L11	The Acceptance and Halting Problems	HW2 8pm ET	Sip: 5.1, 5.3
Mon 27 May		No Class - Memorial Day
Tue 28 May	L12	Reducibility	HW3 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
Mon 10 Jun	L19	Search and Approximation Algorithms		Sip: 10.1
Discussion	D09	Search and Approximation
Tue 11 Jun	L20	Approximation Algorithms 2
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	HW4 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		Sip: 10.6
Wed 19 Jun		No Class - Juneteenth
Thu 20 Jun	L25	RSA and Factoring
Mon 24 June	L26	Zero-knowledge Proofs	HW5 8pm ET
Discussion	D12	Intro to Cryptography
Final Exam
Wed 26 June		Final Exam, 8-10am	Final 8am ET