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

ABCDEFGHIJKLMNOPQRST
1
TopicRequired
Handouts
/Announcements
2
CMPSC465, Fall 2017, Data Structures and Algorithms
3
Instructor: Professor Paul Medvedev (pzm11)
4
5
SyllabusSyllabus
6
Professor OH:Professor OH
7
Piazzahttps://piazza.com/class/j6h3u1trhlr6xx?cid=9
8
Professor OH:http://medvedevgroup.com/medvedev.html
9
TA Office Hours:See Piazza
10
11
Past and curent schedule
12
8/21/2017 (recit)no recitation
13
8/21/2017Intro, Insertion sortCh 2.1SyllabusSlides posted on Canvas
14
8/23/2017Insertion sort, Loop InvariantsCh 2.1Insertion Sort animation
15
8/25/2017Running time analysis, Asymptotic notationCh 2.2, 3.1
16
8/28 (recit)no recitation
17
8/28/2017Asymptotic notationCh 3.1
18
8/30/2017Asymptotic notation, Merge sortCh 2.3Homework 1 postedMerge Sort Animation
19
9/1/2017Maximum-subarray problemCh 2.3, Ch 4.1
20
9/4 (recit)Labor day, no class
21
9/4/2017Labor day, no class
22
9/6/2017Maximum-subarray problemCh 4.1Homework 1 due
23
9/8/2017Solving Recurrence relationsCh 4.5 and 4.3
24
9/11 (recit)Review of Homework 1 solutions and asymptotic practice problems
25
9/11/2017Solving Recurrence relations and dynamic programming
26
9/13/2017DP: Fibonnaci Numbers and Rod Cutting Ch 15.1
27
9/15/2017Going over HW2 solutionsHomework 2 due
28
9/18 (recit)Review loop invariant proof of correctness of Merge algorithm
29
9/18/2017No class
30
9/20/2017DP: Rod cutting and Weighted Interval Scheduling
31
9/22/2017DR: Weighted interval scheduling (Evening Comprehension Exam)
32
9/25 (recit)DP: Independent set on a line practice problem
33
9/25/2017DP: Longest Common SubsequenceCh 15.4Homework 3 due, before class
34
9/27/2017DP: Longest Common Subsequence and Max Subarray problem
35
9/29/2017no class
36
10/2 (recit)Solutions to Comprehension Exam
37
10/2DP (Max Subbarray) and Greedy Algorithms (Unweighted Interval Scheduling)Ch 4.1, Kleinberg and Tardos, "Algorithm Design"
38
10/4/2017Greedy Algorithms (Unweighted Interval Scheduling) and Midterm ReviewHomework 4 due, before class
39
10/6/2017Greedy Algorithms: UIS and Interval Partitioning
40
10/9 (recit)Solutions to Homework 4
41
10/9/2017Greedy Algorithms: UIS Scheduling to minimize latenessCh 4.2, Kleinberg and Tardos, "Algorithm Design"
42
10/11/2017NO CLASS (Evening Midterm)
43
10/13/2017Abstract Data Types, Priority Queues and binary heapsCh 10.1, 10.2, 10.4, 6.1, 6.2, 6.4, 6.5
44
10/16 (recit)Midterm Solutions
45
10/16/2017Priority Queues and binary heapsCh 6.1, 6.2, 6.4, 6.5
46
10/18/2017Binary Search TreesCh 12.1, 12.2, 12.3
47
10/20/2017Red Black TreesCh 13.1, 13.2, 13.3Homework 5 due, before class
48
10/23 (recit)HW 5 (Greedy) solutions
49
10/23/2017Red Black Trees
50
10/25/2017Rank/Select augmentation Ch 14.1
51
10/27/2017Interval Trees: augmenting data structuresCh 14.3
52
10/30 (recit)Problem 14-1 from CLRS(10/29 11pm) Homework 6 due
53
10/30/2017Interval Trees: augmenting data structures
54
11/1/2017Hashing
55
11/3/2017Hashing
56
11/6 (recit)Q&A Session
57
11/6/2017GraphsCh 22.1
58
59
11/10/2017Depth First Search Ch 22.3
60
11/13(recit)Solutions to d-ary heap problem(11/12 11pm) Homework 7 due
61
11/13/2017Applications of DFS: Finding Cycles and Topological SortCh 22.4
62
11/15/2017Shortest paths propertiesCh 24, intro part
63
11/17/2017no class
64
11/20 - 11/26 holidays
65
11/27 (recit)Finding a cycle in O(V) time
66
11/27/2017no lecture
67
11/29/2017Shortest paths properties / Bellman FordCh 24.1Homework 8 due
68
12/1/2017Bellman Ford, Dijkstra's
69
12/4 (recit)Exercies 24.1-3 and 24-1 -- this will help with your homework!
70
12/4/2017Dijkstra's
71
12/6/2017Final Review, NP-completeness (Evening Comprehension Exam)
72
12/8/2017NP-completenessHomework 9 due before class
73
74
Tentative schedule
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