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