CS35: Final Exam Study Guide

This study guide includes topics covered since the midterm. You should also study all concepts from earlier in the course. The midterm study guide is available here.

You should be able to define or explain the following terms:

Quick sort, partition, randomized quick sort, and pivot
Concepts related to sorting: runtime, comparisons, swaps, in-place sorting, stable sorting
Trees and many related terms and properties, including nodes, the root node, leaf nodes, internal nodes, parent, child, path, depth of a node, subtree, height of a tree
Compare and contrast linear data structures with trees
Tree traversals: pre-order, in-order, post-order, and level-order traversals
Binary tree
Binary search trees and the BST property
Dictionaries (generally)
AVL trees and the AVL tree property
Tree rotations
The recursive definition of binary trees, binary search trees, and AVL trees
Priority queue abstract data type
Analysis of priority queue implementations using sorted lists, unsorted lists, binary search trees, and binary heap trees
Binary heap and the heap operations
Complete binary trees and their array-based representation
The heap-order property
The Complete binary tree property
Using bubble up and bubble down to restore heap-order property
Sorting with a heap
The conceptual overlaps and differences between trees, BST, AVL, priority queues, heaps
Containers of containers; that is, how data structures can contain other data structures as elements
Run time analysis of public interface for LinkedBST, AVLTree, and BinaryHeap
Run time analysis of helper methods as well e.g., balance, rotations, bubbleUp/Down, etc.
The Dictionary abstract data type
Generalized indexing (i.e., associative arrays)
Collisions, mapping and compression
Hash tables, hash functions, hash code, a hash table's load factor
Importance of hash functions, load factors, capacity, etc in performance
Separate chaining and linear probing (as well as possible extensions)
Tradeoffs between BST and HashTable dictionary representations
Various strategies for handling keys (e.g., allowing duplicates in priority queues vs unique keys in BST and Dictionaries)
graph, vertex, edge
directed, undirected graphs
weighted, unweighted graphs
adjacent, neighbor, outgoing edges, incoming edges, out-degree, in-degree, degree
path, reachable, path length, distance, cost
adjacency-list representation, adjacency-matrix representation
breadth-first search, depth-first search of a graph
recursive depth-first search
shortest path problem
Dijkstra's algorithm
cycle
trees
spanning tree, minimum spanning tree (MST)
Prim's algorithm for discovering an MST
Kruskal's algorithm for discovering an MST (at a high level)
directed acyclic graph (DAG)
topological sort

You should be familiar with the following C++-related concepts:

assert
testing strategies
A Pair object
Expanding capacity in CircularyArrayLists vs BinaryHeap
iterators
Processing input correctly by priming the input.
throwing exceptions and try/catch blocks

Practice problems

For each data structure covered in the course, come up with a real-world application that motivates the data structure. The data structure should be able to provide a more efficient solution to the problem then any other structure covered so far.

Give a binary tree with integer keys at nodes, whose traversals are:
- PreOrder: [80 46 92 90 121 111 105]
- InOrder: [46 80 90 92 105 111 121]
- PostOrder: [46 90 105 111 121 92 80]
Is the tree a BST? Is it an AVLTree? Justify your response.

Consider the following tree:
1. What is the pre-order traversal of the tree?
2. What is the in-order traversal of the tree?
3. What is the post-order traversal of the tree?
4. What is the level-order traversal of the tree?
5. Identify if it is a tree, binary tree, BST, AVL tree
6. Based on your previous answer, draw the tree obtained by inserting 10 into the tree.
7. Draw the tree obtained by deleting 2 from the tree.
8. Draw both trees that might be obtained by deleting 4 from the tree while still maintaining the properties in your answer to e)

Consider a boolean function LinkedBST::containsInRange that takes as arguments two keys -- min and max -- and returns true if there exists a key k in the tree such that min <= k <= max. One possible implementation of this function is to call a recursive helper function that takes an additional argument -- a node in the tree, and returns whether that subtree contains any keys in the range:
```
  template <typename K, typename V>
  bool LinkedBST<K,V>::containsInRange(K min, K max) {
    return subtreeContainsInRange(root, min, max);
  }
```
Write the recursive helper function subtreeContainsInRange. You may assume that empty trees are represented by pointer to a NULL node.

For each of the code fragments below, draw the AVLTree that results from the code fragment:

  AVLTree<int,int> t;
  for (int i = 1; i <= 10; ++i) {
    t.insert(i,i);
  }

  AVLTree<int,int> t;
  for (int i = 1; i <= 5; ++i) {
    t.insert(i,i);
    t.insert(-1*i,-1*i);
  }

  AVLTree<int,int> t;
  for (int i = 1; i <= 5; ++i) {
    t.insert(i,i);
    t.insert(11-i,11-i);
  }

For each of the three code fragments above, draw the tree that would result if a LinkedBST were used instead of an AVLTree.

What is the worst-case running time of the following function? Use Big-O notation.

  void f(int n) {
    if (n < 0) {
      return;
    }
    AVLTree<int,int> t;
    for (int i = 0; i < n; ++i) {
      t.insert(i,i);
    }
    for (int i = 0; i < n; ++i) {
      cout << t.remove(i) << endl;
    }
  }

