15-112Fall 2011 Quiz 3

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

1.       [60 pts] On the back of this sheet, write the function nthWithOnlyOddDigits, which takes a non-negative integer n and returns the nth number that only has odd digits (these numbers being 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, 33, ….).  Start counting at 0, so nthWithOnlyOddDigits(0) returns 1.  You may write helper functions.
 

2.       [12 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(              )
 

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

4.       [10 pts] Sort the list (2, 4, 5, 1, 3) using selectionsort, by writing the list after each swap occurs.
 

5.       [10 pts] Say x=10 million, and you call foo(x) and it takes 3 seconds.  Then you call foo(2*x) and it takes 8 seconds.  And then you call foo(4*x) and it takes 21.5 seconds.  What would you guess the big-oh runtime of foo(n) is (assuming it is one of the major function families we have seen)?  Very briefly, why?
 

6.       Bonus/Optional [5pts]:  Describe in a few words of plain English what f(x) does.  For full credit, prove your answer.
Hint: perhaps induction may be useful.

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