A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | Topic | Required Readings | Handouts /Announcements | Slides/Links | ||||||||||||||||

2 | CMPSC465, Fall 2017, Data Structures and Algorithms | |||||||||||||||||||

3 | Instructor: Professor Paul Medvedev (pzm11) | |||||||||||||||||||

4 | ||||||||||||||||||||

5 | Syllabus | Syllabus | ||||||||||||||||||

6 | Professor OH: | Professor OH | ||||||||||||||||||

7 | Piazza | https://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/2017 | Intro, Insertion sort | Ch 2.1 | Syllabus | Slides posted on Canvas | |||||||||||||||

14 | 8/23/2017 | Insertion sort, Loop Invariants | Ch 2.1 | Insertion Sort animation | ||||||||||||||||

15 | 8/25/2017 | Running time analysis, Asymptotic notation | Ch 2.2, 3.1 | |||||||||||||||||

16 | 8/28 (recit) | no recitation | ||||||||||||||||||

17 | 8/28/2017 | Asymptotic notation | Ch 3.1 | |||||||||||||||||

18 | 8/30/2017 | Asymptotic notation, Merge sort | Ch 2.3 | Homework 1 posted | Merge Sort Animation | |||||||||||||||

19 | 9/1/2017 | Maximum-subarray problem | Ch 2.3, Ch 4.1 | |||||||||||||||||

20 | 9/4 (recit) | Labor day, no class | ||||||||||||||||||

21 | 9/4/2017 | Labor day, no class | ||||||||||||||||||

22 | 9/6/2017 | Maximum-subarray problem | Ch 4.1 | Homework 1 due | ||||||||||||||||

23 | 9/8/2017 | Solving Recurrence relations | Ch 4.5 and 4.3 | |||||||||||||||||

24 | 9/11 (recit) | Review of Homework 1 solutions and asymptotic practice problems | ||||||||||||||||||

25 | 9/11/2017 | Solving Recurrence relations and dynamic programming | ||||||||||||||||||

26 | 9/13/2017 | DP: Fibonnaci Numbers and Rod Cutting | Ch 15.1 | |||||||||||||||||

27 | 9/15/2017 | Going over HW2 solutions | Homework 2 due | |||||||||||||||||

28 | 9/18 (recit) | Review loop invariant proof of correctness of Merge algorithm | ||||||||||||||||||

29 | 9/18/2017 | No class | ||||||||||||||||||

30 | 9/20/2017 | DP: Rod cutting and Weighted Interval Scheduling | ||||||||||||||||||

31 | 9/22/2017 | DR: Weighted interval scheduling | (Evening Comprehension Exam) | |||||||||||||||||

32 | 9/25 (recit) | DP: Independent set on a line practice problem | ||||||||||||||||||

33 | 9/25/2017 | DP: Longest Common Subsequence | Ch 15.4 | Homework 3 due, before class | ||||||||||||||||

34 | 9/27/2017 | DP: Longest Common Subsequence and Max Subarray problem | ||||||||||||||||||

35 | 9/29/2017 | no class | ||||||||||||||||||

36 | 10/2 (recit) | Solutions to Comprehension Exam | ||||||||||||||||||

37 | 10/2 | DP (Max Subbarray) and Greedy Algorithms (Unweighted Interval Scheduling) | Ch 4.1, Kleinberg and Tardos, "Algorithm Design" | |||||||||||||||||

38 | 10/4/2017 | Greedy Algorithms (Unweighted Interval Scheduling) and Midterm Review | Homework 4 due, before class | |||||||||||||||||

39 | 10/6/2017 | Greedy Algorithms: UIS and Interval Partitioning | ||||||||||||||||||

40 | 10/9 (recit) | Solutions to Homework 4 | ||||||||||||||||||

41 | 10/9/2017 | Greedy Algorithms: UIS Scheduling to minimize lateness | Ch 4.2, Kleinberg and Tardos, "Algorithm Design" | |||||||||||||||||

42 | 10/11/2017 | NO CLASS | (Evening Midterm) | |||||||||||||||||

43 | 10/13/2017 | Abstract Data Types, Priority Queues and binary heaps | Ch 10.1, 10.2, 10.4, 6.1, 6.2, 6.4, 6.5 | |||||||||||||||||

44 | 10/16 (recit) | Midterm Solutions | ||||||||||||||||||

45 | 10/16/2017 | Priority Queues and binary heaps | Ch 6.1, 6.2, 6.4, 6.5 | |||||||||||||||||

46 | 10/18/2017 | Binary Search Trees | Ch 12.1, 12.2, 12.3 | |||||||||||||||||

47 | 10/20/2017 | Red Black Trees | Ch 13.1, 13.2, 13.3 | Homework 5 due, before class | ||||||||||||||||

48 | 10/23 (recit) | HW 5 (Greedy) solutions | ||||||||||||||||||

49 | 10/23/2017 | Red Black Trees | ||||||||||||||||||

50 | 10/25/2017 | Rank/Select augmentation | Ch 14.1 | |||||||||||||||||

51 | 10/27/2017 | Interval Trees: augmenting data structures | Ch 14.3 | |||||||||||||||||

52 | 10/30 (recit) | Problem 14-1 from CLRS | (10/29 11pm) Homework 6 due | |||||||||||||||||

53 | 10/30/2017 | Interval Trees: augmenting data structures | ||||||||||||||||||

54 | 11/1/2017 | Hashing | ||||||||||||||||||

55 | 11/3/2017 | Hashing | ||||||||||||||||||

56 | 11/6 (recit) | Q&A Session | ||||||||||||||||||

57 | 11/6/2017 | Graphs | Ch 22.1 | |||||||||||||||||

58 | 11/8/2017 | Breadth-First Search | Ch 22.2 | |||||||||||||||||

59 | 11/10/2017 | Depth First Search | Ch 22.3 | |||||||||||||||||

60 | 11/13(recit) | Solutions to d-ary heap problem | (11/12 11pm) Homework 7 due | |||||||||||||||||

61 | 11/13/2017 | Applications of DFS: Finding Cycles and Topological Sort | Ch 22.4 | |||||||||||||||||

62 | 11/15/2017 | Shortest paths properties | Ch 24, intro part | |||||||||||||||||

63 | 11/17/2017 | no class | ||||||||||||||||||

64 | 11/20 - 11/26 | holidays | ||||||||||||||||||

65 | 11/27 (recit) | Finding a cycle in O(V) time | ||||||||||||||||||

66 | 11/27/2017 | no lecture | ||||||||||||||||||

67 | 11/29/2017 | Shortest paths properties / Bellman Ford | Ch 24.1 | Homework 8 due | ||||||||||||||||

68 | 12/1/2017 | Bellman Ford, Dijkstra's | ||||||||||||||||||

69 | 12/4 (recit) | Exercies 24.1-3 and 24-1 -- this will help with your homework! | ||||||||||||||||||

70 | 12/4/2017 | Dijkstra's | ||||||||||||||||||

71 | 12/6/2017 | Final Review, NP-completeness | (Evening Comprehension Exam) | |||||||||||||||||

72 | 12/8/2017 | NP-completeness | Homework 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 |