Test 4 study guide

The test covers lectures 15–19 and their associated readings; discussion 6; and assignment A3. That is approximately all the material covered on the week of July 15th (excluding shortest paths) 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

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

Graphs

  • Terminology (vertices, edges, (un)directed, paths, cycles)
  • Representation (adjacency list, adjacency matrix)
  • Breadth-first search
  • Depth-first search
  • Topological sorting

Skills

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

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

Study tips

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