Final exam review

Comprehensive part:

Object-oriented programming and the Java language

• Classes and objects
• Object creation and deletion
• Constructors, finalizers, accessors, and mutators
• Subclasses and inheritance
• Abstract classes and methods
• Interfaces
• Iterator
• List
  
• Comparable
  
• Packages
• Access Control
• Exceptions

The List interface

• Definition
• Implementations
• Array
• Linked list
• head and tail pointers
• doubly-linked
• circular
• recursive

Sorted lists

• Interface
• Semantics
• Implementations
• Array
• Linked List
• Binary Search

• big-oh notation -- know the definition
• running times for common algorithms

Since the midterm:

Stacks, queues, deques, and priority queues

• Interface
• Semantics
• Implementations
• Array
• Linked List

Arithmetic expressions

• infix, prefix, and postfix notations
• infix-to-postfix algorithm
• evaluate postfix algorithm

• Definition
  
• Implementation
• binary search tree
• hash table

Object-oriented design and analysis

• CRC method
• UML diagrams
• use case
• sequence
• class

Trees

• Basic terminology
• Binary trees
• Tree traversals
• Expression trees
• Implementing binary trees
• Implementing nonbinary trees
• Tries
  
• Tree iterators
• Cloning a binary tree
• Binary search trees
• Balancing a binary search tree
• AVL trees
• Red-black trees
  

Hashing

• Basic concepts
  
• Hash function design
• Collision handling
• Open addressing.
• Linear probing.
• Double hashing
• Chaining
• Chained scatter tables
  
• Separate chaining

Sorting

• Elementary sorting methods
• bubble sort
• insertion sort
• selection sort
• Merge sort.
• Heaps.  Heapsort.  Priority queues.
• Quicksort.