September | ||||
Monday | Tuesday | Wednesday | Thursday | Friday |
24
13:30-14:20 Lecture
MGH 241 Introduction, Stable Matching Chapter 1, Section 1.1 Intro: Main Slides: Stable Matching
14:20-15:00 OH (Beame)
CSE 668 |
25 | 26
13:30-14:20 Lecture
MGH 241 Stable Matching, Complexity Chapter 2, Sections 2.1-2.3 Slides: Stable Matching slides 13-25 Slides: Overview |
27
11:30-12:20 OH (Chagaleti)
CSE 218
14:00-14:50 OH (Eng)
CSE 220 |
28
13:30-14:20 Lecture
MGH 241 Representative Problems, Graph Traversal Section 1.2, Chapter 3 Slides: Overview slides 10-29 Slides: Graph Traversal |
October | ||||
Monday | Tuesday | Wednesday | Thursday | Friday |
01
14:20-15:00 OH (Beame)
CSE 668 |
02
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
03
13:30-14:20 Lecture
MGH 241 Greedy Algorithms: Interval Scheduling Chapter 4 Slides: Greedy Algorithms Slides 1-20
15:00-15:50 OH (Beame)
CSE 668 |
04
14:00-14:50 OH (Eng)
CSE 220 |
05
13:30 HW1 due
13:30-14:20 Lecture
MGH 241 Greedy Algorithms: Deadline Scheduling, Shortest Paths, Min-Spanning Trees Slides: Greedy Algorithms Slides 21-86 |
08
13:30-14:20 Lecture
MGH 241 Greedy Algorithms: Min-Spanning Trees, Belady's Algorithm Slides: Greedy Algorithms Slides 87-107
14:20-15:00 OH (Beame)
CSE 668 |
09
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
10
13:30-14:20 Lecture
MGH 241 Divide and Conquer: Closest Pair in the Plane Chapter 5 Slides: Divide and Conquer
15:00-15:50 OH (Beame)
CSE 668 |
11
11:30-12:20 OH (Chagaleti)
CSE 218
14:00-14:50 OH (Eng)
CSE 220 |
12
13:30 HW2 due
13:30-14:20 Lecture
MGH 241 Divide and Conquer: Master Recurrence, Strassen's Algorithm Chapter 5, Algebraic Divide and Conquer Slides: Divide and Conquer slides 18-32 |
15
13:30-14:20 Lecture
MGH 241 Divide and Conquer: Karatsuba's Algorithm, FFT Chapter 5, Algebraic Divide and Conquer Slides: Divide and Conquer slides 33-58
14:20-15:00 OH (Beame)
CSE 668 |
16
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
17
13:30-14:20 Lecture
MGH 241 Divide and Conquer: Median, Quicksort Analysis Section 13.5 Slides: Divide and Conquer slides 59-79
15:00-15:50 OH (Beame)
CSE 668 |
18
11:30-12:20 OH (Chagaleti)
CSE 218
14:00-14:50 OH (Eng)
CSE 220 |
19
13:30 HW3 due
13:30-14:20 Lecture
MGH 241 Dynamic Programming: Weighted Interval Scheduling Sections 6.1-6.2 Slides: Dynamic Programming slides 1-24 |
22
13:30-14:20 Lecture
MGH 241 Dynamic Programming: Segmented Least Squares, Knapsack, RNA Secondary Structure Sections 6.3-6.5 Slides: Dynamic Programming 25-49 |
23
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
24
13:30-14:20 Lecture
MGH 241 Dynamic Programming: RNA Secondary Structure, Sequence Alignment/Edit Distance Sections 6.6-6.10 Slides: Dynamic Programming 44-62
15:00-15:50 OH (Beame)
CSE 668 |
25
11:30-12:20 OH (Chagaleti)
CSE 218
14:00-14:50 OH (Eng)
CSE 220 |
26
13:30 HW4 due
13:30-14:20 Lecture
MGH 241 Dynamic Programming: Sequence Alignment/Edit Distance, Bellman-Ford Sections 6.6-6.10 Slides: Dynamic Programming 63-81 |
29
14:20-15:00 OH (Beame)
CSE 668 |
30
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
31
13:30-14:20 Lecture
MGH 241 Network Flow: Ford-Fulkerson, Maxflow=Mincut Section 7.2 Slides: Matching/Flow 15-31
15:00-15:50 OH (Beame)
CSE 668 |
01
11:30-12:20 OH (Chagaleti)
CSE 218
14:00-14:50 OH (Eng)
CSE 220 |
02
13:30-14:30 Midterm
MGH 241 |
November | ||||
Monday | Tuesday | Wednesday | Thursday | Friday |
05
14:20-15:00 OH (Beame)
CSE 668 |
06
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
07
13:30-14:20 Lecture
MGH 241 Network Flow: Edmonds-Karp, Applications: Project Selection Section 7.5, 7.11 Slides: Flow 47-62
15:00-15:50 OH (Beame)
CSE 668 |
08
11:30-12:20 OH (Chagaleti)
CSE 218
14:00-14:50 OH (Eng)
CSE 220 |
09
13:30 HW5 due
13:30-14:20 Lecture
MGH 241 Midterm Post, Network Flow applications: Disjoint paths Section 7.6 |
12
Veterans Day
|
13
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
14
13:30-14:20 Lecture
MGH 241 Reductions Chapter 8 Slides: Reductions, Clique, Independent Set, Vertex Cover, Set Cover 1-15
15:00-15:50 OH (Beame)
CSE 668 |
15
11:30-12:20 OH (Chagaleti)
CSE 218
14:00-14:50 OH (Eng)
CSE 220 |
16
13:30 HW6 due
13:30-14:20 Lecture
MGH 241 P, NP, and NP-completeness Chapter 8 Slides: P, NP, and NP-completeness, Cook-Levin Theorem 16-37 |
19
13:30-14:20 Lecture
MGH 241 NP-completeness of Independent-Set, DecisionTSP, etc Chapter 8 Slides: NP-completeness 38-54
14:20-15:00 OH (Beame)
CSE 668 |
20
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
21
13:30-14:20 Lecture
MGH 241 NP-completeness of 3-colorability, Subset-Sum, Hamiltonian Circuit Chapter 8 Slides: NP-completeness 50-61
15:00-15:50 OH (Beame)
CSE 668 |
22
Thanksgiving
|
23
Thanksgiving
|
26
13:30-14:20 Lecture
MGH 241 NP-completeness of 3-Dimensionsal Matching, Approximation Algorithm for Vertex Cover Slides: NP-completeness 62-71 Slides: Dealing with NP-completeness 1-3
14:20-15:00 OH (Beame)
CSE 668 |
27
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
28
13:30 HW7 due
13:30-14:20 Lecture
MGH 241 Hardness of Approximation for Coloring; Approximation for TSP, Set Cover Section 11.3 Slides: Dealing with NP-completeness 4-15
15:00-15:50 OH (Beame)
CSE 668 |
29
11:30-12:20 OH (Chagaleti)
CSE 218
14:00-14:50 OH (Eng)
CSE 220 |
30
13:30-14:20 Lecture
MGH 241 Backtracking; Local search techniques; Biology and Physics-inspired Methods; SAT solvers Slides: Dealing with NP-completeness 16- |
December | ||||
Monday | Tuesday | Wednesday | Thursday | Friday |
03
13:30-14:20 Lecture
MGH 241 SAT solvers, LP, Multiplicative Weight Update
14:20-15:00 OH (Beame)
CSE 668 |
04
12:30-13:20 OH (Chagaleti)
CSE 216
13:30-14:20 OH (Eng)
CSE 218 |
05
13:30 HW8 due
13:30-14:20 Lecture
MGH 241 TBD
15:00-15:50 OH (Beame)
CSE 668 |
06
11:30-12:20 OH (Chagaleti)
CSE 218
14:00-14:50 OH (Eng)
CSE 220 |
07
13:30-14:20 Lecture
MGH 241 TBD |
10
14:30-16:20 Final exam
MGH 241 |
11 | 12 | 13 | 14 |