|
|
|
|
|
Final Exam Study Guide
Final Exam: 2:30-4:20pm, Tuesday, March 16, 2010
- Exam policies
- The exam will be held in our regular lecture room (EEB 125)
- Closed book, closed notes.
- The exam begins promptly at 2:30 and ends at 4:20.
- Topics
- All material from lecture is fair game, although
you can assume that material you have not been tested on
yet (post-midterm material) will be emphasized a bit more.
- This material corresponds to: Chapters: 1-9, and 10.3.4
- Here is a (fairly complete, but not exhaustive) summary of topics we've covered in lecture that are fair game for the exam:
Pre-Midterm:
- 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 (just
the idea), 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.
- Skew Heaps - Findmin, Deletemin, Insert.
Additional operations of merge, increaseKey,
decreaseKey
- Leftist 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, (no delete), build.
Post Midterm:
- Splay trees - Splaying: zig, zig-zig, and zig-zag
rotations, insert, find, (no delete).
- The memory hierarchy. Temporal and spatial
locality. Data structure choice and the memory
hierarchy.
- B trees - motivation, choice of M and L, basic
operations of find, insert, 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.
- Sorting. Insertion sort, Selection 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 (just the ideas on these -
don't have to be able to execute). Depth-first, breadth-first,
best-first.
- Shortest paths: Dijkstra's algorithm for
SSSP, Floyd-Warshall for APSP
- Minimum spanning tree: Prim's and Kruskal's algorithms
- Huffman Coding will only appear as an extra credit question.
- The focus will be on ideas/concepts about data
structures and algorithms, not Java. Although
you could be asked to write short bits of Java or pseudo
code.
- Study suggestions
- Do concrete problems from the book and re-work problems from
lecture and homework.
- 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.
- Review the practice midterms.
- Practice finals (which cover some topics that we did not):
|
CSE Home 
