Final Exam Study Guide
CSE 373: Data Structures & Algorithms
Autumn 2009

Midterm 3 (a.k.a. Final Exam), Friday December 11, 2009.

• 12:30 - 1:30pm in GLD 322 (Our regular lecture room)

• Exam policies
• Closed book, closed notes. Calculators NOT allowed.
• The exam begins promptly at 12:30pm and ends at 1:30pm.

Topics covered on the Midterm 3:

The Midterm 3 is cumulative, although a bit 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
• Dictionary ADT
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• AVL trees - Single and double rotations, insert, find.
• B-trees.  Motivation, structure, choice of M and L, insert/delete.
• Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• 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, Extendible Hashing
• Sorting: Bubble Sort, Insertion sort, Selection sort, Heap sort, Merge sort, Quicksort. Lower bound on comparison sorting. Bucket sort, Radix sort. 

After Midterm 2

• Disjoint Union/Find: Dynamic equivalence relations, Up-tree representation, union, find, weighted union (union by size) and path compression.
• Graphs. Directed and undirected. Adjacency list and adjacency matrix representations.

• 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.

• Netwrk Flow: Definition, Residual Graph, Ford-Fulkerson Method, Minimum Cuts.

Sample Midterm 3:

• Sample Midterm 3 (calculators will NOT be allowed on our exam, Splay trees and Memory Hierachy will not be on our exam)
• Solution to Sample Midterm 3

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

• Sample Midterm I (Solution to Sample Midterm I) (Extra steps written out for Sample Midterm I)
• Midterm I from 08sp (Solution to Midterm I from 08sp)
• Midterm I from 09wi (Solution to Midterm I from 09wi)
• Midterm I from 09sp (Solution to Midterm I from 09sp)
• Sample Midterm II (Key to Sample Midterm II)
• Midterm II from 08sp (Key to Midterm II from 08sp)
• Midterm II from 09wi (Key to Midterm II from 09wi)
• Midterm II from 09sp (Solution to Midterm II from 09sp)

Study suggestions:

• Do concrete problems from the book and re-work problems from lecture, and HW.
• All material from lecture up through Network Flow is fair game.

---