Tue, May 7 (1:002:40) 

Format same as midterm 

Study advice 

Course material 
Data Structures Java review, arrays, generics, iterators inheritance, interfaces, polymorphism Collections List interface: ArrayList, LinkedList Set Interface: TreeSet, HashSet Map interface: TreeMap, HashMap Stack class, Queue interface, PriorityQueue class Graph interface: DiGraphList, DiGraphMatrix, GraphList, GraphMatrix lowlevel structures linked lists: singly vs. doubly, dummy nodes, iterators trees: hierarchical, recursive processing, binary search trees, heaps, heap sort, array implementation graphs: adjacency matrix vs. list hash tables: hash functions, load factor, rehashing collisions, clustering, probing vs. chaining Math Structures functions & sets bijections, mappings, sequences, sets & subsets linear structures lists, sets, maps nonlinear structures trees: root, leaf, child, path, height, weight, ... binary search trees, selfbalancing trees (redblack, AVL), heaps graphs: vertex, edge, adjacent, incident, degree, path, ... simple vs. directed, weighted vs. unweighted depth first search, breadth first search, finite state machines counting techniques bijection rule, product rule, sum rule, division rule, generalized product rule, n choose k, inclusion/exclusion rule, pigeonhole principle proof techniques direct proof, proof by contradiction, proof by induction Algorithm Analysis algorithm analysis best vs. average vs. worst case analysis bigOh notation, rateofgrowth analysis, bigOmega & bigTheta searching and sorting standard algorithm analysis, specialized sorting algorithms recursion recursive algorithms, recurrence relations Assignments 1. java review & design (credit card verification) 2. queues & efficiency (ArrayQueue vs. LinkedList) 3. lists & linked structures (ComboList) 4. proofs & counting (induction proofs, counting) 5. lists, trees & tries (Trie, memory/access comparisons) 6. treesets & text processing (WordSet) 7. maps & finite state machines (FSM, PathTracer, pathFinder) 