CMPS 144   Spring 2025
Final Exam Preview

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.

• 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 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.
  • 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. (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. 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. #6.) 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 describe such a solution.

• 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 Lab #5.)
• Lists:
  • With Cursors Paradigm: Given a concrete array-based representation of a list with cursors, show how the instance variables would change as a result of inserting or removing an item. (Recall Lab #11.)

    Given a relatively simple problem about lists, develop a Java method that uses the methods in the PositionalListWithCursors and PositionalListCursor 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 and #8, and Prog. Assg. #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.)

  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). Recall Lab #9. 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. #3.)
  • Implementation/representation: array-based, reference-based
• Queues:
  • Applications: breadth-first search (including finding shortest paths in a graph) (Recall Lab #8, Prog. Assg. #5.)
  • Implementation/representation: array-based, reference-based
• Manipulating Link1 objects. Recall Lab #8.