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.

See the syllabus for all the details.

Calendar   Regular Calendar OH Calendar OH Schedule

Day	#	Material and Readings in Notes	Deadline
Design and Analysis of Algorithms
Mon 5 Jan		No Class (Winter Break)
Wed 7 Jan	L01	Introduction, The Potential Method
Discussion	D01	Review: Proofs, Asymptotic Notation, Induction
Mon 12 Jan	L02	Divide and Conquer 1
Wed 14 Jan	L03	Divide and Conquer 2 1 2
Discussion	D02	Divide and Conquer
Mon 19 Jan		No Class (MLK Day)
Wed 21 Jan	L04	Dynamic Programming 1	HW1 8pm ET
Discussion	D03	Divide and Conquer & Dynamic Programming
Mon 26 Jan	L05	Dynamic Programming 2
Wed 28 Jan	L06	Dynamic Programming 3	HW2 8pm ET
Discussion	D04	Dynamic Programming
Mon 2 Feb	L07	Greedy Algorithms
Computability
Wed 4 Feb	L08	Formal Languages and Finite Automata 1 2	HW3 8pm ET
Discussion	D05	Greedy and Finite Automata
Mon 9 Feb	L09	Turing Machines and Decidability
Wed 11 Feb	L10	Diagonalization	HW4 8pm ET
Discussion	D06	Turing Machines and Diagonalization
Mon 16 Feb	L11	The Acceptance and Halting Problems
Wed 18 Feb	L12	Reducibility	HW5 8pm ET
Discussion	D07	Acceptance and Reducibility
Midterm
Mon 23 Feb	L13	Midterm Review	HW6 8pm ET Tuesday
Wed 25 Feb	L14	Special Topcs (Untested Material)
Wed 25 Feb		Midterm, 7-9pm ET	Midterm 7-9pm ET
Discussion		No Class (Midterm)
Mon 2 Mar		No Class (Spring Break)
Wed 4 Mar		No Class (Spring Break)
Discussion		No Class (Spring Break)
Complexity
Mon 9 Mar	L15	The Classes P and NP
Wed 11 Mar	L16	Reductions and NP-Completeness
Discussion	D08	NP Overview and PTMR Intro
Mon 16 Mar	L17	NP-Complete Problems 2
Wed 18 Mar	L18	The Cook-Levin Theorem	HW7 8pm ET
Discussion	D09	More PTMRs and The Cook-Levin Theorem
Mon 23 Mar	L19	Search and Approximation Algorithms
Wed 25 Mar	L20	Approximation Algorithms 2	HW8 8pm ET
Discussion	D10	Search and Approximation
Randomness in Computation
Mon 30 Mar	L21	Probability, Randomness in Computation
Wed 1 Apr	L22	Randomness in Computation 2	HW9 8pm ET
Discussion	D11	Randomness and Modular Arithmetic Review
Mon 6 Apr	L23	Randomness in Computation 3
Cryptography
Wed 8 Apr	L24	One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2	HW10 8pm ET
Discussion	D12	Randomized Algorithms
Mon 13 Apr	L25	RSA and Factoring
Wed 15 Apr	L26	Zero-knowledge proofs	HW11 8pm ET
Discussion	D13	Intro to Cryptography
Special Topics
Mon 20 Apr	L27	Special Topcs (Untested Material)
Final Exam
Tue 21 Apr		Last Day of Classes	HW12 8pm ET Tuesday
TBA		Final Review
Wed 29 Apr		Final Exam, 7-9pm ET	Final 7-9pm ET