ABCDEFGHIJKLMNOPQRST
1
TopicRequired
Readings		Handouts
/Announcements		Slides/LinksProgramming assignment
2
CMPSC465, Fall 2015, Data Structures and Algorithms
3
Instructor: Professor Paul Medvedev (pzm11)
4
For up to date Instructor's office hours and location, see http://medvedevgroup.com/medvedev.html
5
6
TA Office Hours:Farnaz Tehranchi, IST 359, Tuesdays and Thursdays 6pm - 7pm
Chen Sun, Wartik 506, Wednesdays and Fridays 10:30am - 11:30am
Don Hoang (Learning Assistant), IST 338A, Mondays 2:20-3:20 and 5:40-6:40
Jinhang Choi (Vocareum TA), IST 338A, Tuesdays 2pm - 3pm and Wednesday 6pm to 7pm
7
Professor OH:Professor OH
8

9
Discussion board: https://piazza.com/class/icb646n9hlm7oz
10
11
8/24/2015Intro, Insertion sort
SyllabusSlides posted on angel
12
8/26/2015Insertion sort, Loop InvariantsCh 2.1Homework 1 posted on AngelInsertion Sort animation
13
8/28/2015Running time analysis, Asymptotic notationCh 2.2, 3.1
14
8/31/2015 (recit)Loop Invariants, Binary Search
15
8/31/2015Asymptotic notationCh 3.1
16
9/2/2015Merge sortCh 2.3Homework 2 posted on AngelMerge Sort Explained
17
Merge Sort Animation
18
9/4/2015Maximum-subarray problemCh 2.3, Ch 4.1
19
9/7/2015 (recit)no class
20
9/7/2015no class
21
9/9/2015Recurrence relationsCh 4.3Homework 2 due, 4pm
22
Homework 3 posted on Angel
23
9/11/2015Recurrence relations(tent) Ch 4.3, 4.5Homework 1 due (Deadline extended)
24
9/14/2015 (recit)Solutions for Homework 2 will be discussed
25
9/14/2015DP: Rod CuttingCh 15.1Homework 1 due (before 9pm)
26
9/16/2015DP: Rod Cutting (cont)Homework 3 due, 4:40 (before class)
27
9/18/2015DR: Weighted interval schedulingnot in book
28
9/21 (recit)
29
9/21/2015Midterm Review
30
9/23/2015Midterm
31
9/25/2015DP: Weighted Interval schedulingCh 15.4
32
9/28(recit)Independent Set on a Line Graph
33
9/28/2015DP: Longest Common SubsequenceCh 15.4
34
9/30/2015DP: Longest Common Subsequence and independent set on a gridnot in book (see slides)Homework 4 posted on Angel
35
10/2/2015Greedy Algorithms (Unweighted Interval Scheduling, a.k.a activity selection)Ch 16.1(alternate resource is Kleinberg and Tardos, "Algorithm Design", Ch 4.1)
36
10/5 (recit)no class
37
10/5/2015Greedy Algorithms: Interval Partitioningnot in book (see notes/slides)(alternate resource is Kleinberg and Tardos, "Algorithm Design", Ch 4.1)
38
10/7/2015Greedy Algorithms: Scheduling to minimize lateness
not in book (see notes/slides)(alternate resource is Kleinberg and Tardos, "Algorithm Design", Ch 4.2)
39
10/9/2015no classHomework 4 due, 4:40 (before class)
40
10/12 (recit)Review of greedy algorithms we've seen
41
10/12/2015Data Structures and Abstract Data types RevewCh 10.1, 10.2, 10.4
42
10/14/2015Priority queues and binary heapsCh 6.1, 6.2, 6.4, 6.5
43
10/16/2015Binary Search TreesCh 12.1, 12.2, 12.3
44
10/19 (recit)Go over solution to Homework 4
45
10/19/2015Red Black TreesCh 13.1, 13.2, 13.3Homework 5 due, 4:40 (before class)Red Black Trees animation
46
10/21/2015Red Black Trees
47
10/23/2015Red Black TreesCh 14.1
48
10/26 (recit)Go over solution to Homework 5Homework 6 due, 4:40 (before class)
49
10/26/2015Rank/Select augmentation / Midterm ReviewCh 14.1
50
10/28/2015Midterm
51
10/30/2015no class
52
11/2 (recit)no recitation
53
11/2/2015Interval Trees: augmenting data structuresCh 14.3
54
11/4/2015Interval trees, hashing.Ch 14.3, Ch 11.1
55
11/6/2015Hashingparts of Ch 11.2, 11.4
56
11/9 (recit)(tent) Problem 14-1 from CLRS
57
11/9/2015Graphs / Breadth First SearchCh 22.1, 22.2
58
11/11/2015Depth-First SearchCh 22.3Homework 7 due, 4:40 (before class)
59
11/13/2015DFS and Topological Sort Ch 22.3, 22.4
60
11/16 (recit)Finding cycles even more quickly using DFS
61
11/16/2015Topological Sort and shortest pathsCh 24.0, 24.1, 24.2
62
11/18/2015Midterm Review / Shortest paths propertiesCh 24.0, 24.1, 24.2Homework 8 due, 4:40 (before class)
63
11/20/2015Midterm 3
64
11/23 --11/27Thanksgiving break
65
11/30 (recit)no recitation
66
11/30/2015Shortest paths properties / Bellman FordCh 24.0, 24.1, 24.2
67
12/2/2015Bellman Ford, Dijkstra'sCh 24.3
68
12/4/2015Dijkstra's / Minimum Spanning TreesCh 24.3
69
12/7 (recit)Midterm 3 solutions
70
12/7/2015Minimum Spanning TreesCh 23
71
12/9/2015Minimum Spanning TreesHomework 9 due, 4:40 (before class)
72
12/11/2015Final Review
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100