15-112Spring 2013 Quiz 4

* 15 Minutes.  No calculators, no notes, no books, no computers.

1.       [10 pts] Below each algorithm (as we discussed in class), write its Big-Oh runtime:
a) selectionsort       b) mergesort       c) linear search       d) binary search       e) isPrime       f) fasterIsPrime     
    O(              )              O(              )            O(              )               O(              )             O(              )         O(              )
 

2.       [10 pts] Say the list (3, 8, 1, 4, 2, 6, 9, 7) is being sorted with mergesort.  Write the partially-sorted list just before the start of the final pass (just before the last merge).
 

3.       [10 pts] Sort the list (3, 8, 1, 4) using selectionsort, as implemented in xSortLab, by writing the list after each swap occurs.
 

4.       [20 pts] The following table gives the runtimes of calling foo(x) and foo(4*x) for a reasonably large value of x.  Fill in the third column, indicating the big-oh function family that most likely described foo(x)'s runtime, where all the answers will be among the major function families we have studied.

5.       [10 pts] List Polya’s 4 steps to problem solving:

 

6.       [10 pts] Before writing any code, you should consider a variety of algorithms, and then do some algorithmic analysis to determine which is most suitable.  Which step of Polya would this fall under?
 

7.       [10 pts] When adapting your manual solution so it is amenable to code, you are advised: “Do not require human memory”, and instead to “explicitly write down values you need to remember”.   When you finally do convert this to a program, what element(s) of the program will be defined by this specific technique?
     A)  The overall program logic
     B)  The variables
     C)  The operators
     D)  The helper functions
     E)   All of the above
     F)   None of the above

8.       [10 pts] For each problem-solving technique (from the required reading), write the letter of its corresponding definition.

1. Lateral Thinking                   A. solving the problem in a model of the system before applying it to the real system

2. Abstraction                            B. transforming the problem into another problem for which solutions exist

3. Root Cause Analysis          C. using a solution that solved an analogous problem

4. Divide and Conquer           D. approaching solutions indirectly and creatively

5. Reduction                              E. breaking down a large, complex problem into smaller, solvable problems

F. None of the above

 

9.       [10 pts] In just a few words, state one compelling reason why magic numbers are undesirable.  Be precise, so for example, “it’s bad style” would not receive any credit.  Why is it bad style?

 

10.   Bonus/Optional [5pts]:  Rewrite f(x) so it works the same (for non-negative int values x) and does not use loops, conditionals, or recursion.

def f(x):
    y = 5
    for x in xrange(x):
        y += 5*f(x)
    return y