15-112 Fall 2012 Quiz 4a (Autograded) [see Quiz4b below]
45 minutes


Read these instructions first!
  1. nthCarolPrime [25 pts]
  2. inverseF [25 pts]

  1. nthCarolPrime [25 pts]
    Write the function nthCarolPrime(n), which takes a non-negative int and returns the nth Carol Prime, which is a prime number of the form
         ((2k - 1)2 -2)
    for some value positive int k.  For example, if k equals 3, ((23 - 1)2 -2) equals 47, which is prime, and so 47 is a Carol Prime.  The first several Carol primes are:
        7, 47, 223, 3967, 16127, 1046527, 16769023,...
    Note:  You must use an efficient approach that quickly works up to n==9, which will return a 12-digit answer!
     
  2. inverseF [25 pts]
    Consider the function f(x) = 3x - 2x.  Write the function inverseF(y), that takes a positive floating-point value y, and finds and returns the value x such that f(x) == y.  As this is approximate, your answer needs to be within 0.001 of the actual answer.  For example, f(2) = 32 - 22 = 9 - 4 = 5.  Thus, since f(2)==5, inverseF(5)==2.  How to do this?  Using bisection, though you may have to slightly adapt it.

    Hint:  in the homework, we used bisection to find zeros.  We can adjust this problem easily to search for a zero.  How?  Well, say:
         y = 3x - 2x
    Then we also have:
         3x - 2x - y = 0
    Hopefully that's enough to get you started.  Good luck!


15-112 Fall 2012 Quiz 4b (non-autograded)

* 15 Minutes.  No calculators, no notes, no books, no computers.
* 50 pts.  (The other 50 points are on the autograded hw4a)

1.       [5 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.       [5 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.       [5 pts] Sort the list (3, 8, 1, 4) using selectionsort, as implemented in xSortLab, by writing the list after each swap occurs.
 

4.       [10 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.

Time for foo(x)

Time for foo(4*x)

Big-Oh function family

3s

6s

 

2s

32s

 

8s

32s

 

4s

19s

 

3s

3.5s

 

 

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

6.       [5 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.       [5 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.       [5 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.       [5 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 = 1
    for x in xrange(x):
        y += 24*f(x)
    return y
 


carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem