|
|
|
|
|
Final Study Guide
Final Exam, Friday, August 18, 2006
- Exam policies
- Closed book, closed
notes. No cheating.
- The exam begins
promptly at 9:40 and ends at 10:40.
- Topics covered
- 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.
- 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.
- Binary search trees
– Inorder, preorder, postorder traversals, insert, delete, find.
- Minimum spanning tree: Prims and Kruskals algorithms.
- NP completeness. Euler and Hamiltonian circuits. Reductions.
- In general: Algorithmic analysis (best case, worst case, average case, amortized). Order notation (Big Oh, big Omega). Recursion.
- Study suggestions
- Do concrete problems
from the book and re-work problems from lecture, section, and homeworks.
Suggestions of more problems from the book:
Chapter 2: 2.6, 2.10. Chapter 3: 3.21, 3.22, 3.23 (a). Chapter 4: 4.1,
4.8, 4.22, 4.27, 4.28. Chapter 6: 6.2, 6.3, 6.30.
- Selected solutions to practice problems. Please note that some
of the figures end up on the last page.
- More problems: Chapter 5: 5.1, 5.8, 5.9, 5.10, 5.11. Chapter 7: 7.1, 7.15, 7.19, 7.39.
Chapter 9: 9.20, 9.34, 9.53. Ruth Anderson's homework 3.
- Practice all the
sorting and hashing algorithms. Practice topological sort, graph search,
and shortest path. Practice analysis of algorithms.
- All material from
lecture up through NP Completeness is fair game. This material corresponds to: Chapters:
1, 2, 3, 4, 5, 6 (not including 6.6 and 6.7), 7, 8 (not including 8.6), and 9 (not including 9.4).
|
CSE Home 
