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