Prelim 2 study guide

The exam covers everything on Prelim 1, plus lectures 8–21 and their associated readings, discussion sections 5–10, quizzes 5–11, and assignments A3, A4, and 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

Data Structures

  • Abstract Data Types
  • Bag (resizable array implementation, linked implementation)
  • Linked lists
  • Stacks and queues

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)

Concurrency

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

Skills

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

  • Given a written description that includes text, diagram(s), and/or code, classify the entity being described as either an ADT or a data structure.
  • Name at least three kinds of data collections that are common examples of ADTs.
  • Given a real-world example of some data collection, either in written form or as a picture, choose one of the following ADTs as the most appropriate representation: Bag, List, Stack, Queue. Examples: a coin purse, the line to order at the Mattin’s sandwich counter.
  • You are given a real-world example of some data collection, either in written form or as a picture. You are also given one of the following ADTs: Bag, List, Stack, Queue. Identify one characteristic of the collection that makes the ADT unsuitable for representing it. Example: a coin purse and a List.
  • Describe at least four operations that are part of a Bag ADT. The descriptions must include a Java method signature for the operation, and a single sentence describing the main task performed by the operation. Precise preconditions/postconditions are not required for the descriptions.
  • Given a Java interface for a Bag, write a Java method that uses a Bag to perform a stated task. The method should contain no algorithmic errors. Example task: add the individual digits from a phone number to a Bag, then print the frequency of each digit in the number.
  • State one advantage and one disadvantage for each of these approaches to implementing a Bag: an array, a dynamic array, a linked chain of nodes.
  • Given the field declarations for a Bag implementation based on an array, write a class invariant that correctly constrains the relationships between the fields. Example: given fields for size, capacity, and an array, write an invariant that describes which indices of the array are non-null, and how those relate to the size field, and how the capacity field relates to the length of the array field.
  • Given a Java class for a Node, write Java code to construct a chain of linked nodes that contain three different data values. Also write Java code to construct a chain of two other linked nodes that both point to a single, shared data value.
  • Draw a node diagram representing a chain of linked nodes containing N different data values, where N is between 0 and 5 inclusive.
  • You are given a node diagram of a chain of linked nodes. You are also given a new data value. Draw the new node diagram that results from adding a new node to the beginning of the chain. The new node should contain the new data value.
  • Given the fields and class invariant for a Bag implementation (array or linked), and a specification for a Bag operation, implement that operation in Java in less than 5 minutes. The operation might be one we studied in class/readings, or it might be a new one. Example operations: add, contains, frequencyOf, remove a specified value, remove an unspecified value, etc.
  • Given the fields and class invariant for a Bag implementation (array or linked), and a specification for a Bag operation, identify whether the running time required by the implementation would be dependent or independent of the number of items in the bag. Examples: for the array implementation of a Bag with a field that tracks the number of items in the bag, the “size” operation is independent of the number of items, and the “remove specific item” operation is dependent.
  • You are given a series of operations performed on a List, and the specifications for those operations. The specifications identify whether the list uses 0-based or 1-based positioning. Draw the node diagram for the list at the end of that series. Example: addFront(0), addEnd(5), addAt(2, 3), remove(1).
  • Given the fields and class invariant for a LinkedList implementation, and a specification for a List operation, implement that operation in Java in less than 10 minutes. The operation might be one we studied in class/readings/A3, or it might be a new one. Example operations: addAt, addFront, addBack, get, remove at a specific position, remove an unspecified value, etc.
  • Given the fields and class invariant for a LinkedList implementation, and a specification for a List operation, identify whether the running time required by the implementation would be dependent or independent of the number of items in the bag. Examples: for the linked list implementation that has head and tail pointers, the “add at end” operation is independent; but if we had only a head pointer, that operation would be dependent.
  • You are given a series of push and pop operations performed on a Stack, followed by a peek operation. State the value returned by the peek.
  • You are given a series of enqueue and dequeue operations performed on a Queue, followed by a peek operation. State the value returned by the peek.
  • You are given the fields and class invariant for a Stack or a Queue. One of the fields is a Node or a List. Implement in Java a stated operation according to its specification. Example: the Stack is represented by a List field that keeps the most recent item at the beginning, and you have to implement the push operation by adding to the front of the Stack.

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

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

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.