## CS 314: Study Guide for Final Exam

### Date: Friday, December 13, 9-12 AM in Hogg Memorial Auditorium, HMA

(next to Flawn Academic Center, northwest of the Tower). A makeup exam from 7-10 PM on Dec. 13 will be in CPE 2.218 for students who have conflicting exams; contact the instructor if you have a conflict.

Weiss, Data Structures & Problem Solving Using Java, Sections 1, 5 - 5.2, 2 - 2.4, 17.1, 7 - 7.3.4, 17.3, 17.4, 11 - 11.1, 6 - 6.6, 16, 18 - 18.4, 19 - 19.1, 19.3, 18.4, 19.4, 19.8, 20 - 20.3.1, 20.5 - 20.7, 6.9, 21 - 21.2, 13.2, 8 - 8.3, 8.5 - 8.8, 14; class lecture notes; MapReduce paper.

### Material covered in class:

• Trees:
• Depth-first search
• Balanced binary trees
• AVL tree, Red-Black tree, Splay tree
• B-tree
• Sparse Arrays
• Pattern Matching:
• Substitution, subst, sublis
• Tree equality, equal
• Pattern matching, match
• Transformation, transform
• Uses of pattern matching
• Java API's:
• Collection
• Set
• TreeSet
• Map, HashMap, TreeMap
• Comparator
• Hashing:
• How hashing works; O(1)
• Hash functions; XOR
• Collision, rehash, clustering, load factor
• Hashing with buckets
• Hash table resizing
• Extendible hashing
• Randomized algorithms
• Priority Queues:
• Ordering of a priority queue
• Uses of priority queue
• Binary heap
• Discrete event simulation
• Greedy algorithms
• Sorting:
• Best possible Big O is O(n*log(n)). Know the Big O and properties of each kind of sort.
• Insertion sort
• Heapsort
• Merge sort
• Quicksort
• Graphs:
• Examples of graphs
• Path, cycle, cost of a path, shortest path
• Dijkstra's algorithm
• Prim's algorithm
• A* algorithm
• MapReduce:
• mapcar, reduce
• MapReduce, key/value produced by Map, collection process, key/list-of-values processed by Reduce
• Parallelism, network bandwidth, master/slave, fault tolerance

### Vocabulary

>
 A* acyclic adjacency list adjacency matrix arc AVL tree balanced tree bandwidth B-tree bijective binary heap binding binding list Boolean matrix bucket cache Cartesian product clustering collision comparison critical path cycle DAG dense graph Dijkstra's algorithm directed directed acyclic graph discrete event simulation domain edge exclusive or external sort fold geometric series gradient ascent graph greedy algorithm hash function hashing with buckets heuristic in-place injective internal sort iterator latency load factor map mapping master max queue memory hierarchy memory locality min queue minimum spanning tree on-line one-to-one onto parsing path pattern pattern variable pivot priority queue randomized algorithm range Red-Black tree reduce rehash row-major order scalability separate chaining shortest path simple path slack slave sparse array sparse graph spatial locality Splay tree stable surjective symbol table temporal locality topological sort tree rotation undirected unparsing vertex weight XOR