Fall 2006

Test 1 Review

Java review class, object, fields, methods, private vs. public, parameters variables, primitive vs. objects, expressions, if, if-else, while, for object-oriented design: cohesion, coupling String, Math, arrays, ArrayList, generics interfaces, List, LinkedList, iterators searching and sorting, algorithm efficiency, recursion Stack class, Queue interface inheritance, polymorphism algorithm design and analysis big-Oh notation intuitive definition, formal definition rate-of-growth analysis searching sequential search: O(N) worst/average case, O(1) best case binary search: O(log N) worst/average case, O(1) best case sorting insertion sort: O(N^{2}) worst/average case, O(1) best case selection sort: O(N^{2}) worst/average/best case merge sort: O(N log N) worst/average/best case quick sort: O(N log N) average/best case, O(N^{2}) worst case specialized sorts if limited range of values, sort via frequency list: O(range * N) if can compare by digit/char, radix sort: O(maxLength * N) recursion base case(s), recursive case(s) analysis via recurrence relation inheritance and efficiency derived classes extending a class vs. implementing an interface overriding methods, calling parent methods/constructors with super polymorphism List --> ArrayList --> SortedArrayList divide-and-conquer algorithms examples: merge sort, quick sort, Euclid's gcd, ... divide-and-conquer characterizations: binary search, sum of list, ... Java Collections and list implementations Collection interface, many useful static methods in Collections List interface (extends Collection) ArrayList (implements List): underlying array representation O(1) add/remove at end, O(N) add/remove from beginning/middle O(1) access, O(N) search LinkedList (implements List): underlying doubly-linked list representation O(1) add/remove at beginning/end, O(N) add/remove from middle O(1) add/remove if have access to location, O(N) access/search Set interface (extends Collection) TreeSet (implements Set): underlying ordered binary tree representation O(log N) add/remove/search HashSet (implements Set): underlying hash table representation O(1) add/remove/search on average, O(N) worst case Map interface TreeMap (implements Map): underlying ordered binary tree representation O(log N) add/remove/search HashMap (implements Map): underlying hash table representation O(1) add/remove/search on average, O(N) worst case iterators Iterator interface: hasNext, next, remove ListIterator interface: hasPrevious, previous, add, set