Final score distribution
Final Study Guide
Final Exam
8:30am - 10:20am
Thursday, June 11, 2009
EEB 125
- Exam policies
- Closed book, closed notes.
- Topics
- All material from lecture is fair game.
- This material corresponds to: Chapters: 1-9.
- Here is a (fairly complete, but not exhaustive) summary of topics we've covered in lecture:
- Linked lists. Simple linked lists, doubly linked lists,
circularly linked lists.
- Stacks and Queues, array and list implementations.
- Recursion. Designing algorithms recursively. Inductive proof.
- Asymptotic analysis, Big-O. Worst, amortized, average, best
cases. Upper and lower asymptotic bounds. Analyzing loops,
recurrences.
- Trees - definitions
- Binary Heaps, D-heaps - Findmin, Deletemin, Insert. Additional
operations of increaseKey, decreaseKey, buildHeap.
- Leftist Heaps and Skew Heaps - Findmin, Deletemin, Insert.
Additional operations of merge, increaseKey, decreaseKey
- Binomial Queues - Findmin, Deletemin, Insert. Additional
operations of merge, increaseKey, decreaseKey.
- Dictionary ADT
- Binary search trees - Inorder, preorder, postorder traversals,
insert, delete, find, build.
- AVL trees - Single and double rotations, insert, find, delete,
build.
- Splay trees - Splaying: zig, zig-zig, and zig-zag rotations, insert, find, delete,
build.
- B+ trees - motivation, basic operations.
- 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.
- Sorting. Insertion sort, Bubble sort, Selection sort, Shell
sort, Binary tree sort, Heap sort, Merge sort, quicksort. In-place
sorting. Stable sorting.
- Bucket sort, Radix sort.
- Lower bound on comparison sorting.
- Disjoint Union/Find - Up-trees. Weighted union (union by size)
and path compression.
- Graphs. Directed and undirected. Adjacency list and adjacency
matrix representations. Edge and vertex complexities.
- Topological sorting.
- Graph searching. Depth-first, breadth-first search
- Shortest paths. Dijkstra's algorithm for SSSP.
- Minimum spanning tree: Prim's and Kruskal's algorithms
- The focus will be on ideas/concepts about data structures and
algorithms, not Java.
- Study suggestions
- Do concrete problems from the book and re-work problems from
lecture, section, and HW.
- Practice all the operations on the data structures.
- Practice analysis of algorithms. Learn and be able to reason about
the complexities of operations on the data structures we've discussed in
class.
- Try practice finals.
- Practice finals (which cover some topics that we did not):