15-112 Fall 2014 Homework 6
Due Sunday, 5-Oct, at 10pm
Read these instructions first!
- This entire hw is strictly SOLO, in the same way hw1-part2, hw2, and hw3 were, so you may not even discuss the problems with any other students or anyone except the course staff.
- There is no starter file this week. Submit a single file, hw6.py. Be sure to include your name and andrew id at the top. And be sure to place all the non-autograded problems below the #ignore_rest line!
- As with last week, you may use 1d lists and tuples, in addition to strings, graphics, loops, and conditionals, but (as usual) you may not use constructs we have not yet covered (2d lists, sets, maps, recursion, etc), unless explicitly allowed below.
- This week, you may only make up to 8 submissions max to Autolab. This includes a few extra since dealing with efficiency issues can be tricky. As usual, only your last one counts.
- This being the week on efficiency, your solutions must not only be correct, they must also be reasonably efficient. The autograder will check for this. It will not require PhD level algorithmic prowess, but it will require that you do better than a naive solution (which we provide as a reference, in most cases).
-
Note: do not copy-paste the basicAnimation.py file into your hw6.py file. Instead, include the line:
from basicAnimation import BasicAnimationRunner
Be sure to include that line below the #ignore_rest line so the autograder does not get confused. And be sure that basicAnimation.py is in the same folder as your hw6.py file when you run it. We'll do the same when we run it. - Some hints and clarifications are included at the end of this document.
-
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.
-
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. - 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. - 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. -
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. -
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. -
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. -
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. -
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. -
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. -
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:
- In general
- In general, you should not use strings to solve purely numeric problems, such as nearestKaprekarNumber.
- We are not looking for deep, subtle math truths. You do not have to look up formulas for special properties of Carol numbers, for example.
- We'll not require test functions for functions you used from the notes. Just be sure to cite they are from the notes.
- Don't forget to be non-destructive in all cases except when explicitly told otherwise (such as, say, when writing a sort function).
- For questions requiring a more efficient solution, generally any movement to a better function family should be good enough. So for containsPythagoreanTriple, for example, since the naive solution is O(n**3), it's ok to reduce this to O(n**2.5) or O(n**2 logn), even though even better solutions exist.
- You may not use sets or dictionaries this week, even though yes, they would certainly help!
- You may not use eval() in general, unless explicitly called for. It's dangerous and leads to serious security holes.
- There is no recursion yet. In particular, do not use a recursive version of mergesort.
- You should know the big-oh of built-in functions you use. Most are fairly obvious. For example, max(a) has to look at every element in a, so if there are n elements in a, it is O(n). Similarly, (val in a) is O(n). sorted(a) and a.sort() are both O(nlogn).
- instrumentedSelectionSort(a) and instrumentedBubbleSort(a)
- The writeup requires that you use the exact versions from the course notes. Do not use xSortLab's versions, which are similar yet minorly different. And do not make any modifications to the versions in the course notes, except to count comparisons, swaps, and measure time.
- All swaps count, including self-swaps such as swap(a, 0, 0).
- Do not use any math or formulas to compute the number of comparisons or swaps. Instead, just count them as they occur.
- For test functions, just use some very small lists where you can manually predict and confirm the results for comparisons and swaps. And don't worry about testing the times.