COS 226 Final: COS 226 Princeton Final Fall 11
31 Jan 2019
School
Department
Course
Professor
Document Summary
This test has 14 questions worth a total of 100 points. The exam is closed book, except that you are allowed to use a one page cheatsheet (8. 5-by-11, both sides, in your own handwriting). No calculators or other electronic devices are permitted. Give your answers and show your work in the space provided. Write out and sign the honor code pledge before turning in the test. I pledge my honor that i have not violated the honor code during this examination. Estimate the memory usage of the program (in bytes) as a function of n and use tilde notation to simplify your answer. Hint: recall that logb a = lg a/ lg b. 3 (b) for each function on the left, give the best matching order of growth of the running time on the right. Assume the adjacency lists are in sorted order: for example, when iterating through the edges pointing from 0, consider the edge 0 1 before.
