Final Exam Study Guide
CSE 373: Data Structures
Spring 2007

Final Exam, Wednesday June 6, 2007.

• 2:30 - 4:20pm in WFS 201 (Our regular lecture room)

• Exam policies
• Closed book, closed notes. Calculators allowed (not sure they will be useful for anything but you may use one if desired)
• The exam begins promptly at 2:30pm and ends at 4:20pm.

 

Topics covered on the Final Exam:

 

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

 

            From Midterm 1:

• Stacks and Queues, array and list implementations.
• Recursion.  Designing algorithms recursively.
• Asymptotic analysis, Big-O.  Worst case, upper bound, lower bound, analyzing loops, recurrences, amortized complexity.
• Trees – definitions
• Dictionary ADT
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• AVL trees - Single and double rotations, insert, find.
• Splay trees – insert, find, splay operations
• Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.

 

            From Midterm 2:

• D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• Leftist Heaps and Skew Heaps - Findmin, Deletemin, Insert.  Additional operations of merge, increase, decrease
• Binomial Queues - Findmin, Deletemin, Insert.  Additional operations of merge, increase, decrease.
• Disjoint Union/Find.  Up-trees.  Weighted union (union by size) and path compression.
• The memory hierarchy.  Temporal and spatial locality.  Data structure choice and the memory hierarchy.
• 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.
• B-trees.  Motivation, choice of M and L, Insert (no delete).

 

            After Midterm 2:

• 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: (Know the definition, do not have to know Prim’s and Kruskal’s algorithms.)
• Sorting. Insertion sort, Selection sort, Heap sort, Merge sort, Quicksort.
• Bucket sort, Radix sort.  Lower bound on comparison sorting.  In-place sorting.  Stable sorting.

 

• Study suggestions:

 

• Do concrete problems from the book and re-work problems from lecture, and HW.

 

All material from lecture up through sorting is fair game.