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.

Open calendar in new window

Open calendar in new window

Day	#	Material and Readings in Notes	Deadline	Optional Readings*
Design and Analysis of Algorithms
Mon 28 Aug	L01	Introduction, The Potential Method 1 2		MM: 1, 2-2.2, Sip 7.1
Wed 30 Aug	L02	Divide and Conquer 1		MM: 2.3, 3-3.1, 3.2.1 (Mergesort)
Discussion	D01	Review: Proofs, Asymptotic Notation, Information
Mon 4 Sep		No Class - Labor Day
Wed 6 Sep	L03	Divide and Conquer 2	HW1 8pm ET
Discussion	D02	Divide and Conquer
Mon 11 Sep	L04	Dynamic Programming 1		MM: 3.3-3.4
Wed 13 Sep	L05	Dynamic Programming 2	HW2 8pm ET
Discussion	D03	Dynamic Programming
Mon 18 Sep	L06	Greedy Algorithms		MM: 3.5
Computability
Wed 20 Sep	L07	Formal Languages and Finite Automata 1 2	HW3 8pm ET	Sip: 0.1, 1.1, 1.3
Discussion	D04	Greedy Algorithms and Finite Automata
Mon 25 Sep	L08	Turing Machines and Decidability		Sip: 3.1, 3.2
Wed 27 Sep	L09	Diagonalization	HW4 8pm ET	Sip: 4.2
Discussion	D05	Turing Machines and Diagonalization
Mon 2 Oct	L10	The Acceptance and Halting Problems		Sip: 5.1, 5.3
Wed 4 Oct	L11	Reducibility	HW5 8pm ET	Sip: 5.2
Discussion	D06	Acceptance and Reducibility
Mon 9 Oct	L12	Rice's Theorem & Kolmogorov Complexity
Midterm
Wed 11 Oct	L13	Midterm Review	HW6 8pm ET
Discussion	DMR	Midterm Review
Mon 16 Oct		No Class - Fall Break
Wed 18 Oct		Midterm	Midterm 7pm ET
Discussion
Complexity
Mon 23 Oct	L14	The Classes P and NP		Sip: 7.2, 7.3
Wed 25 Oct	L15	The Cook-Levin Theorem		Sip: 7.4
Discussion	D07	NP Overview
Mon 30 Oct	L16	Reductions and NP-Completeness		Sip: 7.5
Wed 1 Nov	L17	NP-Complete Problems 2	HW7 8pm ET
Discussion	D08	NP-Completeness
Mon 6 Nov	L18	Search and Approximation Algorithms		Sip: 10.1
Wed 8 Nov	L19	Approximation Algorithms 2	HW8 8pm ET
Discussion	D09	Search and Approximation
Randomness in Computation
Mon 13 Nov	L20	Probability, Randomness in Computation
Wed 15 Nov	L21	Randomness in Computation 2	HW9 8pm ET
Discussion	D10	Randomness and Modular Arithmetic Review
Mon 20 Nov	L22	Randomness in Computation 3
Wed 22 Nov		No Class - Thanksgiving	HW10 8pm ET
Discussion		No Class - Thanksgiving
Cryptography
Mon 27 Nov	L23	One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2		Sip: 10.6
Wed 29 Nov	L24	RSA and Factoring	HW11 8pm ET
Discussion	D11	Randomness and Intro to Cryptography
Special Topics
Mon 4 Dec	L25	Special Topcs (Untested Material)
Wed 6 Dec	L26	Special Topcs (Untested Material)	HW12 8pm ET
Final Exam
Tue 12 Dec		Final Exam	Final 7pm ET