15-112 Fall 2014 Homework 6
Due Sunday, 5-Oct, at 10pm

Read these instructions first!
  1. Study sorting code and big-oh proofs [0 pts] [not graded]
    This problem is not to be submitted and is worth 0 pts on hw6, but it is essential that you do it, and do it well. The task is to thoroughly study the sorting algorithms we studied this week -- selectionSort, bubbleSort, and mergeSort. In particular, you need to be able to:
    • understand and explain every step in the xSortLab visual simulations of each of these sorts.
    • write these sorts from scratch, quickly and easily.
    • prove the worst-case and best-case big-oh time complexity of each of these sorts.
    • write timing code to measure the runtime of each of these sorts.
    • use the runtime information to empirically confirm the big-oh time complexity of each of these sorts.
    It is all but guaranteed that some of these tasks will appear in some form in upcoming quizzes, midterms, and the final exam. So: practice, practice, practice!

  2. instrumentedSelectionSort(a)
    and
    instrumentedBubbleSort(a) [5 pts] [autograded]

    Write the functions instrumentedSelectionSort(a) and instrumentedBubbleSort(a). Each of these should work just like the versions in the course notes (the ones you just studied thoroughly in the previous question!), except instead of returning None, they return a triple of values: the number of comparisons, the number of swaps, and the time in seconds to run the sort.

  3. selectionSortVersusBubbleSort() [5 pts] [manually graded]
    Write the function selectionSortVersusBubbleSort(). This function takes no parameters, and calls the instrumented functions you just wrote above, perhaps several times each, and then uses the results to empirically confirm that both selectionSort and bubbleSort are quadratic (O(n**2)), and then also prints a short but clear report making clear which sort runs in less time, which sort uses fewer comparisons, and which sort makes fewer swaps. This function returns nothing -- all the information is printed to the console.

  4. mergeSortWithOneAuxList(a) [5 pts] [manually graded]
    Write the function mergeSortWithOneAuxList(a) that works just like mergeSort from the notes, only here you can only create a single aux list just one time, rather than once for each call to merge. To do this, you will need to create the aux list in the outer function (mergeSortWithOneAuxList) and then pass it as a parameter into the merge function. The rest is left to you. In a comment at the top of this function, include some timing measurements comparing this function to the original mergeSort, and a brief reflection on whether or not this change was worthwhile.

  5. largestSumOfPairs(a) [5 pts] [autograded]
    Write the function largestSumOfPairs(a) that takes a list of integers, and returns the largest sum of any two elements in that list, or None if the list is of size 1 or smaller. So, largestSumOfPairs([8,4,2,8]) returns the largest of (8+4), (8+2), (8+8), (4+2), (4+8), and (2+8), or 16.

    The naive solution is to try every possible pair of numbers in the list. This runs in O(n**2) time and is much too slow.

  6. hasBalancedParentheses(s) [5 pts] [autograded]
    Write the function hasBalancedParentheses(s) that takes a string s composed of only left and right parentheses, and returns True if these are legal and False otherwise. So:
       hasBalancedParentheses("())") == False # extra right paren
       hasBalancedParentheses("()(") == False # unclosed left paren
       hasBalancedParentheses(")(") == False # closing right paren occurs before opening left paren
       hasBalancedParentheses("(()())") == True

    A naive solution is to repeatedly remove each "()" pair until none remain, at which point the original string was balanced if only the empty string remains. This solution is very inefficient, as there is a way to compute the answer with one single loop over the characters in the string, and without ever creating any new strings.

  7. containsPythagoreanTriple(a) [5 pts] [autograded]
    Write the function containsPythagoreanTriple(a) that takes a list of positive integers and returns True if there are 3 values (a,b,c) anywhere in the list such that (a,b,c) form a Pythagorean Triple (where a**2 + b**2 == c**2). So [1,3,6,2,5,1,4] returns True because of (3,4,5).

    A naive solution would be to check every possible triple (a,b,c) in the list. That runs in O(n**3). You'll have to do better than that.

  8. nthCarolPrime(n) [10 pts] [autograded]
    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 ((2**k - 1)**2 - 2) for some value positive int k. For example, if k equals 3, ((2**3 - 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,...
    As such, nthCarolPrime(0) returns 7.

    Note: You must use a reasonably efficient approach that quickly works up to n==9, which will return a 12-digit answer! In particular, this means you cannot just edit nthPrime (or fasterIsPrime) to call isCarolPrime instead of isPrime.

  9. nearestKaprekarNumber(n) [10 pts] [autograded]
    Background: a Kaprekar number is a non-negative integer, the representation of whose square can be split into two parts (where the right part is not zero) that add up to the original number again. For instance, 45 is a Kaprekar number, because 45**2 = 2025 and 20+25 = 45. You can read more about Kaprekar numbers here. The first several Kaprekar numbers are: 1, 9, 45, 55, 99, 297, 703, 999 , 2223, 2728,... With this in mind, write the function nearestKaprekarNumber(n) that takes a numeric value n and returns the Kaprekar number closest to n, with ties going to smaller value. For example, nearestKaprekarNumber(49) returns 45, and nearestKaprekarNumber(51) returns 55. And since ties go to the smaller number, nearestKaprekarNumber(50) returns 45.

    Note: as you probably guessed, this also cannot be solved by counting up from 0, as that will not be efficient enough to get past the autograder.

  10. bubblesortSimulator(app, canvas) [50 pts] [manually graded]
    For this problem, you will use our Basic Interactive Graphics package to write a bubblesort simulator, similar to the xSortLab that we used in class (the link is provided in the course notes on efficiency). You only have to do bubblesort, and you only have to do the Visual Sort (not the timed sort). You do not have to include "Go" (run), just "Step". And you do not need any buttons that work with mouse presses -- it can all be driven by keyboard commands if you wish ('s' to step and 'r' to restart; in any case, display some simple help text at the bottom of your screen, listing the keyboard commands and what they do). You should use enough steps so that the algorithm is clear -- what is being compared, what the results of each comparison is, when swaps occur, which values are being swapped, and also when values are in sorted order. You do not need to do a perfect knockoff of xSortLab. In fact, you may vary your design quite a bit if you wish, so long as what you do (in our estimation) makes each step of the algorithm very clear.

    A fairly close xSortLab knockoff (ignoring the animated effects) would get full credit. But we will give up to 2.5 points of bonus for really nice designs that are quite unlike xSortLab and which do a great job in helping the user understand how bubblesort works. That's not enough bonus for you to invest tons of effort into this, but it means that some nice work on your part could garner some extra well-earned points.

    Note: you may want to use random.shuffle(a) here.

    Note: you should not do anything animated here, even though xSortLab does animated some of the bar movements. That is: the only changes in your graphics should occur in immediate response to a keypress event.

  11. bonus/optional: evaluateTimeComplexity(f) [up to 5 pts] [manually graded]
    For this problem, write the function evaluateTimeComplexity(f). This function takes another function, f(n), and that function is guaranteed to only take one parameter, n, of type int. Your function should first call f with various sizes of n to find one that takes about one-half second to run. Do this efficiently. Then, increase the size of n by some well-chosen constant c and then time the call to f(c*n). Based on the timing of the results, you should be able to guess the function family for the time complexity of f(n). You may assume that the function is in one of these function families: O(1), O(logn), O(nlogn), or O(n**k) where k is some value in [0.5, 1, 1.5, 2, 2.5,...]. Also, you might need to make a couple calls with a couple different c's to be sure. In any case, when you are done, create a graphical window and display a nice graph with n on the x axis and the time to run f(n) on the y axis. Finally, label the graph with f.__name__ and also the big-oh function family that you determined the function requires. There are numerous design decisions left to you. Have fun!

Here are some hints and clarifications: