CMPS 144   Fall 2025
Final Exam Preview

• Hashing and Hash Tables: 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 that specific table), and be able to compare the latter number with how many probes could be expected to be made in an unsuccessful search, based only upon the table's packing density (per the formula developed in lecture that produces this number).
  • show at which address a new <key,value>-pair would be inserted (given its key's home address).
  • show the effects of removing a specified <key,value>-pair from the table, and explain why such a removal might require that <key,value>-pairs remaining in the table be moved to different locations.
• 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-binary-codeword mapping that the tree induces. (Recall Lab #14.)
  • Heaps:
    • Be able to show how a max-heap would change as a result of inserting an element or of removing its maximum element. (Recall Lab #14.) This would make it possible for you to trace execution of the HeapSort algorithm (Phase 1 of which builds a heap containing the elements in the collection to be sorted and Phase 2 of which removes those elements in order from greatest to least). (Recall Prog. Assg. #6.)
    • 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 and memory-intensive 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 #14.)
• Recursion: (Recall Labs #11-13 and Prog. Assg. #5.) Given a relatively simple recursive method, be able to trace its execution (e.g., by completing a table showing, for each "instance" of the method, the values of the parameters it received and the value it returned). More generally, be able to describe the effects produced by a call to such a method (with specified parameter values), including 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 describe such a solution.

• Lists:
  • Recursive Paradigm: Be able to develop a recursive Java method that solves a relatively simple problem (e.g., count how many negative numbers are in a "recursive list" of integers). (Recall Lab #12.) Also, be able to trace execution (manually) of such a method (as discussed above).
  • With Cursors Paradigm: Given a relatively simple problem pertaining to lists, develop a Java method that uses the methods in the ListWithCursors and ListCursor interfaces to solve it. (Recall Lab #10.)
• 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 #5 and #6.)
• 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 #3.)
• 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, Lab #4, and Prog. Assg. #2.)

  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 or RedBlueClassifier from Lab #10). Also see Generic Comparator-based Sorting in Java. Indeed, this is usually a better approach than using extension.

• Runtim Polymorphism (Dynamic Method Dispatch): Given a hierarchy of Java classes (e.g., any among TossableCoin, Counter, or SixSidedDie and its descendants) and a client program that creates objects from various classes of that hierarchy, be able to tell, for a particular method call upon such an object, which version of that method (from among the possibly multiple versions of that method found in the classes in the hierarchy) will actually be executed. Also be able to tell whether a given method call will be flagged by the Java compiler as being illegal.

  For example, if coin is a variable declared to be of type Coin but it is bound to an object of the class BiasedCoin (as would happen as a result of an assignment statement such as coin = new BiasedCoin(0.4)), the version of the toss() method executed as a result of the call coin.toss() is the one found in the BiasedCoin class (which overrides the version of the method inherited from its parent Coin class).

  Meanwhile, if coin is declared to be of type Coin, then the call coin.headsProbability() will be flagged as an error by the Java compiler, regardless of whether or not that call occurs in a context in which it is guaranteed that coin would have been bound to an instance of the BiasedCoin class. (Recall that the method headsProbability() does not exist in the Coin class but rather was introduced in its child class BiasedCoin.)

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