Data Structures and Algorithms
COSC 336: Final Exam Study Guide
Prepared by: Marius Zimand
The text is open books, open notes, open internet. Open internet means that you are allowed to search information on the internet (even though I think it’s a bad idea, because it takes too much time), but you are not allowed to ask a person, or a forum, this would be cheating.
List of topics (the Sections and Chapters are from the Cormen, Leiserson, Rivest, Stein textbook; the Notes are posted on Blackboard):
1. Hashing: hash tables, hashing with chaining, closed hashing with different probing strategies; linear probing, quadratic probing, probing with a second hash functions. Read Chapter 11 (sections 11.1. 11.2, 11.3, 11.4) and Notes 7.
2. Sorting (review Notes 8 on Blackboard, and the sections from the textbook indicated below):
• lower bound for comparison-based sorting algorithms (section 8.1), • heap sort (section 6.4),
• mergesort (section 2.3.1),
• quicksort and the partition procedure (chapter 7),
• randomized selection (section 9.2)
• linear time sorting algorithms: counting sort and radix sort ( sections 8.2, 8.3)
3. Graph algorithms
• graph representations (adjacency lists, adjacency matrix) (Notes 9, and textbook section 22.1)
• topological sorting of DAGs (Notes 10 and textbook section 22.4)
• DFS and BFS traversals (Notes 10 and textbook sections 22.2 and 22.3)
• DFS with timing and applications: determining if a graph has a cycle, edge classification, finding the strongly connected components of a directed graph. (Notes 10 and textbook section 22.5)
• Algorithms for the single source shortest path problem: Bellman-Ford (textbook section 24.1), Dijkstra (textbook section 24.3) and Notes 11
• Floyd-Warshall algorithm for the all pairs shortest paths problem (textbook sec- tion 25.2 and Notes 11).
• Algorithms for the minimum spanning tree problem: Kruskal algorithm and Prim algorithm (textbook section 23.2 and Notes 12)
• Maximum flow, Ford-Fulkerson method, maximum bipartite matching (textbook sections 26.1, 26.2, 26.3 and Notes 13)
1
For practice, do “by hand” executions of all algorithms from the list above; review the assignments and do the following exercises (from the textbook):
1. Insert additional numbers in the example in Fig. 11.5 2. Exercises 7.2-2, 7.2-3;
3. Exercise 9.2-4
4. Exercise 8.3-1
5. Exercises 22.1-1, 22.1-2 6. Exercises 22.3-2, 22.4-1 7. Exercise 22.5-2
8. Exercises 24.1-1, 24.3-1 9. Exercise 23.1-1
10. Exercise 26.1-2
2