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*^{2}) sorts—selection, insertion, exchange - O(
*n*log*n*) sorts—quicksort, heapsort, mergesort

- O(
- 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.