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