Final exam study guide

The final exam is cumulative. It covers everything on the Prelim 1 and Prelim 2 study guides, plus lectures 25–28 and their associated readings, discussion section 13, quizzes 12–13, and assignment A6.

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: we may overlook missing semicolons or unambiguous spelling/capitalization mistakes, but ambiguous or structurally invalid code will be penalized.

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

Design patterns

  • Design patterns (purpose, specification)
  • Iteration (Iterator and Iterable), enhanced for-loops
  • Iterators for tree and graph traversals

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.

  • Write a recommendation for whether it would be appropriate to deploy a particular design pattern to address a programming challenge. The pattern might be one of “Iterator” or “Factory method”, or a description of a new pattern may be provided.
  • Write a while-loop to perform an operation on every element contained in an Iterable collection.
  • Given the implementation of a collection, write the methods of an Iterator class to yield the collection’s elements in a specified order. Examples: preorder or level-order traversal of a tree.

Study tips

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

Sample exams

Here are some examples of exams from past courses covering similar material. Please note: these examples cover topics that are not in scope for our exam this semester, and they do not cover all topics that are in scope for our exam. The organization and style of questions on these exams is not necessarily indicative of what you will see this semester. Some notational conventions differ between other courses and ours.

Merely reading solutions is ineffective for knowledge retention. Pro-tip: do not look at the solutions until you have already solved the problems and checked your answers using your notes, IntelliJ, and/or a study partner.