COS 226 Midterm: COS 226 Princeton Midterm Fall 09 Solution
31 Jan 2019
School
Department
Course
Professor
Document Summary
0 3 5 2 6 4 8 7 9 1: analysis of algorithms. (a) i and ii only. Iii is a true statement, but tilde notation also suppresses lower order terms so it is not a reason why tilde notation is more precise. (b) 10 9n 3 seconds: binary heaps. (a) k m r (b) S (b) 2 left rotation (one while inserting z, one while inserting p), 1 right rotations (while inserting p), 2 color ips (while inserting p). I only: i results from inserting the keys in the order b d f a c e g, ii cannot result. The rst key inserted will end up in the table entry corresponding to its hash value. But no key has this property: iii cannot result. Both a and f end up in the table entry corresponding to their hash values, so we can assume they were inserted rst and second.
