Euiwoong Lee
12pm-1:30pm MW
Canvas
FilesPiazza
Office HoursGradescope
NotesAn 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.
| Day | # | Material and Readings in Notes | Deadline | Optional Readings* |
|---|---|---|---|---|
| Design and Analysis of Algorithms | ||||
| Mon 2 Jan | No Class | |||
| Wed 4 Jan | L01 | Introduction | MM: 1, 2-2.2, Sip 7.1 | |
| Discussion | D01 | Review: Proofs, Asymptotic Notation, Information | ||
| Mon 9 Jan | L02 | The Potential Method and Divide and Conquer 1 2 | MM: 2.3, 3-3.1, 3.2.1 (Mergesort) | |
| Wed 11 Jan | L03 | Divide and Conquer 2 |
HW1
8pm ET |
|
| Discussion | D02 | Divide and Conquer | ||
| Mon 16 Jan | No Class - MLK Day | |||
| Wed 18 Jan | L04 | Dynamic Programming |
HW2
8pm ET |
MM: 3.3-3.4 |
| Discussion | D03 | Dynamic Programming | ||
| Mon 23 Jan | L05 | Dynamic Programming 2 and Greedy Algorithms | MM: 3.5 | |
| Computability | ||||
| Wed 25 Jan | L06 | 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 30 Jan | L07 | Turing Machines and Decidability | Sip: 3.1, 3.2 | |
| Wed 1 Feb | L08 | Diagonalization |
HW4
8pm ET |
Sip: 4.2 |
| Discussion | D05 | Turing Machines and Diagonalization | ||
| Mon 6 Feb | L09 | The Acceptance and Halting Problems | Sip: 5.1, 5.3 | |
| Wed 8 Feb | L10 | Reducibility |
HW5
8pm ET |
Sip: 5.2 |
| Discussion | D06 | Acceptance and Reducibility | ||
| Mon 13 Feb | L11 | Rice's Theorem | ||
| Midterm | ||||
| Wed 15 Feb | L12 | Midterm Review |
HW6
8pm ET |
|
| Discussion | DMR | Midterm Review | ||
| Mon 20 Feb | Midterm |
Midterm
7pm ET |
||
| Wed 22 Feb | No Class | |||
| Discussion | No Class | |||
| Mon 27 Feb | No Class - Spring Break | |||
| Wed 1 Mar | No Class - Spring Break | |||
| Discussion | No Class - Spring Break | |||
| Complexity | ||||
| Mon 6 Mar | L13 | The Classes P and NP | Sip: 7.2, 7.3 | |
| Wed 8 Mar | L14 | The Cook-Levin Theorem | Sip: 7.4 | |
| Discussion | D07 | NP Overview | ||
| Mon 13 Mar | L15 | Reductions and NP-Completeness | Sip: 7.5 | |
| Wed 15 Mar | L16 | NP-Complete Problems 2 |
HW7
8pm ET |
|
| Discussion | D08 | NP-Completeness | ||
| Mon 20 Mar | L17 | Search and Approximation Algorithms | Sip: 10.1 | |
| Wed 22 Mar | L18 | Approximation Algorithms 2 |
HW8
8pm ET |
|
| Discussion | D09 | Search and Approximation | ||
| Randomness in Computation | ||||
| Mon 27 Mar | L19 | Probability, Randomness in Computation | ||
| Wed 29 Mar | L20 | Randomness in Computation 2 |
HW9
8pm ET |
|
| Discussion | D10 | Randomness and Modular Arithmetic Review | ||
| Mon 3 Apr | L21 | Randomness in Computation 3 | ||
| Cryptography | ||||
| Wed 5 Apr | L22 | One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2 |
HW10
8pm ET |
Sip: 10.6 |
| Discussion | D11 | Randomness and Intro to Cryptography | ||
| Mon 10 Apr | L23 | RSA and Factoring | ||
| Special Topics | ||||
| Wed 12 Apr | Special Topcs (Untested Material) |
HW11
8pm ET |
||
| Final Exam | ||||
| Discussion | D12 | RSA and Exam Review | ||
| Mon 17 Apr | L24 | Final Review |
HW12
8pm ET |
|
| Wed 19 Apr | No Class - End of Semester | |||
| Discussion | No Class - End of Semester | |||
| Wed 26 Apr | Final Exam |
Final
7pm ET |
||
