EECS 215: Design and Analysis of Algorithms, Fall 2011

Lecture Schedule and Materials

This tentative schedule will be updated throughout the quarter.

Week Lecture Date Topic Book Chapters Slides Homeworks
0 1 Thu 9/22 course syllabus
Stable Matching
-
KT 1.1
syllabus
stable matching, demo
1 2 Tue 9/27 representative problems
Algorithm Analysis
KT.1.2
KT 2.1-2.4
5 problems
(ch.2) analysis
3 Thu 9/29 Graphs: definitions,
exploration (BFS)
KT 3.1-3.2 Slides from Ch.3
2 4 Tue 10/4 traversal, BFS, DFS KT 3.2-3.4 HW1
(due 10/20)
5 Thu 10/6 directed graphs,
greedy algorithms
KT 3.5-3.6
KT 4.1
Slides from Ch.4
3 - Mon 10/10 Python tutorial (optional) python scripts, slides
electronic submission
HW1 instructions
6 Tue 10/11 scheduling,
shortest paths
KT 4.1
KT 4.4
7 Thu 10/13 shortest paths
MST
KT 4.4
KT 4.5
4 8 Tue 10/18 MST, clustering
recursions
KT 4.5-4.7
KT 5.1-5.2
9 Thu 10/20 Divide and conquer KT 5.1-5.3, 5.5 Slides from Ch.5 HW2
HW1sol
GS python
5 10 Tue 10/25 Dynamic Programing (DP) 6.1,6.2,6.4 slides on DP
11 Thu 10/27 MIDTERM a and b
solution
6 12 Tue 11/1 DP continued 6.6, 6.8
13 Thu 11/3 Shortest Paths revisited
Network Flow
6.8-6.10
7.1-7.2
all slides on shortest paths HW2sol
7 14 Tue 11/8 Finding Max Flow 7.2-7.3 slides on network flow
15 Thu 11/10 Applications
of Max Flow
7.5-7.7 HW3
due 11/22
8 16 Tue 11/15 Reductions 8.1-8.2 slides, Ch.8, Part 1
17 Thu 11/17 NP, NP-complete 8.3-8.4 slides, Ch.8, Part 2
9 18 Tue 11/22 Well-known NP-complete problems 8.5-8.8 slides, Ch.8, part3 HW3sol
HW4
- Thu 11/24 THANKSGIVING
10 19 Tue 11/29 Beyond NP
NP-hardness in practice
8.9, 9.1
10.1-10.2
slides "beyond np"
special input
20 Thu 12/1 Review review slides sample final, HW4sol
11 - Tue 12/6
10:30-12:30
FINAL EXAM (in the regular classroom!)

(*) 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). By default (unless otherwise notified), the lectures will be given as scheduled.