COS 226 Final: COS 226 Princeton Final Fall 11 Solution
31 Jan 2019
School
Department
Course
Professor
Document Summary
Final solutions: analysis of algorithms. (a) t (n ) = 1. When n increases by a factor of 8, the memory usage increases by a factor of 32. T (n ) = an b, where b = log8 32 = lg 32/ lg 8 = 5/3. 10000 = a 10005/3, which implies a = 1. Remark: this is essentially the same question from the midterm. The starting vertex must be either a or f (but it doesn"t matter which). 1: shortest paths. (a) 3 0 10 5 2. It is not necessary to run the algorithm from the beginning to deduce this because dijk- stra"s algorithm considers the vertices in increasing order of distance from the source. (b) the next vertex to relax is 4. v. 3 10: string sorting. count[] count[] count[] c. 19 a[i] blurb climb crumb basic cubic freed dwarf cliff. Transition. (iii) there are two missing match transitions: 2 3 and 4 5.
