Thu, Mar 2	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 conceptual understanding: short answer, discussion synthesis and application: explain/trace/modify code, analyze an algorithm, ... Sample Midterm Questions
Study advice	review online lecture notes review the text book (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/Data Structures review OO design: cohesion, coupling, interfaces, inheritance, polymorphism data structures: List, Set, Map, Graph, Stack, Queue algorithm efficiency: big-Oh, rate-of-growth, iteration, recursion Brute force approach focus on solving in simplest way - don't worry about extensibility/reuse exhaustive search, generate & test, nP-hard problems examples: invoice handling, string matching, N-queens, knapsack, dictionary Decrease & conquer approach reduce problem to a similar problem of a smaller size top-down (recursive) vs. bottom-up (iterative) implementations decrease by constant: insertion sort, topological sorting decrease by constant factor: binary search, fake coin problem decrease by variable amount: search/insert into BST, quick select Divide & conquer approach reduce problem to multiple subproblems, combine answers Master Theorem examples: merge sort, quick sort, closest pair, large int multiplication, exhaustive tree recursion (e.g., size, contains, toString) Transform & conquer approach transform problem into a more easily solved one examples: presorting, BSTs (AVL, red-black), heaps, Horner's rule problem reduction: lcm --> gcd, graph searches space vs. time additional storage can often allow for a more efficient algorithm examples: ArrayList resize, linked structures, heap sort, hash tables examples: AnagramFinder, BinaryTree string matching: brute force, Horspool, Boyer-Moore Greedy approach solve by making a sequence of choices/actions, select locally optimal examples: minimal change, job scheduling, minimal spanning tree: Prim's algorithm shortest path: modified BFS, Dijkstra's algorithm data compression: Huffman codes