CS 2110: Object-Oriented Programming and Data Structures

Final exam study guide

The final exam is cumulative. It covers everything on the Prelim 1 and Prelim 2 study guides, plus lectures 19–26 and their associated readings, discussion sections and quizzes 10–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: 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

Concurrency

  • Threads
  • Race conditions
  • Deadlock
  • Mutex locks (synchronized)
  • Condition variables (wait()/notifyAll())
  • Ring buffers
  • Barriers

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

Design patterns

  • Iteration (Iterator and Iterable), enhanced for-loops
  • Alternatives to null (optional aka Maybe)

Skills

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

  • Given two sequences of instructions (in pseudocode or Java) that are executed concurrently and require exclusive access to one or more shared resources, state whether deadlock is possible. If so, propose an alteration to one of the sequences that eliminates this possibility while preserving the desired behavior of the original instructions.
  • Given two or more sequences of Java statements that are executed concurrently and that access shared objects, state whether a race condition may be encountered, and what class invariants might be invalidated because of the race condition. Or, add synchronization to the code to prevent race conditions.
  • Given two sequences of Java statements that are executed concurrently and that increment a shared int variable with or without synchronization, state which numbers are possible final values for the variable after both sequences have completed execution.
  • Given the implementation of a method that employs synchronization, state which object is serving as the mutex.
  • Given the implementation of a method that employs synchronization, circle which statements could cause a thread to block, and for each such statement, describe what another thread could do to cause the first thread to become unblocked.
  • Given an abbreviated reference for the API of Java’s Thread class, write code to execute a function on a new thread.
  • Given a sequence of addition and removal operations made to a circular buffer with a specified capacity, draw the contents of its backing array after those operations have completed.
  • Given a specification for the desired behavior of a class, and a partial implementation of the class, add code that uses condition variables (i.e., wait and notifyAll) to complete the implementation. The code you add causes threads to correctly synchronize by making some threads block and wait for others. Example: Barrier from DIS.
  • Not in scope: Swing Event Dispatch Thread

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

  • 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. Out of scope: coroutines.
  • Describe a situation in which returning a Maybe is preferable to possibly returning null. Or, given an API for Maybe, rewrite code that potentially throws a NullPointerException to instead use Maybe and thereby avoid the possibility of that exception.

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.