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 | Programming 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/2015 | Intro, Insertion sort | Syllabus | Slides posted on angel | ||||||||||||||||

12 | 8/26/2015 | Insertion sort, Loop Invariants | Ch 2.1 | Homework 1 posted on Angel | Insertion Sort animation | |||||||||||||||

13 | 8/28/2015 | Running time analysis, Asymptotic notation | Ch 2.2, 3.1 | |||||||||||||||||

14 | 8/31/2015 (recit) | Loop Invariants, Binary Search | ||||||||||||||||||

15 | 8/31/2015 | Asymptotic notation | Ch 3.1 | |||||||||||||||||

16 | 9/2/2015 | Merge sort | Ch 2.3 | Homework 2 posted on Angel | Merge Sort Explained | |||||||||||||||

17 | Merge Sort Animation | |||||||||||||||||||

18 | 9/4/2015 | Maximum-subarray problem | Ch 2.3, Ch 4.1 | |||||||||||||||||

19 | 9/7/2015 (recit) | no class | ||||||||||||||||||

20 | 9/7/2015 | no class | ||||||||||||||||||

21 | 9/9/2015 | Recurrence relations | Ch 4.3 | Homework 2 due, 4pm | ||||||||||||||||

22 | Homework 3 posted on Angel | |||||||||||||||||||

23 | 9/11/2015 | Recurrence relations | (tent) Ch 4.3, 4.5 | Homework 1 due (Deadline extended) | ||||||||||||||||

24 | 9/14/2015 (recit) | Solutions for Homework 2 will be discussed | ||||||||||||||||||

25 | 9/14/2015 | DP: Rod Cutting | Ch 15.1 | Homework 1 due (before 9pm) | ||||||||||||||||

26 | 9/16/2015 | DP: Rod Cutting (cont) | Homework 3 due, 4:40 (before class) | |||||||||||||||||

27 | 9/18/2015 | DR: Weighted interval scheduling | not in book | |||||||||||||||||

28 | 9/21 (recit) | |||||||||||||||||||

29 | 9/21/2015 | Midterm Review | ||||||||||||||||||

30 | 9/23/2015 | Midterm | ||||||||||||||||||

31 | 9/25/2015 | DP: Weighted Interval scheduling | Ch 15.4 | |||||||||||||||||

32 | 9/28(recit) | Independent Set on a Line Graph | ||||||||||||||||||

33 | 9/28/2015 | DP: Longest Common Subsequence | Ch 15.4 | |||||||||||||||||

34 | 9/30/2015 | DP: Longest Common Subsequence and independent set on a grid | not in book (see slides) | Homework 4 posted on Angel | ||||||||||||||||

35 | 10/2/2015 | Greedy 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/2015 | Greedy Algorithms: Interval Partitioning | not in book (see notes/slides) | (alternate resource is Kleinberg and Tardos, "Algorithm Design", Ch 4.1) | ||||||||||||||||

38 | 10/7/2015 | Greedy 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/2015 | no class | Homework 4 due, 4:40 (before class) | |||||||||||||||||

40 | 10/12 (recit) | Review of greedy algorithms we've seen | ||||||||||||||||||

41 | 10/12/2015 | Data Structures and Abstract Data types Revew | Ch 10.1, 10.2, 10.4 | |||||||||||||||||

42 | 10/14/2015 | Priority queues and binary heaps | Ch 6.1, 6.2, 6.4, 6.5 | |||||||||||||||||

43 | 10/16/2015 | Binary Search Trees | Ch 12.1, 12.2, 12.3 | |||||||||||||||||

44 | 10/19 (recit) | Go over solution to Homework 4 | ||||||||||||||||||

45 | 10/19/2015 | Red Black Trees | Ch 13.1, 13.2, 13.3 | Homework 5 due, 4:40 (before class) | Red Black Trees animation | |||||||||||||||

46 | 10/21/2015 | Red Black Trees | ||||||||||||||||||

47 | 10/23/2015 | Red Black Trees | Ch 14.1 | |||||||||||||||||

48 | 10/26 (recit) | Go over solution to Homework 5 | Homework 6 due, 4:40 (before class) | |||||||||||||||||

49 | 10/26/2015 | Rank/Select augmentation / Midterm Review | Ch 14.1 | |||||||||||||||||

50 | 10/28/2015 | Midterm | ||||||||||||||||||

51 | 10/30/2015 | no class | ||||||||||||||||||

52 | 11/2 (recit) | no recitation | ||||||||||||||||||

53 | 11/2/2015 | Interval Trees: augmenting data structures | Ch 14.3 | |||||||||||||||||

54 | 11/4/2015 | Interval trees, hashing. | Ch 14.3, Ch 11.1 | |||||||||||||||||

55 | 11/6/2015 | Hashing | parts of Ch 11.2, 11.4 | |||||||||||||||||

56 | 11/9 (recit) | (tent) Problem 14-1 from CLRS | ||||||||||||||||||

57 | 11/9/2015 | Graphs / Breadth First Search | Ch 22.1, 22.2 | |||||||||||||||||

58 | 11/11/2015 | Depth-First Search | Ch 22.3 | Homework 7 due, 4:40 (before class) | ||||||||||||||||

59 | 11/13/2015 | DFS and Topological Sort | Ch 22.3, 22.4 | |||||||||||||||||

60 | 11/16 (recit) | Finding cycles even more quickly using DFS | ||||||||||||||||||

61 | 11/16/2015 | Topological Sort and shortest paths | Ch 24.0, 24.1, 24.2 | |||||||||||||||||

62 | 11/18/2015 | Midterm Review / Shortest paths properties | Ch 24.0, 24.1, 24.2 | Homework 8 due, 4:40 (before class) | ||||||||||||||||

63 | 11/20/2015 | Midterm 3 | ||||||||||||||||||

64 | 11/23 --11/27 | Thanksgiving break | ||||||||||||||||||

65 | 11/30 (recit) | no recitation | ||||||||||||||||||

66 | 11/30/2015 | Shortest paths properties / Bellman Ford | Ch 24.0, 24.1, 24.2 | |||||||||||||||||

67 | 12/2/2015 | Bellman Ford, Dijkstra's | Ch 24.3 | |||||||||||||||||

68 | 12/4/2015 | Dijkstra's / Minimum Spanning Trees | Ch 24.3 | |||||||||||||||||

69 | 12/7 (recit) | Midterm 3 solutions | ||||||||||||||||||

70 | 12/7/2015 | Minimum Spanning Trees | Ch 23 | |||||||||||||||||

71 | 12/9/2015 | Minimum Spanning Trees | Homework 9 due, 4:40 (before class) | |||||||||||||||||

72 | 12/11/2015 | Final 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...