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

Final Exam, Tuesday December 13, 2011.

• 2:30 - 4:20pm in 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
• Dictionary ADT
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• AVL trees - Single and double rotations, insert, find. (No delete)
• Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• D-heaps - Findmin, Deletemin, Insert.
• Disjoint Union/Find - Dynamic equivalence relations, Up-tree representation, union, find, weighted union (union by size) and path compression.
• 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.
• The memory hierarchy -  Temporal and spatial locality.  Data structure choice and the memory hierarchy.
• Graphs - definitions, adjacency list and adjacency matrix representations [Graphs I lecture, Weiss 9.1]
• Graphs - topological sort [Graphs II lecture (up through slide 25, material on graph traversals is not included) , Weiss 9.2]

After Midterm 2:

• Graphs:

• Graph traversals: 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.
• Bucket sort, Radix sort.
• Parallelism: There will only be extra credit questions on parallelism

NOTES

· Topics covered on these exams may not be the exact same topics covered on our exam; please see the list of topics listed above for topics covered on our exam.

· These are provided to help you study and are not meant to be interpreted as a guarantee of the format of our actual exam in terms of length or type of questions.

Sample final exam questions:

• Sample Final Exam Questions (calculators will NOT be allowed on our exam, “null path length” and Splay trees will not be on our exam)
• Solution to Sample Final Exam Questions

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)
• Midterm I from 10sp (Solution to Midterm I from 10sp)
• Midterm I from 10au (Solution to Midterm I from 10au)
• Midterm I from 11au (Solution to Midterm I from 11au)
  
  
• Sample Midterm II (Key to Sample Midterm II) (Questions on Memory and B-trees)
• Midterm II from 08sp (Key to Midterm II from 08sp) (Questions on Memory and B-trees)
• Midterm II from 09wi (Key to Midterm II from 09wi) (Questions on Memory)
• Midterm II from 09sp (Solution to Midterm II from 09sp)
• Midterm II from 10sp (Key to Midterm II from 10sp)
• Midterm II from 10au (Key to Midterm II from 10au)
• Midterm II from 11au (Key to Midterm II from 11au)

Study suggestions:

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

---