Additional topics to study for the final examination in CS 302.
This page was last updated: Thu Dec  6 11:05:50 PST 2012

What are, greedy algorithms, divide and conquer algorithms,
and dynamic programming?

What is an ADT?  Array, search stucture, and prioity queue are examples.
But so are simple types, such as integer and Boolean.

What is relaxation?

What are the various versions of the minimum path problem?
What are some of the algorithms used to solve them?

What is a hash table?  What is a hash function?  What are its properties?
What is probing?  What is a perfect hash table?  What is cuckoo hashing?

Sorting.

Lazy deletion.

Graph, directed graph, weighted graph, acyclic graph, connected graph,
strongly connected directed graph, topological order, in-neighbor list,
out-neighbor list, matrix representations, component, minimum spanning tree,
planar graph, weighted directed graph, directed acyclic graph, breadth-first
search, depth-first search.

Sparse graphs, sparse arrays.

Preorder visitation, inorder visitation, postorder visitation, level order
visitation.

Input condition, output condition, correctness, loop invariant,
time complexity, space complexity, asymptotic time complexity,
asymptotic space complexity, worst case analysis.

Sparse graphs, sparse arrays.