1Final Exam Review: December 11, 2007The University of Michigan2Agendaz Important Topicsz Exam Formatz Last year’s exam reviewz Any Questions?:3Important Topicsz Cumulative w/focus on new material (after midterm)− Sorting algorithms: Selection, Insertion, Heap, Merge and Quicksort(*)− Hashing− Recurrence relations / Recursive Functions− Trees: AVL, BST, M-way, 2-[34] and B-tree− Graphs: (*)z Traversals (BFS & DFS)z Topological sortz MST (Kruskal’s and Prim’s)z SPF (Dijkstra’s)− P/NP problems− Convex hull / Graph coloring:Important Topics Continued:4−Dynamic Programming (*)− 0/1 Knapsack (*)− Travelling salesman− Longest Common Subsequence (*)− Edit Distance, Approximate Match and Pattern Matching (*)Formatz 5-8 questions with an average of 12-15 points eachz No surprises (like the midterm)z 110 minutesz Wednesday 12/19− 4:00-6:00 pm in CSE 1670 (A-M)− DOW 1005 (N-Z):5Conclusion:6Any Questions?Good Luck for the
View Full Document