CS 106B Midterm: CS 106B Midterm 1 4 Spring 2013 Solutions
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) This problem can be solved either by following through the computation or by figuring out what each function does. In this case, it is easier to undertake the latter approach. The enigma function computes the product of n1 and n2 by recursively summing n1 copies of n2. The mystery function then uses enigma to multiply n copies of the integer: the value of mystery(n) is therefore 2n, which means that mystery(3) returns 8. Computing the complexity order requires noticing that the computation of mystery(n) makes n calls to enigma. Given the coding of mystery, each call to enigma requires a constant amount of work because the first argument is always 2.