What is the smallest AVL tree such that removing a node requires a rotation to rebalance the tree? (There is more than one correct answer, but they're all the same size.)

What is the smallest AVL tree such that removing a node requires two rotations to rebalance the tree? (Again there is more than one correct answer, but they're all the same size.)

For each of the code fragments below, draw the BinaryHeap that results from the code fragment, and draw its final array-based representation:

  BinaryHeap<int,int> heap;
  for (int i = 1; i <= 10; ++i) {
    heap.insert(i,i);
  }
  for (int i = 1; i <= 5; ++i) {
    heap.removeMin();
  }

  BinaryHeap<int,int> heap;
  for (int i = 10; i > 0; --i) {
    heap.insert(i,i);
  }

  BinaryHeap<int,int> heap;
  for (int i = 1; i <= 5; ++i) {
    heap.insert(i,i);
    heap.insert(-1*i,-1*i);
  }

What is the worst-case running time of the following function? Use Big-O notation.

  void f(int n) {
    if (n < 0) {
      return;
    }
    BinaryHeap<int,int> heap;
    for (int i = 0; i < n; ++i) {
      heap.insert(i,i);
    }
    for (int i = 0; i < n; ++i) {
      cout << heap.removeMin() << endl;
    }
  }

Using chaining to resolve hash collisions, insert the following five items into a hash table of capacity 5, in the order given (from top to bottom):

Key Hash code

A 1

B 1

C 1

D 0

E 2

Repeat using linear probing to resolve hash collisions, instead of chaining.

Consider the following hash function, like the function in hashTable-inl.h:
```
  int hash(int key, int capacity) {
    return key % capacity;
  }
```
1. Complete the following code so that the total running time is asymptotically proportional to n^2:
```
  void f(int n) {
    HashTable<int,string> ht(n);  // Creates hash table with capacity n.
    for (int i = 0; i < n; ++i) {

      ht.insert(________________, "skittles");
    }
  }
```
2. Complete the above code so that the total running time is asymptotically proportional to n.
(In either case, assume that the hash table does not resize.)

Consider the following graph:
1. Give the adjacency-list representation of the graph.
2. Give an adjacency-matrix representation of the graph.

Play Charlie Garrod's Dijkstra Adventure Game by running dag in a terminal window. Be sure to play once or twice with the --random option:
```
  $ dag --random
```
(I'm sorry for how tedious the game can be -- the graph is big!)

In lab we saw a variant of recursive depth-first search. Recursive depth-first search is extremely simple and elegant if the algorithm does not need to track additional information or return any value:
```
  dfs(G, src):                           // This function initializes the
      isVisited = new dictionary         // dictionary and calls the
      for each vertex v in G:            // recursive helper function.
          isVisited[v] = false
      recursiveDfs(G, src, isVisited)

  recursiveDfs(G, src, isVisited):       // This recursive function
      isVisited[src] = true              // searches the graph.
      for each neighbor v of src:
          if !isVisited[v]:
              recursiveDfs(G, v, isVisited)
  
```
1. Execute dfs on the following graph, using s as the source vertex. Draw the stack frame diagram for the program as it executes. (Assume that isVisited refers to a single copy of the dictionary for all frames of the stack.)
2. Modify the pseudocode above to accept a second vertex, dest, as an argument. Return true if there is a path from src->dest in G, and return false otherwise.
3. Modify the pseudocode again to return the length of some src->dest path (not necessarily the shortest path) if there is a path from src to dest in G. If there is no src->dest path, return -1.
4. Write a version of breadth first search and depth first search that determines if a graph is connected.
5. Write a version of depth first search that returns all vertices in the same component as some source vertex.

Compare the run time of all key Graph methods using an adjacency list versus adjacency matrix representation. Express each in terms of the number of vertices (n) and edges (m) in the graph.
Execute Prim's algorithm to find a MST of the following graph using s as the initial vertex. For each step of the algorithm, show which edges and vertices have been selected for the MST up to that step.

Consider the following set of courses and their prerequisites:
- PHYS 005: none
- PHYS 007: PHYS 005 and MATH 025
- PHYS 008: PHYS 007 and MATH 033
- PHYS 014: PHYS 008, MATH 027, and MATH 033
- PHYS 050: MATH 027 and MATH 033
- PHYS 111: PHYS 014 and MATH 033
- PHYS 112: PHYS 014, PHYS 050, and MATH 033
- PHYS 113: PHYS 111 and MATH 027
- PHYS 114: PHYS 111 and MATH 033
- MATH 025: none
- MATH 027: none
- MATH 033: MATH 025
Assuming that a physics student can take only one course at a time, use a graph algorithm from this course to find a sequence of courses that satisfies the prerequisites. Show the graph on which you executed the graph algorithm.

What is the run time of breadth first search? depth first search? Dijkstra's? What about for a topological sort? How does the run time change if we use a stack, queue, or priority queue for the topological sort algorithm?

Key	Hash code
A	1
B	1
C	1
D	0
E	2