15-112 Spring 2015 Homework 7
Due Sunday, 1-Mar, at 10pm

• This hw is entirely SOLO.


• Starting this week, you may use sets and maps, in addition to 2d lists, event-based animations, 1d-lists, tuples, strings, graphics, loops and conditionals, but (as usual) you may not use constructs we have not yet covered (recursion, etc), unless explicitly allowed below.


• Part of this hw is autograded. You may make up to 5 submissions. As usual, only your last one counts.


• Do not use global variables! Do use test functions! Do use helper functions!


• This hw is somewhat lighter than usual, to give you time to catch your breath and to study for the upcoming midterm.

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 hw7, 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. mergeSortWithOneAuxList(a) [10 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.
   
   Note: Your test function here can do little more than confirm that at least the function does sort a list correctly. The more ambitious among you could also confirm that this remains O(nlogn).


3. friendsOfFriends(d) [30pts] [autograded]
   Do friendsOfFriends from here.


4. F14 Midterm1 [30 pts, manually graded (by effort)]
   Take f14-midterm1 under nearly-exam conditions, in one sitting, in 80 minutes, without access to a Python interpreter, or a calculator, or the class notes, etc. However, unlike an exam, here you will type your solutions into an editor, so that you can submit them in the triple-quoted string at the top of your hw7.py file (actually, they will go just below your answers to your next question, as noted below).
   
   Note: be sure to show your work, especially for CT and RC problems!
   
   We will provide optional solution sessions to this midterm, which we strongly encourage but do not require that you attend. Note that we will grade this part of hw7 only on effort, not correctness, so if you do this exercise with reasonable effort (as you should!), you'll get all the points.


5. Better Big-Oh [30 pts, manually graded]
   Note: Place your solutions to these Better-Big-Oh problems in a triple-quoted string at the top of your hw7.py, above your solutions to f14-midterm1.
   
   For each of the following functions:
   1. State in just a few words what it does in general.
   2. State and prove (in a few words) its worst-case big-oh runtime.
   3. Provide an equivalent Python function that is more than a constant-factor faster (so it's worst-case big-oh runtime is in a different function family). The better your solution's big-oh runtime, the more points you get!
   4. State and prove (in a few words) your better solution's worst-case big-oh runtime.
   You should assume that lists all contain at least 5 values, and only integer values. Also, if a function takes two lists, you should assume they are the same length n.
   
   

   import copy
   
   def slow1(a):
       (b, c) = (copy.copy(a), 0)
       while (b != [ ]):
           b.pop()
           c += 1
       return c
   
   def slow2(a):
       n = len(a)
       count = 0
       for i in xrange(n):
           for j in xrange(n):
               if (a[i] == a[j]):
                   count += 1
       return (count == n)
   
   def slow3(a, b):
       # assume a and b are the same length n
       n = len(a)
       assert(n == len(b))
       result = 0
       for c in b:
           if c not in a:
               result += 1
       return result 
   
   def slow4(a, b):
       # assume a and b are the same length n
       n = len(a)
       assert(n == len(b))
       result = abs(a[0] - b[0])
       for c in a:
           for d in b:
               delta = abs(c - d)
               if (delta > result):
                   result = delta
       return result
   
   def slow5(a, b):
       # Hint: this is a tricky one!  Even though it looks syntactically
       # almost identical to the previous problem, in fact the solution
       # is very different and more complicated.
       # You'll want to sort one of the lists,
       # and then use binary search over that sorted list (for each value in
       # the other list).  In fact, you should use bisect.bisect for this
       # (you can read about this function in the online Python documentation).
       # The bisect function returns the index i at which you would insert the
       # value to keep the list sorted (with a couple edge cases to consider, such
       # as if the value is less than or greater than all the values in the list, 
       # or if the value actually occurs in the list).
       # The rest is left to you...
       #
       # assume a and b are the same length n
       n = len(a)
       assert(n == len(b))
       result = abs(a[0] - b[0])
       for c in a:
           for d in b:
               delta = abs(c - d)
               if (delta < result):
                   result = delta
       return result
   



6. Bonus/Optional: O(n) checkNearlySorted() [1 pt, manually graded]
   Write checkNearlySorted() from quiz5, but here it must be O(n). Have fun!


7. Bonus/Optional: 3d Tetris [5 pts, manually graded]
   Write the function play3dTetris() that takes no arguments and plays a 3d version of Tetris, similar for example to this video. Include a help screen when the user presses “h”, which explains the controls. Do this using Tinter, so keep the graphics as simple as you can while still looking 3d. Keep your time on this capped to 5 hours or less. Have yet more fun!