CMPS 144   Spring 2026
Final Exam Preview (5:15pm, Monday May 18, LSC 091)

You can expect that topics that did not appear on either mid-term exam will be emphasized more than those that did. In particular, that would include the topics covered since the second mid-term exam.

• Parallel Computing and Threads:
  • Parallel Algorithms: With respect to the relevant web page, be able to answer questions about the algorithms shown there (summing the elements of an array, RankSort), or to give a high-level sketch of a parallel algorithm that works in a manner similar to an example shown there.
  • Threads: Be able to describe how one might solve a computational problem (that is amenable to parallelization) in Java using threads. See Lab #14.
• Hashing and Hash Tables: (See Lab #14) Given a hash table (where open addressing is used with the linear probing collision resolution strategy),
  • compute the expected number of probes in both successful and unsuccessful searches (for the specific contents of that table), and be able to compare the latter number with how many probes could be expected to be made in an unsuccessful search, according to the formula (derived in class) that predicts the number of probes based solely upon the table's packing density.
  • show at which address a new <key,value>-pair would be inserted (given its key's home address).
  • show how any <key,value>-pairs would move within the table as a consequence of removing one of them.
• Binary Trees:
  • Huffman Trees/Coding: Given a list of symbols and their respective frequencies-of-occurrence, build a corresponding Huffman Tree and show the symbol-to-codeword mapping that the tree induces. (See Prog. Assg #5, algorithm and example, and another example.)
  • Heaps:
    • Be able to show how a max-heap would change as a result of inserting an element or of removing its maximum element. This would make it possible for you to trace execution of (one version of) the HeapSort algorithm. (Recall Lab #13.)
    • Be able to explain why a heap (or, more generally, a complete binary tree) is conveniently represented using an array (as opposed to a more complicated structure involving pointers/references to child and parent nodes).
  • Binary Search Trees: Given one, show how it would change as a result of inserting or deleting specified keys. (Recall Lab #12.)
• Recursion: (Recall Lab #10 and Prog. Assg. #4.)
  • Given a relatively simple recursive method, be able to trace its execution (e.g., by showing its effects when called with specified parameter values). Such effects would include what it prints, what value it returns, and how it may change the values of "global" variables or the states of objects passed to it (e.g., the contents of an array passed to it).
  • Given a relatively simple problem —involving numbers or an array, say— that is amenable to a recursive solution, be able to devise such a solution.
  • If a single instance of a recursive method could call itself multiple times, be able to show the tree depicting all instances of the method that get created (recall Lab #10: Array Sum))
  • Given a recurrence relation describing the running time of a recursive method/algorithm (as a function of some measure N of input size), be able to use the "repeated substittion" method to lead you towards a "solution". (See Recursion: Timing link on course web page.)
  • Given a recursive method, be able to express its running time as a recurrence relation. (See "Recursion: Timing" link on course web page.)
• Loop Invariants: Given some task to carry out, and a loop invariant to guide you, develop code to solve the problem in a manner consistent with the given loop invariant. (Recall the 2- and 3-color partitioning problems and Labs #4 and #5.)
• Lists:
  • With Cursors Paradigm: Given a relatively simple problem about lists, develop a Java method that uses the methods in the ListWithCursors and ListCursor interfaces to solve it. (Recall Lab #9.)
• Class Hierarchies/Extension
  • To provide extra functionality: Given a relatively simple Java class that lacks some desired functionality, develop a child class that provides that functionality. (Recall Lab #2.)
  • To provide alternative behaviors of some key method(s): Given a relatively simple Java class having an abstract method, develop concrete child classes that implement that method in ways that result in different behaviors. (See the Counter Class Hierarchy, Labs #3 and #3b.)

    A similar effect (of producing objects of the same class having different behaviors) can be achieved by using an instance variable that provides some particular functionality (e.g., comparison, classification) as described in a Java interface (e.g., java.util.Comparator (Lab #9), Predicate (Lab #10)). Also see Generic Comparator-based Sorting in Java. Indeed, this is usually a better approach than using extension.

• Stacks:
  • Applications: method call management, evaluation of expressions (Recall Lab #7 and Prog. Assg. #2.)
  • Implementation/representation: array-based, reference-based
• Queues:
  • Applications: breadth-first search (including finding shortest paths in a graph) (Recall Lab #8, Prog. Assg. #3.)
  • Implementation/representation: array-based, reference-based
• Manipulating Link1 objects. Recall Lab #8.