COS 226 Midterm: COS 226 Princeton Midterm Fall 10 Solution
31 Jan 2019
School
Department
Course
Professor
Document Summary
1: analysis of algorithms. (a) for each expression in the left column, give the best matching description from the right column. 1 + 2 + 4 + 8 + . 1 + 3 + 5 + 7 + . N 2 + 100n lg n: n 2, n 3. The order of growth of the running time is n 2 log n from the search. Thus, if the problem size increases by a factor of 10, the running time will increase by a bit more than a factor of 102. 2 (d) 40 bytes (using 32-bit cost model from intro to programming). (8 bytes of object overhead, 4 bytes for the int, and 4 bytes for each of the 7 references) 0 5 7 6 4 3 9 2 8 1: binary heaps. (a) (b) (c) K: red-black bsts. (a) h, i, j, and k (b) red (c)
