Thu, Oct 8 

Types of questions 

Study advice 

Course material 
Java review class, object, fields, methods, private vs. public, parameters variables, primitive vs. objects, expressions, if, ifelse, while, for objectoriented design: cohesion, coupling String, Math, arrays, ArrayList, generics interfaces, List, LinkedList, iterators searching and sorting, algorithm efficiency, recursion interfaces, inheritance, polymorphism GUI building Data Structures 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 doublylinked 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 iterators Iterator interface: hasNext, next, remove ListIterator interface: hasPrevious, previous, add, set Stack class (extends Collectio, implements List) FILO/LIFO list operations: push, pop, peek, empty Queue interface (extends Collection) FIFO/LILO list operations: add, remove, peek, empty implemented by LinkedList class linked structures nodes, references singlylinked lists, next references, front and/or back references doublylinked lists, previous & next references, front & back dummy nodes Algorithm Analysis best vs. average vs. worst case analysis bigOh notation intuitive definition, formal definition rateofgrowth analysis bigOmega, bigTheta recurrence relations for analyzing recursion unwinding a recurrence relation 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(N) 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) 