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
Tue 5 May	L01	Introduction, The Potential Method 1 2
Wed 6 May	L02	Divide and Conquer 1
Thu 7 May	L03	Divide and Conquer 2	HW1 8pm ET
Mon 11 May	L04	Dynamic Programming 1
Tue 12 May	L05	Dynamic Programming 2	GA1 8pm ET
Wed 13 May	L06	Dynamic Programming for Graphs
Thu 14 May	L07	Greedy Algorithms	HW2 8pm ET
Computability
Mon 18 May	L08	Formal Languages and Finite Automata 1 2
Tue 19 May	L09	Turing Machines and Decidability	GA2 8pm ET
Wed 20 May	L10	Diagonalization and Undecidability
Thu 21 May	L11	The Acceptance and Halting Problems	HW3 8pm ET
Mon 25 May		No Class - Memorial Day
Tue 26 May	L12	Reducibility	GA3 8pm ET
Midterm
Wed 27 May	L13	Midterm Review	HW4 8pm ET
Thu 28 May		Midterm, 1:30-3:30pm ET	Midterm 1:30pm ET
Computability
Mon 1 Jun	L14	Recognizability
Complexity
Tue 2 Jun	L15	The Classes P and NP
Wed 3 Jun	L16	Reductions and NP-Completeness
Thu 4 Jun	L17	NP-Complete Problems 2	GA4 8pm ET
Mon 8 Jun	L18	The Cook-Levin Theorem
Tue 9 Jun	L19	Search to Decision and Approximation Algorithms	HW5 8pm ET
Wed 10 Jun	L20	Approximation Algorithms 2
Randomness in Computation
Thu 11 Jun	L21	Randomness in Computation	GA5 8pm ET
Mon 15 Jun	L22	Randomness in Computation 2
Tue 16 Jun	L23	Randomness in Computation 3	HW6 8pm ET
Cryptography
Wed 17 Jun	L24	Introduction to Crypography 1 2
Thu 18 Jun	L25	RSA Encryption and Signatures	GA6, HW7 8pm ET
Mon 22 Jun		TBD
Final Exam
Wed 24 Jun		Final Exam, 8-10am	Final 8am ET