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