derezin@umich.edu
4:30-6pm MW
1571 GGBL
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.
Day | # | Material and Readings in Notes | Deadline | |
---|---|---|---|---|
Design and Analysis of Algorithms | ||||
Mon 6 Jan | No Class | |||
Wed 8 Jan | L01 | Introduction, The Potential Method | ||
Discussion | D01 | Review: Proofs, Asymptotic Notation, Induction | ||
Mon 13 Jan | L02 | Divide and Conquer 1 | ||
Wed 15 Jan | L03 | Divide and Conquer 2 1 2 |
HW1
8pm ET |
|
Discussion | D02 | Divide and Conquer | ||
Mon 20 Jan | No Class - MLK Day | |||
Wed 22 Jan | L04 | Dynamic Programming 1 |
HW2
8pm ET |
|
Discussion | D03 | Divide and Conquer & Dynamic Programming | ||
Mon 27 Jan | L05 | Dynamic Programming 2 | ||
Wed 29 Jan | L06 | Dynamic Programming 3 |
HW3
8pm ET |
|
Discussion | D04 | Dynamic Programming | ||
Mon 3 Feb | L07 | Greedy Algorithms | ||
Computability | ||||
Wed 5 Feb | L08 | Formal Languages and Finite Automata 1 2 |
HW4
8pm ET |
|
Discussion | D05 | Greedy and Finite Automata | ||
Mon 10 Feb | L09 | Turing Machines and Decidability | ||
Wed 12 Feb | L10 | Diagonalization |
HW5
8pm ET |
|
Discussion | D06 | Turing Machines and Diagonalization | ||
Mon 17 Feb | L11 | The Acceptance and Halting Problems | ||
Wed 19 Feb | L12 | Reducibility | ||
Discussion | D07 | Acceptance and Reducibility | ||
Midterm | ||||
Mon 24 Feb | Midterm Review |
HW6
8pm ET |
||
Wed 26 Feb | Special Topcs (Untested Material) | |||
Thu 27 Feb | Midterm, 7-9pm ET |
Midterm
7pm ET |
||
Discussion | No Class | |||
Mon 3 Mar | L13 | No Class - Spring Break | ||
Wed 5 Mar | L14 | No Class - Spring Break | ||
Discussion | No Class - Spring Break | |||
Complexity | ||||
Mon 10 Mar | L15 | The Classes P and NP | ||
Wed 12 Mar | L16 | The Cook-Levin Theorem | ||
Discussion | D08 | NP Overview | ||
Mon 17 Mar | L17 | Reductions and NP-Completeness | ||
Wed 19 Mar | L18 | NP-Complete Problems 2 |
HW7
8pm ET |
|
Discussion | D09 | NP-Completeness | ||
Mon 24 Mar | L19 | Search and Approximation Algorithms | ||
Wed 26 Mar | L20 | Approximation Algorithms 2 |
HW8
8pm ET |
|
Discussion | D10 | Search and Approximation | ||
Randomness in Computation | ||||
Mon 31 Mar | L21 | Probability, Randomness in Computation | ||
Wed 2 Apr | L22 | Randomness in Computation 2 |
HW9
8pm ET |
|
Discussion | D11 | Randomness and Modular Arithmetic Review | ||
Mon 7 Apr | L23 | Randomness in Computation 3 | ||
Cryptography | ||||
Wed 9 Apr | L24 | One-time Pad, Diffie-Hellman, and Discrete Logarithm 1 2 |
HW10
8pm ET |
|
Discussion | D12 | Randomized Algorithms | ||
Mon 14 Apr | L25 | RSA and Factoring | ||
Wed 16 Apr | L26 | Zero-knowledge proofs |
HW11
8pm ET |
|
Discussion | D13 | Intro to Cryptography | ||
Special Topics | ||||
Mon 21 Apr | L27 | Special Topcs (Untested Material) | ||
Final Exam | ||||
Tue 22 Apr | End of Semester |
HW12
8pm ET |
||
Wed 30 Apr | Final Exam 7:00 - 9:00 PM |
Final
7pm ET |
derezin@umich.edu
4:30-6pm MW
1571 GGBL
graetzer@umich.edu
1:30-3pm MW
Stamps Auditorium
pettie@umich.edu
12-1:30pm MW
1013 Dow
iarya@umich.edu
4:30-5:30pm Th
2166 Dow
yeyuanch@umich.edu
3:30-4:30pm Th and 9:30-10:30am F
1005 EECS and 1003 EECS
kxfa@umich.edu
2:30-3:30pm F
2150 Dow
erickhiu@umich.edu
12:30-1:30pm Th
1005 EECS
umaku@umich.edu
3:30-4:30pm F
2150 Dow
katemcg@umich.edu
11:30am-12:30pm F
1018 Dow
vvraghu@umich.edu
5:30-6:30pm Th and 1:30-2:30pm F
1200 EECS and 1017 Dow
jettr@umich.edu
11:30am-12:30pm F
1008 FXB
nshagri@umich.edu
4:30-5:30pm Th and 10:30-11:30am F
1303 EECS and 2166 Dow
mitwang@umich.edu
12:30-1:30pm F
1017 Dow