Thu, Oct 12	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 In general, sorting a list of N comparable items requires an O(N log N) algorithm. However, we discussed two specialized sorts, frequency lists and radix sort, that can do better but only if the data has certain properties. Describe one (1) of these specialized sorts and the properties the data must have in order to allow for improved efficiency. 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? Fall 2015 Midterm Exam
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 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 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 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 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