Exam

Topics: through linked lists

• Book: Chapters 1 to 5, 6 (backtracking)
• Homeworks: 1 to 5
• Labs/Notes: through the 4/23-4/25 exercises on linked lists
• Terminology
• Invariants
  • loop invariants
  • class invariants
• Recursion
• Interfaces
  • used to specify Abstract Data Types (ADTs): a collection of data and operations on the data (whose representation is hidden).
  • consist of public components, such as public constants and public method headers (no method definitions/implementations) and comments (documentation for each method with preconditions, postconditions...).
  • have no constructors (only in concrete classes that implement the interface)
  • represent a contract between driver (external view) and implementer (internal view) of classes that implement the interface. The driver code need only be aware of the interface (what the methods do, not how they do it), and therefore would require very little change (calling a different constructor) in order to switch from one implementation of the interface to another.
  • e.g. textbook example: ListInterface, which is implemented by ListArrayBased and ListReferenceBased (linked list version).
• Principles/Features of Object-Oriented Programming (OOP)
  • Abstraction and Encapsulation (object-based)
  • Inheritance
  • Polymorphism

Format

• 1 or 2 problems: Recursion - review notes/slides/examples
  • Draw a box trace for a recursive method that we discussed, e.g. binarySearch, factorial
  • Write a small, recursive method (see examples for chapter on recursion)
• 2 or 3 problems: Know how to work with collections of objects, including arrays and ArrayLists (e.g. chapter 5 examples, lab exercises) and how to write a method that works with a list of integers, or a list of objects
  • external view where you are calling upon the methods specified in an interface such as ListInterface (e.g. exercises 1-3 of hw5, and the lab exercise where accounts or creatures are stored in a list)
  • internal view where you are implementing a method in the ListArrayBased or ListReferenceBased class (e.g the insert method we discussed that inserts an item into a sorted list, and the 4/23 - 4/25 lab exercises on lists, labeled "More list exercises").
• 1 or 2 problems: Write an invariant (for a loop or class).
• 2 problems: Inheritance and exception handling - review examples and exercises from class and lab, and the handout on exception handling.