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