Thu, Oct 13 

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 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 used by the enahnced for loop to traverse the list efficiently Stack class (extends Collection, 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 frequency list (if limited range of values): O(range * N) radix sort (if can compare by digit/char): O(maxLength * N) counting techniques rules: bijection, product, generalized product, sum, division binomial coefficient, pigeonhole principle proof techniques direct proof, proof by contradiction, proof by induction 