CSE 373 Midterm Exam 2 Topics (Winter 2010)
- Priority queues and binary heaps, including complete binary
trees, INSERT, DELETEMIN, BUILDHEAP, and the worst-case running
times of these operations. Implementation using arrays.
- Graphs. Directed and undirected graphs, with and without edge costs.
Representations of graphs with
(a) vertex lists and edge lists, (b) adjacency lists, (c) adjacency matrices.
Graph terminology: adjacency, self loops, paths, path length, path cost, cycle,
simple cycle, DAG (directed acyclic graph), trees in relation to DAGs,
connectivity (strong, weak, ordinary), completeness.
- Graph algorithms. Depth-first and breadth-first search in graphs.
Shortest path problems: single source/single destination, single source/all destinations,
all pairs. Dijkstra's algorithm for the single-source/all destinations problem.
Topological ordering and topological sorting.
- Spanning trees. minimum spanning trees. Prim's algorithm. Kruskal's algorithm.
- Hashing, including hash functions, hash functions for string keys,
separate chaining, probing (both linear and quadratic), primary clustering in hashing, rehashing, deletion,
load factors, Dictionary ADT.
- Equivalence relations: reflexive, symmetric, and transitive properties of
binary relations. Partition of a set.
- Disjoint Sets ADT. Meaning of UNION and FIND operations. Up-trees and their
use in implementing the disjoint sets ADT. Implementation using
the weighted-UNION method. Path compression during FIND operations.
Application in maze construction. Application in Kruskal's algorithm.
Application in determining the connected components of an image.
- Sorting. Comparable objects: trichotomy. Stability.
Bubble sort and its running time, simple Insertion Sort, simple Selection Sort.
Sorting with an AVL tree. Heapsort.
Here are a
practice midterm, and
solutions.