• Unlike hw4a, this portion of the hw is COLLABORATIVE.  You may work in groups of up to 3 other students who are in this course this semester (and nobody else except current CA's), so long as you do not simply copy their work but truly work together.  In fact, you are encouraged (though not required) to work in groups, provided you all contribute and nobody simply copies someone else's work.
   
• If you work collaboratively, you still must submit your own solutions.
   
• This part is worth 40 pts.  Hw4a (which is SOLO) is worth 60 pts.
   
• Submit a physical copy (handwritten, not typed).  Show your supporting calculations as appropriate.  Write neatly.  Staple multiple pages.  Include your name, andrew id, and section clearly at the top of the first page, and the names and andrew id's of your collaborators.
   
• Since this requires a physical submission, if you cannot attend office hours on Sunday night, you may drop off your submission at my office (GHC 5001) on Monday morning up until 9am (but no later!), and your submission will count as on time.

1. [3 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. [3 pts] Binary search requires at most how many guesses to guess a number between 1 and 1 thousand?   Between 1 and 1 billion?  Between 1 and 1 trillion?
    

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

4. [3 pts] Sort the list (2, 5, 4, 1, 3) using selectionsort (the way it works in xSortLab), by writing the list after each swap occurs.
    

5. [3 pts] Say x=20 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. [3 pts] Watch these videos on selectionsort and mergesort (you do not need to watch the whole thing, just long enough to be sure you understand how each sort works).  Also, work with xSortLab for both selectionsort and mergesort to further confirm that you all understand how each sort works.  What to submit?  Just a confirmation that you did this step (this should take 10 minutes or so).
    

7. [3 pts] Re-derive the worst-case big-oh runtime for both selectionsort and mergesort.  Submit short "proofs" (in plaintext) of each of these.  Be sure you understand the math.
    

8. [3 pts] Using the timing feature of xSortLab, run the other sorts (besides selectionsort and mergesort) that it includes.  Try different size lists for each sort (include your data in your submission!), and use just this timing information to predict the big-oh function family of each of those sorts.
    

9. [6 pts; 2 pts each] For each of these functions, circle the closest family it belongs to (big O notation).

   A. T = 2N + 5

       O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)

   B. T = N + logN

       O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)

   C. T = N**3 + 45N**2 + 100logN

       O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)

   D. T = 10N * 3N

       O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)

   E. T = 10N + 3N

       O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)

   F. T = number of steps merge sort takes to sort a list of N numbers

       O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)
    

10. [10 pts; 2 pts each] What is the (worst-case) big-oh runtime of each of the following functions (assume n>0, x>0, and ignore cases when they might crash):
    Hint: you are not being asked anything about what the function returns, which is irrelevant to this problem....

    def f0(n):
        count = 0
        for x in xrange(n):
            for y in xrange(1, n):
                count += 1
        return count
    
    def f1(n):
        count = 0
        for x in xrange(n):
            for y in xrange(1, x):  # note ranges to x, not n
                count += 1
        return count
    
    def f2(n):
        count = 0
        for x in xrange(1,n/2, 2):
            for y in xrange(1, x/2):
                count += 1
        return count
    
    def f3(n):
        count = 0
        for x in xrange(1,n):
            for y in xrange(1, n, n/100):
                count += 1
        return count
    
    def f4(n):
        count = n**2 # note: not setting count = 0
        while (n > 0):
            count += 1
            n /= 2
        return count
    
    def f5(n):
        count = 0
        for x in xrange(1, n):
            count += f4(n)
        return count

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