CS 2110: Object-Oriented Programming and Data Structures

Prelim 2 study guide

The exam covers everything on Prelim 1, plus lectures 11–18 and their associated readings, discussion sections 7–9, quizzes 6–9, and assignments A4 and A5. That is approximately all the material covered before Spring Break and all the activities related to that material (even if the activity occurred after break).

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

Efficiency

  • Big-O notation
  • Time and space complexity
  • Best case vs. worst case
  • Space complexity of recursive functions
  • Analyzing complexity of nested loops
  • Application to searching algorithms (linear and binary search)

Recursion

  • Recursive methods and recursive static functions
  • Termination and base cases
  • Recursive data types
  • Activation records and the call stack

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

GUIs and lambda expressions

  • GUI widgets
  • Swing components
  • Inversion of control
  • Events, event sources, and event handlers
  • Anonymous functions and functional interfaces
  • Control flow of painting
  • The event dispatch thread (EDT)

Skills

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

  • Match each of these complexity classes to its common name: \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n^2)\), \(O(2^n)\). (Common names: constant, logarithmic, linear, quadratic, exponential.)
  • Given the common names of several complexity classes, order them from smallest to biggest. Example (not in order): exponential, constant, linear.
  • Given a growth-rate function, indicate which of several Big Oh sets it is in, and further indicate which of those is the tightest bound. Example: function is \(42 n^2 + 3 n + 7\), sets are \(O(1)\), \(O(n)\), \(O(n^2)\), \(O(2^n)\).
  • Use the definition of Big Oh to show that a growth-rate function is in \(O(n)\) or \(O(n^2)\) by stating suitable constants \(c\) and \(N\). Example: show that \(42 n^2 + 3 n + 7\) is in \(O(n^2)\). Out of scope: a proof involving logarithms.
  • Given an English description of an algorithm, state what quantity describes the problem size, and state the algorithm’s worst-case time complexity using Big Oh notation. Example: compute the sum of the integers stored in an array.
  • Variants of the above skill: Java code instead of an English description; best-case instead of worst-case; space instead of time.
  • Out of scope: Big Omega and Big Theta notation. The exam will use only Big Oh, but we do expect you to be able to give the tightest Big Oh bound for both best and worst cases.

  • Given the implementation of a recursive function, describe its base case in your own words.
  • Given a recursive function and some argument values, write the sequence of calls to the function and the output it returns from each call.
  • Variant of the above skill: draw the call stack at a given point of execution, or state the maximum depth of recursion.
  • Given a recursive function, state its space complexity in Big Oh notation as a function of its parameters.
  • Given a recursive static function operating on a data structure, convert the function to an instance method in the data structure’s class (or vice versa).
  • Implement a specified function using recursion. The problem to be solved can be broken into identical but smaller problems. Example: determine the number of ‘7’ digits in a number’s decimal form, leveraging the quotient and remainder when the number is divided by 10.
  • Given a function’s implementation, draw the contents of its activation record (excluding the program counter / return address) in object diagram notation.

  • 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 an interface, state whether a lambda expression could be used to provide that interface. Example: ActionListener, which declares one abstract method named actionPerformed().
  • Write a JUnit assertion to check that a given expression results in an exception being thrown.
  • Write a lambda expression to be passed as an argument to a method expecting a functional interface. Examples: write an expression for an ActionListener to print a message when a button is pressed; write an expression for a Comparator to order students by age when sorting them.
  • Match a picture of a standard GUI widget to its name. Widgets could include labels, buttons, text fields, sliders, radio buttons, progress bars, and scroll bars.
  • Given a picture of a window containing bordered panels and standard widgets, sketch a hierarchy of how the components could be contained within one another (the frame will be at the root).
  • Given a sketch of a GUI with labels indicating variable names that reference each widget, write the code to cause a component to react in a specified way. For example, make a button change the text of a label when clicked. A sufficient subset of the Swing API will be provided for reference.
  • Given a snippet of Swing code that registers an event listener, identify the the event source, the event object, and the listener.
  • Given a desired outcome (example: notify Swing that a component’s appearance needs to change), circle which painting-related method (e.g. repaint(), paintComponent()) should be called or overridden.
  • Not in scope: Model-View-Controller.

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.