CSE 373: Data Structures & Algorithms

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

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

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

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

**Sample final exam:**

- Sample Final Exam (calculators will
__NOT__be allowed on our exam, Splay trees will not be on our exam) - Solution to Sample Final Exam

**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)

- 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)

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