EECS 215: Design and Analysis of Algorithms, Winter 2017

Lecture Schedule and Materials

This tentative schedule will be updated throughout the quarter.

Week Date Lecture Topic & Slides Reading Materials and
Assignments
1 Mon 1/09 Syllabus
Stable Marriage and Demo
KT 1.1
Wed 1/11 Analysis of Running Time KT 2.1-2.4 supplemental: SW1.4 and slides
2 Mon 1/16 MLK Day HW1
Wed 1/18 Running Time Cont'd 2.3-2.4
3 Mon 1/23 Undirected Graphs
BFS and DFS demos
Directed Graphs
3.1-3.4

3.5-3.6

SW, Ch.4
Wed 1/25 Greedy Alg. for Scheduling 4.1-4.2
4 Mon 1/30 Shortest Paths: Dijkstra KT 4.4
Wed 2/01 Minimum Spanning Trees KT 4.5 HW1Sol
5 Mon 2/06 Discussion
MergeSort
KT 4.6
KT 5.1
SW 1.5: Union Find
HW2
Wed 2/08 General Recursions
Merge-and -Count
5.2
5.3
sample midterm
sample midterm solution
6 Mon 2/13 Recursive multiplications
midterm review
5.4 HW2sol
Wed 2/15 Midterm
7 Mon 2/20 Presidents' Day
Wed 2/22 DP: scheduling 6.1-6.2
8 Mon 2/27 DP: Knapsack
DP: Bellman-Ford
6.4
6.8-6.10
Wed 3/01 Asynchronous BF
Intro to Network Flows
DP in control HW3 and KP files
9 Mon 3/06 Max Flow, Ford-fulkerson 7.1-7.3 HW4
Wed 3/08 Max Flow Applications 7.5-7.7 midterm solution
10 Mon 3/13 Poly-time reductions 8.1-8.2
Wed 3/15 P vs. NP
NP Completeness
8.3
8.4
HW3sol, KP code
HW4sol, HW5 from F15
11 Mon 3/20
1:30-3:30pm
FINAL EXAM logistics sample finals: F11, F15