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