CPTR 318 Data Structures Final Examination Study Guide

The material presented in this guide covers the concepts emphasized on the final exam. It is meant to guide students studying and reviewing for the test; it is not guaranteed to be comprehensive. Actual test questions will differ from any examples given here. Students should use this guide in addition to other study activities (like reading the textbook, reviewing completed lab assignments, old quizzes, etc.) Some material here may be updated, so check periodically for changes.

The final exam for CPTR 318 is Thursday, December 10, at 10am. Note that this is a different day of the week than we normally meet. The exam will emphasize Chapters 7 (sorting), 9 (hash tables), 10 (2-3 trees, 2-3-4 trees), 11 (graphs), 13 (AVL trees, red-back trees), 14 (amortized analysis), 16 (dynamic programming, skip lists), 17 (limits of computation), and parallel algorithms.

Several of the questions involve graphs, so I've included these instructions on the test:

--------------------------------------------------------------------- Some of the questions pertain to graphs. In each case, the n vertices in a graph are represented by the integer values 0, 1, 2, 3, ..., n - 1. Several questions use the AdjacencyMatrix data type. Here is its definition and an example of code that uses it: using AdjacencyMatrix = std::vector<std::vector<int>>; // A 2-D vector of integers void print_matrix(const AdjacencyMatrix& m) { // Prints the contents of an adjacency matrix int n = m.size(); for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) std::cout << m[row][col] << ' '; std::cout << '\n'; } } -------------------------------------------------------------------------

This definition of the adjacency matrix data type should look familiar; it is same one used in your Prim's minimal spanning tree program. Be sure you are comfortable writing a function that uses such an AdjacencyMatrix to implement a graph algorithm.

Several questions on the test require you to write C++ code. Some questions may ask for pseudocode for an algorithm, while others may ask you to explain and/or perform an algorithm.

There may be at most one mathematical proof on the exam, and one problem may consist entirely of multiple-choice questions.

While you will not be asked detailed questions about the material found in earlier chapters, you should have a general knowledge about the earlier data structures and algorithms—their complexity and application.

Study carefully:

general complexity issues (what kinds of algorithms are constant time, linear, quadratic, logarithmic, exponential, etc.)
sorting
- O(n²) sorts—selection, insertion, exchange
- O(n log n) sorts—quicksort, heapsort, mergesort
hash tables
- hash functions
- external chaining
- internal chaining (probing)
- linear probing
- complexity
graph terminology and representations
- sparse vs. dense graphs
- adjacency matrices
- adjacency lists
- applications of graphs
graph algorithms
- connectivity
- Depth-first search and its applications
- Breadth-first search and its applications
- Dijkstra's shortest path algorithm
- Prim's minimal spanning tree algorithm
- Kruskal's minimal spanning tree algorithm
- Topological sorting
- applications of graphs
- complexity of graph algorithms
balanced trees
- AVL trees
- 2-3 trees
- 2-3-4 trees
- red-black trees
dynamic programming
- longest common subsequence
- complexity LCS
- applications of dynamic programming
randomized algorithms
- skip lists
amortized analysis
limits of computation
- undecidable problems
- halting problem
- intractable problems
- NP-complete problems
parallel algorithms
- Amdahl's law
- race conditions
- critical sections
- deadlock
- map-reduce

Any questions involving AVL trees and red-black trees are limited to the extent we talked about them in class and may be found among the multiple choice questions.