Mark Brehob
4:30pm-6pm MW
1109 FXB
Canvas
Lecture Videos
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 8 Jan | No Class | |||
| Wed 10 Jan | L01 | Introduction, The Potential Method 1 2 | MM: 1, 2-2.2, Sip 7.1 | |
| Discussion | D01 | Review: Proofs, Asymptotic Notation, Induction | ||
| Mon 15 Jan | No Class - MLK Day | |||
| Wed 17 Jan | L02 | Divide and Conquer 1 |
HW1
8pm ET |
MM: 2.3, 3-3.1, 3.2.1 (Mergesort) |
| Discussion | D02 | Divide and Conquer | ||
| Mon 22 Jan | L03 | Divide and Conquer 2 | ||
| Wed 24 Jan | L04 | Dynamic Programming 1 |
HW2
8pm ET |
MM: 3.3-3.4 |
| Discussion | D03 | Divide and Conquer & Dynamic Programming | ||
| Mon 29 Jan | L05 | Dynamic Programming 2 | ||
| Wed 31 Jan | L06 | Dynamic Programming 3 |
HW3
8pm ET |
|
| Discussion | D04 | Dynamic Programming | ||
| Mon 5 Feb | L07 | Greedy Algorithms | MM: 3.5 | |
| Computability | ||||
| Wed 7 Feb | L08 | Formal Languages and Finite Automata 1 2 |
HW4
8pm ET |
Sip: 0.1, 1.1, 1.3 |
| Discussion | D05 | Greedy and Finite Automata | ||
| Mon 12 Feb | L09 | Turing Machines and Decidability | Sip: 3.1, 3.2 | |
| Wed 14 Feb | L10 | Diagonalization |
HW5
8pm ET |
Sip: 4.2 |
| Discussion | D06 | Turing Machines and Diagonalization | ||
| Mon 19 Feb | L11 | The Acceptance and Halting Problems | Sip: 5.1, 5.3 | |
| Wed 21 Feb | L12 | Reducibility |
HW6
8pm ET |
Sip: 5.2 |
| Discussion | D07 | Acceptance and Reducibility | ||
| Midterm | ||||
| Mon 26 Feb | No Class - Spring Break | |||
| Wed 28 Feb | No Class - Spring Break | |||
| Discussion | No Class - Spring Break | |||
| Mon 4 Mar | L13 | Midterm Review | ||
| Wed 6 Mar | L14 | Midterm, 7-9pm ET |
Midterm
7pm ET |
|
| Discussion | D08 | TBD | ||
| Complexity | ||||
| Mon 11 Mar | L15 | The Classes P and NP | Sip: 7.2, 7.3 | |
| Wed 13 Mar | L16 | The Cook-Levin Theorem | Sip: 7.4 | |
| Discussion | D09 | NP Overview | ||
| Mon 18 Mar | L17 | Reductions and NP-Completeness | Sip: 7.5 | |
| Wed 20 Mar | L18 | NP-Complete Problems 2 |
HW7
8pm ET |
|
| Discussion | D10 | NP-Completeness | ||
| Mon 25 Mar | L19 | Search and Approximation Algorithms | Sip: 10.1 | |
| Wed 27 Mar | L20 | Approximation Algorithms 2 |
HW8
8pm ET |
|
| Discussion | D11 | Search and Approximation | ||
| Randomness in Computation | ||||
| Mon 1 Apr | L21 | Probability, Randomness in Computation | ||
| Wed 3 Apr | L22 | Randomness in Computation 2 |
HW9
8pm ET |
|
| Discussion | D12 | Randomness and Modular Arithmetic Review | ||
| Mon 8 Apr | L23 | Randomness in Computation 3 | ||
| Cryptography | ||||
| Wed 10 Apr | L24 | One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2 |
HW10
8pm ET |
Sip: 10.6 |
| Discussion | D11 | Randomized Algorithms | ||
| Mon 15 Apr | L25 | RSA and Factoring | ||
| Wed 17 Apr | L26 | Zero-knowledge proofs |
HW11
8pm ET |
|
| Discussion | D12 | Intro to Cryptography | ||
| Special Topics | ||||
| Mon 22 Apr | L27 | Special Topcs (Untested Material) | ||
| Final Exam | ||||
| Wed 24 Apr | No Class - End of Semester | |||
| Discussion | No Class - End of Semester | |||
| Wed 1 May | Final Exam, 7–9pm |
Final
7pm ET |
||
4:30pm-6pm MW
1109 FXB
3pm-4:30pm MW
1670 Beyster
1:30-3pm MW
STAMPS
9am-10:30am MW
220 CHRYS
