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, ...