Test 5 study guide

The test covers lectures 20–22 and their associated readings; discussions 8 and 9; and assignment A3. That is approximately all the material covered between Monday July 22nd and Thursday July 25th (inclusive) and all the activities related to that material.

The exam will ask you to write correct and stylish Java code. Your code should not be redundant, needlessly inefficient or complicated, or indicate a lack of understanding of Java features. Your code should follow our coding guidelines, with one exception: unless comments are specifically requested, you may omit them on the exam. Your code should contain at most minor syntactic errors: syntax errors that can be corrected by (i) a local insertion or deletion of punctuation and/or whitespace, (ii) corrected spelling of identifiers, or (iii) transposition of adjacent tokens. In other words, a malformed program that an experienced programmer can nonetheless understand unambiguously with a second or two of thought.

The exam will not allow access to reference materials. You will not have access to notes, a “cheat sheet”, or IntelliJ, or the Java API documentation. Except: if there is a Java API method you must use to solve a problem not listed among the topics below, we will provide a brief specification for it.

List of topics

Graphs

  • BFS for unweighted shortest paths
  • Dijkstra’s single-source shortest path algorithm

Heaps

  • Priority queue ADT
  • Heap invariants
  • Heap operations (bubble-up, bubble-down)
  • Array representation of complete trees
  • Heapsort

Dictionaries & hashing

  • Hash codes and index derivation
  • Consistency of hashCode() and equals()
  • Collision resolution: chaining vs. linear probing
  • Load factor
  • Resizing
  • Asymptotic complexity of operations for chaining

Skills

To do well on the exam, you should be able to do the following:

  • Given a diagram of a graph with edge weights and a starting node, state the order in which nodes are settled by Dijkstra’s shortest path algorithm.
  • Given a diagram of a graph with edge weights and a starting node, state the contents of the frontier (that is, the nodes in the frontier, their candidate shortest-path distances, and their back pointers) immediately after a given node would be settled by the algorithm. That is, trace the execution of Dijkstra’s algorithm on a given graph, and write the state of the algorithm at a specified point.
  • Given a table of destination nodes and back pointers produced by BFS or Dijkstra’s algorithm, construct the shortest path from the starting node to a destination.
  • Given a snapshot of the frontier set (including distances and back pointers) during an execution of Dijkstra’s algorithm, state lower and upper bounds for the distances of the final shortest paths to each of the nodes in the set. Examples: Canvas quiz questions.

  • Given a diagram of a tree, state whether it is a valid min-heap or max-heap. If it is not, explain how it violates a heap’s invariants.
  • Draw a diagram of a complete binary tree given its array representation. Or vice versa.
  • Given the index of a node in a complete binary tree represented as an array, state the array indices of the node’s left and right children and of its parent.
  • Given the contents of a heap (either as a tree diagram or as an array), draw the state of the heap after performing a sequence of “add” and “remove” operations.
  • Given the fields of a heap class and its methods’ specifications, implement the “bubbleUp” and “bubbleDown” operations for a heap represented as an array. The heap may be a min-heap or a max-heap, and priorities may be compared as primitives, as Comparables, or with a Comparator.
  • Describe a situation in which the behavior of heapsort would be preferred over merge sort, or vice versa. Example: a situation calling for stability and/or constant space complexity.
  • You are given code that implements an operation (examples: “add”, “remove”, “peek”) of a priority queue. The code uses a particular data structure (examples: heap, binary search tree, sorted linked list). You must determine and state the worst-case efficiency of the operation. Or, you are told what operation to implement and what data structure to use, and you must write the code yourself.

  • Given an “entry” class, implement a dictionary’s “put” and “get” operations using a binary search tree data structure.
  • State the worst-case time complexity of a dictionary’s “put” and “get” operations if entries are stored in a sorted or unsorted list.
  • Evaluate a proposed hashCode() method in terms of collision avoidance and consistency with equals().
  • Given a key’s hash code and the length of a hash table array, state which element of the array the key should be stored under if indices are derived by taking the positive remainder mod the table length.
  • Given a key’s hash code and the contents of a hash table array, state which element an entry with that key would be stored in if linear probing is used to resolve collisions.
  • Given the contents of the buckets of a hash table using chaining and the hash codes of all keys stored in it, draw the table and its buckets’ contents after the table is resized to a given new size, assuming indices are derived by taking the positive remainder mod the table length.
  • Given the contents of a hash table, compute its load factor.
  • Given the load factor of a hash table using chaining, state the expected number of comparisons needed to search for a random key.

Study tips

To prepare for the test, we recommend the following study habits: