CS 314: Study Guide for Final Exam

Date: THURSDAY, DECEMBER 14, 9-12 Noon, in CAL 100

Reading:

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 from the Midterm Study Guide is included on the exam.

Material covered in class:

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