Prelim 2 study guide

The exam covers everything on Prelim 1, plus lectures 13–22 and their associated readings, discussion sections 7–11, quizzes 7–9, and assignments A4–A5.

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

Trees

  • Terminology: leaf, parent, size, height, subtree, …
  • General vs. binary trees
  • Tree traversal orders: preorder, inorder, postorder
  • Binary search trees; implementing “find” and “add”
  • Recursive algorithm patterns: counting vs. searching
  • Asymptotic complexity of operations on general trees vs. BSTs
  • Possible height of a BST (perfect tree vs degenerate list)

Loop invariants and searching

  • The loop checklist, aka the “four loopy questions”
  • Array diagrams; array range notation
  • Developing loops with an invariant
  • Termination and the “loop variant”

Sorting and comparisons

  • Stability
  • Asymptotic complexity (time and space, best case and worst case)
  • Algorithms and their loop invariants: insertion sort, selection sort, merge sort, quicksort
  • Comparable and Comparator

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

Graphs

  • Terminology (vertices, edges, (un)directed, paths, cycles)
  • Representation (adjacency list, adjacency matrix)
  • Breadth-first search
  • Depth-first search
  • Topological sorting
  • 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

Skills

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

  • Given a diagram of a tree, circle examples of the following: leaf, parent and child, subtree, root, interior node, siblings and descendants and ancestors of a given node.
  • Given a diagram of a tree, state its size and height.
  • Given the size of a binary tree, state its minimum and maximum possible height.
  • Given a diagram of nodes connected by edges, state whether it is a tree.
  • Given a diagram of a tree, state whether it is a binary tree.
  • Given a diagram of a binary tree, state whether it is a valid binary search tree (BST).
  • Given a diagram of a tree with children ordered left to right, enumerate the nodes visited by a preorder or postorder traversal.
  • Given a diagram of a binary tree, enumerate the nodes visited by an inorder traversal.
  • Given a recursive algorithm for processing a tree, state whether it is a “counting” or “searching” algorithm. Examples: methods in A4.
  • Given the declaration of a “tree node” class for a general tree, implement a recursive method to query the tree in a specified way. Example: return the depth of a node containing a given value.
  • Given the declaration of a BST node class, implement a recursive or iterative method for a specified operation. The operation might be familiar from the textbook or lecture, or it might be new. Examples: “contains”, “add”, find the minimum value in the tree, or find the largest value below some limit. Node values may be primitive types or subtypes of Comparable, or a Comparator may be provided.
  • Using Big Oh notation, state the time and/or space complexity of a general tree or BST operation in terms of the tree’s size or height.

  • From memory, state the “loop checklist” aka “the four loopy questions.” In your own words, explain what each question means.
  • Given a range notation, state the numbers contained in the sequence it identifies. Examples: [1..5], (1..5), a[..5), a[1..]. In the latter examples, a is an array.
  • Given an array diagram, and an index, state what properties must hold of the array element at that index according to the diagram.
  • Given a precondition and postcondition, and an English description of the intuition for a loop-based algorithm, state a loop invariant that would correctly implement the algorithm. Example: precondition is “array is unsorted”, postcondition is “array is sorted”, intuition is “a sorted segment of the array grows from the left to the right; an unsorted segment of the array likewise shrinks from the left to the right; nothing is known about the elements in the unsorted segment.” (That is insertion sort, by the way.)
  • Continuing the above skill: also state a loop variant, that is, a function that decreases with each loop iteration and cannot decrease infinitely.
  • Given some Java code for a loop, possibly with some pieces missing, draw a dot at the points where the loop invariant must hold, and where it might not.
  • You are given some Java code for a loop, with some pieces missing. You are given the precondition, postcondition, loop invariant. Fill in the missing pieces to make the loop correct. Or, the loop code is complete, but the invariant is missing; state the invariant that makes the loop correct. Or, select which of several loop invariants would be correct.
  • You are given the Java code for a loop, the precondition, the postcondition, and the loop invariant. Explain in your own words why the loop checklist (aka the four loopy questions) is satisfied.
  • Note that the last two skills above for loop invariants could be instantiated with a linear or binary search loop, or a tweak on one of those.
  • In your own words, describe the linear and binary search algorithms.

  • Among selection sort, insertion sort, merge sort, and quicksort, identify which algorithms are stable, and explain why.
  • State the best-case time complexity for insertion sort and quicksort and describe the conditions in which it is achieved.
  • State the worst-case time complexity for selection sort, insertion sort, merge sort, and quicksort.
  • State the best-case space complexity for selection sort, insertion sort, merge sort, and quicksort.
  • Given some properties about an array to be sorted, along with performance constraints, select the most appropriate sorting algorithm. Example: which algorithm would be preferred if it is known that only a couple of elements are out of order?
  • Given a loop invariant in array range or array diagram notation, state whether it is consistent with the outer loop of selection sort, the outer loop of insertion sort, an insertion procedure for insertion sort, or a partitioning algorithm for quicksort.
  • Implement selection sort, insertion sort, and a partition procedure for quicksort, given relevant loop invariants. Values may be primitive types or subtypes of Comparable, or a Comparator may be provided.
  • Implement merge sort and quicksort, given the specifications for “merge” and “partition” methods (which you do not need to implement).
  • Given a class with two fields, implement the Comparable interface for it so that instances are ordered first by one field, then, in the case of a tie, by the other field.
  • Given a class with two observers, declare and implement a Comparator that orders instances of the class first by one observable, then, in the case of a tie, by the other.

  • 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.

  • Given a drawing of a graph, perform the following tasks:
    • Write the set of vertices, write the set of edges, state whether the graph is directed or undirected. Or vice-versa, given the vertex and edge sets, draw the graph, and state whether it is directed or undirected.
    • State whether a given sequence of vertices is a legal path in the graph. Or, write down all the paths in the (small) graph, and their lengths.
    • Redraw the graph, which now must be undirected, as a directed graph with the same set of vertices and paths.
    • State the length and/or weight of a given path in the graph.
    • Circle which of several adjacency list representations corresponds to the drawing. Or vice-versa, given a representation, draw the graph, or circle which drawing is correct. Likewise, do the same for adjacency matrix representations.
  • Given a representation (adjacency list or matrix), perform the following tasks:
    • State in Big Oh notation the space requirements to store a graph using that representation, based on the number of vertices and edges.
    • State the time and/or space complexity of an operation on the graph based on an English description of the operation, or on Java (pseudo)code implementing the operation. The operation might be one we studied, or it might be new. Your answer must be in the form of a Big Oh tightest bound.
    • Given the fields and class invariant for implementing the representation, and given a specification for an operation, write the Java code for that. The operation might be one we studied, or it might be new.
  • Given some criteria—for example, about the size and density of the graph, and about which operations will be most frequent—choose the most suitable data structures to represent a graph. If an adjacency list representation is most suitable, that could include choosing data structures for the vertex set and adjacency lists.
  • Given a diagram of a graph, state whether it is acyclic. If not, trace a path that forms a cycle.
  • Given a diagram of a directed acyclic graph, state a topological ordering of its vertices. Or, circle which of several sequences of vertices correspond to a topological ordering.
  • Given a diagram of a graph, a starting node, and a rule for the order in which neighbors are iterated (for example, alphabetical order by vertex label), state the order in which nodes are visited during a breadth-first or depth-first traversal. Or, state the order in which nodes are settled during a depth-first traversal.
  • 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.

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.