CSE 373 Final Exam Topics (Winter 2010)
- Sets, binary relations, cartesian products,
properties of binary relations, functions, properties of functions.
- Logarithms and exponents, the number of
bits required to distinguish one element of a set.
- Arithmetic and geometric series.
- Growth rates, big O, big Omega, big Theta.
- Asymptotic analysis of running times.
- Analysis of Mergesort running time.
- Proof by induction.
- Stacks and queues.
- Binary trees; complete, full, and perfect binary trees; depth, height.
- Binary search trees, traversals, lookup (find), insertion and deletion.
- AVL trees, single and double rotations, insert, delete.
- B-trees (comparing access times for RAM and magnetic disks; B-tree definitions according to Weiss; insertion, deletion).
- Hashing, including hash functions, surjections,
separate chaining, probing, lazy deletion,
load factors, Dictionary ADT.
- Priority queues and binary heaps, including complete binary
trees, INSERT, DELETEMIN, BUILDHEAP, and the worst-case running
times of these operations.
- Sorting, including simple Insertion Sort, simple Selection Sort, BubbleSort,
Heapsort, Merge Sort, and Quicksort, stability of a sorting method, in-place sorting, Bucket Sort, Radix Sort, the n log n lower bound on the number of comparisons for sorting n keys.
- Disjoint sets, UNION and FIND operations, uptree implementation, path compression; application to maze construction, and to minimum spanning tree construction (Kruskal's algorithm). Application to image connected components.
- Graph definitions, undirected graphs, directed graphs, directed acyclic graphs, topological sorting; representation of graphs using adjacency lists, adjacency matrix.
- Dijkstra's algorithm for the Single Source Shortest Paths problem. (updated -- was listed earlier as All Pairs)
- Minimum spanning trees; Prim's and Kruskal's algorithms.
- Dynamic programming. Application to Fibonacci number computation. Application to the all-pairs shortest path problem
(Floyd-Warshall Algorithm). Application to finding Longest Common Subsequences.
- Simple ADT for an image in which the image itself is defined as a function, and the two methods PUTPIXEL and GETPIXEL are defined; the domain and range of a function corresponding to an image.