EECS 215: Design and Analysis of Algorithms, Fall 2015

Lecture Schedule and Materials

This tentative schedule will be updated throughout the quarter.

Week Date Lecture Topic & Slides Reading Materials and
Assignments
1 Mon 9/28 Syllabus
Stable Marriage and Demo

KT 1.1
Wed 9/30 Analysis of Running Time
Experiments vs. Models
KT. 2.1, 2.2, 2.4
SW 1.4
2 Mon 10/5 Undirected Graphs
BFS Demo, DFS Demo
KT 3.1, 3.2, 3.4
SW 4.1
Wed 10/7 Directed Graphs
Greedy I: Scheduling
KT 3.5-3.6, SW 4.2
KT 4.1-4.2
HW1
3 Mon 10/12 Greedy II: Trees on Graphs KT 4.4, 4.5, 4.7
Wed 10/14 greedy misc, union-find
MergeSort
SW 1.5, KT 4.6
KT 5.1-5.2
4 Mon 10/19 Divide-and-conquer cont'd:
beyond mergesort
KT 5.3, 5.5
SW 2.2
visualization
HW2
Wed 10/21 Dynamic Programming:
WIS, Knapsack

6.1-6.2, 6.4
HW1sol
5 Mon 10/26 Bellman-Ford
midterm info
6.8 HW3
midterm sample
Wed 10/28 DV protocols, negative cycles 6.9-6.10
6 Mon 11/2 Flows, Max Flow Min Cut 7.1-7.2 HW2sol
Wed 11/4 MIDTERM midterm sol
7 Mon 11/9 Flows: Running Time, Applications 7.3, 7.5-7.7 HW4
Wed 11/11 Veteran's Day: NO CLASS HW3sol
HW3 Knapsack Code
8 Mon 11/16 Applications of Flows
Polynomial Reductions
KT 7.5-7.7
KT 8.1-8.2
Wed 11/18 P vs. NP KT 8.3
9 Mon 11/23 NP-Completeness 8.4 HW4sol
Wed 11/25 More NPC: Sequencing 8.4-8.5 HW5
10 Mon 11/30 NPC cont'd: Coloring, Numerical
co-NP and beyond NP
8.6-8.8
8.9, 8.10. 9.1
Wed 12/2 Special or small instances
Greedy approx to KP
Review
10.1, 10.2

sample finals: F11, F14
11 Fri 12/11
8-10am
FINAL EXAM HW5sol