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 at 10am. Note that this is a different day and time than we normally meet. The exam will emphasize Chapters 5 (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.

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:

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