CSE326: Data Structures

Final Review List

1.

General: Be able to write, trace, or perform a complexity analysis of:

(a)

recursive functions

(b)

functions that work with any kind of linked list (singly linked, doubly linked, circular, or whatever a problem defines)

(c)

functions that work with binary trees, general trees implemented via binary trees, binary search trees (with or without splaying), B+trees (NOT AVL trees)

(d)

functions that implement hashing

(e)

functions that work with binary heaps

(f)

functions that implement heapsort, mergesort, or quicksort

(g)

functions that implement disjoint sets with the union-find structure

(h)

functions that work with graphs, including topological sort, unweighted shortest path, weighted shortest path with nonnegative weights, all-pairs path existance, minimal spanning trees, depth-first and breadth-first search, and graph matching.

2.

Complexity Analysis: Be able to determine time complexity in Big Oh notation, in terms of the smallest common function f such that T(N) = O(f(N))

(a)

using counting arguments

(b)

using results of other analyses if applicable

Be able to answer questions about the meaning of O(N).

3.

Trees: Be able to construct and search (by hand)

(a)

binary search trees

(b)

splay trees

(c)

B+trees

Be able to delete from binary search trees.

4.

Hashing: Be able to construct hash tables in several different ways.

(a)

hash to buckets that point to either linked lists or contiguous lists

(b)

direct organization (book says ``open addressing'') with linear or quadratic probing or with double hashing (book's terminology for a second hash function)

Know what to do when the hash table becomes too full. Be able to discuss complexity.

5.

Heaps: Be able to construct, add to, or delete Min from a binary heap (or delete Max from a max heap).

6.

Sorting: Be able to show how sorting is done by heapsort, mergesort, and quicksort (with different pivoting strategies). Be able to discuss the merits and shortcomings of each method. Be able to explain or to mimic the methods shown in the book for setting up and solving recurrence relations. :

7.

Disjoint Sets Be able to work with the representation for disjoint sets that stores a tree for each equivalence class. Be able to apply the union and find algorithms to use in applications.

8.

Graphs Be able to perform graph matching or calculate the error of a mapping for the different variations in the class handout, ie. full isomorphisms, subgraph isomorphisms, relational distance matching for labeled or unlabeled graphs, digraphs or undirected graphs. Be able to show how the various algorithms find topologically-consistent orderings of the nodes of a DAG, shortest unweighted or weighted path for directed graphs that may have cycles, and all pairs of paths that exist for directed graphs represented as adjacency matrices. Be able to answer questions on how these algorithms are the same and how and why they differ. Be able to use Kruskal's algorithm to find a minimal spanning tree of a weighted graph. Be able to perform depth-first or breadth-first searches and to use them to solve some problem.