## Final Exam Study Guide CSE 373: Data Structures & Algorithms Spring 2010

#### Final Exam, Tuesday December 14, 2010.

• 2:30 - 4:20pm in SAV 264 (Our regular lecture room)
• Exam policies
• Closed book, closed notes.  Calculators NOT allowed.
• The exam begins promptly at 2:30pm and ends at 4:20pm.

#### Topics covered on the Final Exam:

The Final exam is cumulative, although more weight will be given to topics covered since the second midterm.

From Midterm 1 & 2:

• Stacks and Queues, array and list implementations.
• Recursion.  Designing algorithms recursively.
• Asymptotic analysis, Big-O.  Worst case, upper bound, lower bound, analyzing loops, recurrences.
• Trees – definitions
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• Hashing.  Properties of good hash functions.  Selecting hash table size.  Separate chaining and open addressing.  Linear Probing, Quadratic Probing, & Double Hashing to resolve collisions.  Rehashing.
• AVL trees - Single and double rotations, insert, find, (NOT delete).
• Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• Leftist Heaps and Skew Heaps - Findmin, Deletemin, Insert.  Additional operations of merge.
• Disjoint Union/Find - Dynamic equivalence relations, Up-tree representation, union, find, weighted union (union by size) and path compression.
• The memory hierarchy.  Temporal and spatial locality.  Data structure choice and the memory hierarchy.

After Midterm 2:

• Topological sorting. Graph searching: Depth-first, breadth-first search.
• Shortest paths. Dijkstra's algorithm. Greedy Algorithms.
• Minimum spanning tree, Prim’s and Kruskal’s algorithms.

• B-trees.  Motivation, structure, choice of M and L, Insert, Delete.
• Sorting:
• Insertion sort, Selection sort, Heap sort, Merge sort, Quicksort. Lower bound on comparison sorting.
• In-place sorting.  Stable sorting.

Sample final exam:

Links to previous exams (copied from the Midterm 1 and Midterm 2 pages):

Study suggestions:

• Do concrete problems from the book and re-work problems from lecture, old midterms, and HW.
• All material from lecture up to and including sorting is fair game.