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 guarranteed 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 Monday, May 1 at noon. Note that this is a different time than we normally meet. The exam will emphasize Chapters 5 (heaps, priority queues, Huffman coding trees), 6 (disjoint sets), 7 (sorting), 9 (hash tables), 10 (2-3 trees, 2-3-4 trees), 11 (graphs), 13 (AVL trees), 14 (amortized analysis), 16 (dynamic programming, skip lists), and 17 (limits of computation).

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 = vector<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++) cout << m[row][col] << ' '; cout << endl; } }

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.

You will not be asked to do a formal mathematical proof on the exam, but may be asked to provide justification for a claim being made.

Given a particular problem, be prepared to recommend a data structure/algorithm that would solve the problem in the most efficient way. Be able to provide the asymptotic complexity of the data structure/algorithm you recommend. For example, consider the problem of being able to add elements to a data structure in any order but always being able to extract the lowest (or highest) value. What data structure is best suited for this problem and what is the asymptotic complexity of the insertion and extraction operations?

Study carefully:

• general complexity issues (what kinds of algorithms are constant time, linear, quadratic, logarithmic, exponential, etc.)
• priority queues
  • heap data structure
  • complexity
• 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
• disjoint sets (union/find)
  • relation to equivalence relations
  • union by height
  • union by size
  • path compression
  • complexity
  • applications of disjoint sets
• 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
  • edit distance
  • complexity LCS
  • applications of dynamic programming
• randomized algorithms
  • skip lists
• amortized analysis
• limits of computation
  • problem reduction
  • proving lower bounds
  • intractable problems
  • NP-complete problems
  • undecidable problems
  • halting problem

Here are some examples of things you may be required to do:

• Determine the structure of a heap after insertions and/or deletions
• Populate a hash table given specifics about its hash function and collision resolution strategy
• Craft a C++ function that uses an adjacency matrix to solve a graph problem
• Apply recursive depth-first search to solve a particular problem
• Construct a 2-3 or 2-3-4 tree from a sequence of values
• Describe a well-known algorithm in pseudocode or actual C++ code
• Complete a dynamic programming table for a given problem instance
• Apply amortized analysis to a given scenario
• Reduce one problem instance to another

The purpose of these examples is to give you an idea of the nature of the questions on the exam. They are not meant to cover all the possibilities of questions that could be on the exam.