Test 3 study guide

The test covers lectures 10–14 and their associated readings; discussions 4 and 5; and assignment A3. That is approximately all the material covered during the week of July 8th 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

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)

Comparisons

  • Comparable and Comparator

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.

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

Study tips

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