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, if-else, while, for object-oriented 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 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 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 singly-linked lists, next references, front and/or back references doubly-linked lists, previous & next references, front & back dummy nodes Algorithm Analysis best vs. average vs. worst case analysis big-Oh notation intuitive definition, formal definition rate-of-growth analysis big-Omega, big-Theta 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(N2) worst/average case, O(N) best case selection sort: O(N2) worst/average/best case merge sort: O(N log N) worst/average/best case quick sort: O(N log N) average/best case, O(N2) 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) |