Thu, Oct 8	The test will include extra points (Mistakes Happen!), e.g., 103 or 104 points, but graded on a scale of 100.
Types of questions	factual knowledge: TRUE/FALSE, multiple choice TRUE or FALSE: When searching for an item in a list, the best case performances for both sequential search and binary search occur when the item is at the front of the list. conceptual understanding: short answer, discussion Suppose that a class for modeling a queue has been implemented using an underlying List data structure. Would the choice of List type, either ArrayList or LinkedList, affect the efficiency of the queue methods? Explain your answer. synthesis and application: explain/debug/analyze algorithm/code, trace/modify algorithm/code One way to determine if a list of numbers has any duplicate values is to first sort the list, then traverse it looking for adjacent identical values. Complete the definition of a method that implements this approach (you may use Collections.sort for the sorting step). What is the Big-Oh complexity of your method?
Study advice	review online lecture notes review the online texts (if not mentioned in class, won't be on test) look over quizzes, homework assignments reference other sources for examples, different perspectives
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)