Fall 2018

Final Review

- To understand fundamental data structures (lists, stacks, queues, sets, maps, and linked structures) and be able to implement software solutions to problems using these data structures.
- To achieve a working knowledge of various mathematical structures essential for the field of computer science, including graphs, trees, and networks.
- To develop analytical techniques for evaluating the efficiency of data structures and programs, including counting, asymptotics, and recurrence relations.
- To be able to design and implement a program to model a real-world system, selecting and implementing appropriate data structures.

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 low-level 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, balanced trees (red-black, 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 big-Oh notation, rate-of-growth analysis, big-Omega & big-Theta 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. linked structures (SpliceString, splice onto end) 4. linked structures (SpliceString, splice into middle) 5. recursion & binary search trees (height & weight, avg search cost) 6. maps & finite state machines (FSM PathTracer, pathFinder)