Final Exam Study Guide
CSE 326: Data Structures
Spring 2007

Final Exam, Thursday June 7, 10:30 am, EE 037.

(Note: The exam is officially scheduled for 8:30 am; if you wish to take it at that time that can be arranged. Please contact Perkins if you want to do this.)

• 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 10:30am and ends at 12:20pm.

 

Topics covered on the Final Exam

           

            The exam will be weighted more towards topics covered since the midterm, but you are responsible for everything covered this quarter.

           

            Pre-Midterm:

• Linked lists. Simple linked lists, doubly linked lists, circularly linked lists.
• Stacks and Queues, array and list implementations.
• Recursion. Designing algorithms recursively.
• Asymptotic analysis, Big-O, Theta, Omega. Worst case, upper bound, lower bound, analyzing loops, recurrences, amortized complexity.
• Trees – definitions
• Priority queues – definitions and operations.
• Binary Heaps, 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.
• Dictionary ADT
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• AVL trees - Single and double rotations, insert, find.

           

            Post Midterm:

• Splay trees - Splaying, insert, find.
• B-trees. Motivation (large data on slow secondary storage), choice of M and L, insert (no delete).
• 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.
• Disjoint Union/Find. Up-trees. Weighted union (union by size) and path compression.
• Sorting. Insertion sort, Selection sort, Heap sort, Merge sort, quicksort.
• Bucket sort, Radix sort. Lower bound on comparison sorting. In-place sorting. Stable sorting.
• Graphs. Directed and undirected. Adjacency list and adjacency matrix representations.
• Topological sorting.
• Graph searching. Depth-first, breadth-first search, best-first search.
• Shortest paths. Dijkstra's algorithm. Greedy Algorithms.
• Minimum spanning tree: Prim’s and Kruskal’s algorithms.
• Floyd-Warshall algorithm; notion of dynamic programming.