COS 226 Midterm: COS 226 Princeton Midterm Fall 08 Solution

• School: Princeton University
• Department: Computer Science
• Course: COS 226
• Professor: All

Document Summary

0 6 5 2 4 9 3 8 7 1: sorting equal keys. Insertion a0 a1 a2 a3 a4 a5 a6. Selection a0 a1 a2 a3 a4 a5 a6. Shellsort a0 a1 a2 a3 a4 a5 a6. Mergesort a0 a1 a2 a3 a4 a5 a6. Quicksort a4 a3 a5 a6 a0 a2 a1. Heapsort a1 a2 a3 a4 a5 a6 a0: analysis of algorithms. (a) i and ii only. Big-oh notation and tilde notation both suppress lower order terms. (b) i only. Amortized analysis provides a worst-case guarantee on any sequence of operations start- ing from an empty data structure. Compute the intersection point p between line i and line j. If the key p is not already in the symbol table, add an entry to the symbol table with key = p and value = empty list. Implement the symbol table using a separate-chaining (or linear-probing) hash table so that each insert/search takes o(1) time.