CMPSC 465 Fall 2015
 Share
The version of the browser you are using is no longer supported. Please upgrade to a supported browser.Dismiss

 
View only
 
 
Still loading...
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
Loading...
 
 
 
Sheet1