EECS 215: Design and Analysis of Algorithms, Fall 2014

Lecture Schedule and Materials

This tentative schedule will be updated throughout the quarter.

Week Lecture Date Lecture Topic & Slides Reading Materials and
Assignments
1 1 Mon 10/6 Syllabus
Stable Matching, Example
KT 1.1
2 Wed 10/8 Analysis of Running Time
Experiments vs. Models
KT 2.1,2.2,2.4
SW 1.4
Discussion 1
2 3 Mon 10/13 Running Time Cont'd
Undirected graphs
Graph traversal
KT 2.3
KT 3.1-3.2
SW 4.1
Ch2. Ex.5,6
4 Wed 10/15 BFS Demo, DFS Demo
Directed graphs
KT 3.2-3.4
KT 3.5
Discussion 2
3 5 Mon 10/20 Greedy I: scheduling KT 4.1-4.3
6 Wed 10/22 Greedy II: Graph Algs
UF: data structure, demo
KT 4.4-4.6
union-find
HW1
Discussion 3
4 7 Mon 10/27 (*) Review problems (David) past midterm
8 Wed 10/29 Divide-and-Conquer:
mergesort, recursions
KT 5.1-5.2
SW 2.2
visualization
Discussion 4
5 9 Mon 11/3 counting inversions, int mult
DP: Weighted Interval Scheduling
KT 5.3, 5.5
KT 6.1-6.2
HW2
10 Wed 11/5 DP: Knapsack
DP: shortest paths
KT 6.4
KT 6.8
HW1sol
Discussion 5
6 11 Mon 11/10 Bellman-Ford KT 6.8-6.9 HW2sol
12 Wed 11/12 MIDTERM
7 13 Mon 11/17 Network Flows, Max Flow Min Cut 7.1-7.2
14 Wed 11/19 Max Flow Cont'd
Applications
7.3
7.5-7.7
midterm sol
HW3
8 15 Mon 11/24 Reductions 8.1-8.2
16 Wed 11/26 P vs. NP, intro to NP-completeness 8.3-8.4
9 17 Mon 12/1 NP Completeness, Sequencing 8.4, 8.5
18 Wed 12/3 Graph coloring, Knapsack
Beyond NP
8.7-8.8
8.9, 9.1
HW3sol, KP code
HW4
10 19 Mon 12/8 Small or special inputs
PTAS, Greedy Approx. to KP
10.1-10.2
11 Intro
20 Wed 12/10 Approximations cont'd
Review
11.6, 11.8 HW4Sol
11 - Fri 12/19
8-10am
FINAL EXAM Sample past finals:
2010, 2011

(*) The instructor may be out of town those days. If that turns out to be the case, an alternative arrangement will be made (somebody else will give the lecture, or we will schedule a makeup session).