CSC 222: Computer Programming II
Spring 2005
Test 2 Review
TEST 1 MATERIAL
Searching and efficiency
sequential search vs. binary search
worst case vs. average case vs. best case performance
Collections.binarySearch, List & Comparable interfaces
application: Dictionary class, spell checking
Big-Oh notation
sequential search is O(N), binary search is O(log N)
rate-of-growth behavior
Sorting and recursion
insertion sort vs. selection sort vs. merge sort
worst case vs. average case vs. best case performance
implementing an O(N) merge
mixing selection & merge sorts
Collections.sort, Collections.shuffle
application: Dictionary class, fastAdd method
Big-Oh analysis
insertion & selection sorts are O(N^2), merge sort is O(N log N)
recursive analysis
formal definition of Big-Oh
Inheritance
derived class inherits fields & methods from parent class
extends keyword
can add new fields & methods, override inherited methods
IS-A relationship: object of derived class is an instance of parent class
can assign object of derived class to variable of parent class
can pass object of derived class to method with parent class parameter
polymorphism
the same method call can refer to different code on different objects
compiler is "smart enough" to call the appropriate method version
allows for general methods that work on an entire hierarchy of classes
examples
BankAccount --> SavingsAccount, CheckingAccount
Die --> ColoredDie
Actor --> Rock, Critter, ...