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 Tuesday, May 3 at noon. Note that this is a different day of the week and 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:

typedef vector<vector<int>> AdjacencyMatrix;  //  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;
    }
}
-------------------------------------------------------------------------

This definition of the adjacency matrix data type should look familiar; it is same one used in your Dijkstra's shortest path 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.

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?

Part 1 of the exam, poses 18 such scenarios. You will need to recommend solutions for all 18 problems and provide complexity information for 12 of the solutions. The total number of points for Part 2 is 30.

Part 2 of the exam contains nine questions, of which you must complete seven. You will select two of the nine to omit. Each question in this part is worth 10 points, so the total points for Part 2 is 70.

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
• union/find (disjoint sets)
  • 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

Since you will omit two questions from Part 2, you need not be a master of everything in the topics above. You may choose to selectively ignore some areas during your preparation. If you do so, you should be well grounded in the remaining areas to maximize your potential to do well on the exam.

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 in Part 2 of the exam. They are not meant to cover all the possibilities of questions that could be on the exam.