Class log: CS 6301.502: Implementation of advanced data structures and algorithms (Fall 2017)
1 W 8/23 Course introduction
2 F 8/25 Java introduction (see also Java examples)
3 W 8/30 Graph class, iterators
4 F 9/1 Lists, stacks, queues
5 W 9/6 List algorithms, Singly linked lise example
6 F 9/8 Depth-first search: topological sort, strongly connected comp
7 W 9/13 DFS: Bridges and cut vertices, LP1 operations, Recursion
8 F 9/15 Euler tours
9 W 9/20 Algorithm to find Euler tours, Quick sort
10 F 9/22 Select algorithm: find k largest elements
11 W 9/27 Priority queues, Prim's MST algorithm
12 F 9/29 Applications of PQ, Kruskal and Boruvka MST algorithms
13 W 10/4 Trees, Dictionary ADT: Binary search trees
14 F 10/6 BST algorithms, MST in directed graphs (optimal branchings)
15 W 10/11 AVL, Red-Black trees
16 F 10/13 Splay, B trees, Shortest paths: BFS, DAG-shortest paths, Dijkstra
17 W 10/18 Bellman-Ford algorithm for shortest paths, enumeration
18 F 10/20 Skip lists, Hashing
19 W 10/25 Skip lists, Verification algorithms for AVL, RBT
20 F 10/27 Advanced hashing algorithms
21 W 11/1 Hashing, Bloom filters, Multi-dimensional search
22 F 11/3 Maximum flow problem
23 W 11/8 Max-flow algorithms
24 F 11/10 Min-cost flow algorithms, Matching problem in bipartite graphs
25 W 11/15 String algorithms, Tries, Rabin-Karp algorithm
26 F 11/17 KMP, Boyer-Moore algorithms, Suffix trees
27 W 11/29 McCreight/Ukkonen's algorithm, Suffix arrays, GST, DP problems
28 F 12/1 Heuristics for push-relabel flow, DP problems on strings
29 W 12/6 DP problems
Final exam: 5:00-7:00 PM, Wed, Dec 13