CS 106B Study Guide - Midterm Guide: Cemex
9 Jan 2019
School
Department
Course
Professor
Document Summary
Review session: sunday, february 3, 7:00 9:00 p. m. , hewlett 201 (next door) Problem 1: tracing c++ programs and big-o (10 points) Tuesday, february 5, 3:15 5:15 p. m. , braun auditorium (chemistry) Tuesday, february 5, 7:00 9:00 p. m. , cemex auditorium (gsb) If you think about what"s happening in the puzzle function, it should be clear that the function computes the number of moves required to solve the tower of hanoi problem. To understand the complexity order of the computation, it helps to draw a tree of the computations involved, which (after abbreviating puzzle to p to save space) looks like this for puzzle(4): Each new level doubles the amount of work, so the total amount of work must be o(2n). Another way to obtain this same result is that the calculation of puzzle(n ) requires twice as many additions as the original tower of hanoi puzzle requires moves to solve the problem for n disks.
