Read these instructions first!

• This hw is entirely COLLABORATIVE.  Be certain to list the names and andrew id's of each collaborator in your group.  You may not collaborate with different students on different questions -- so you may work with only one group for the entire hw.
• What to turn in:
  • Turn in a single file, hw10.py, that contains all your solutions.
  • Place your solutions in hw10.py in the same order as they occur here, with clear comment blocks clearly separating each exercise.
  • Be sure that your hw10.py does not run anything when loaded.  In particular, your test code and also your graphics code should only run when called, and not when loaded!  Please be sure to get this right, since it really slows down grading if you don't.
• All solutions must be recursive.  You may only use loops where appropriate within recursive functions, such as a loop inside findLargestFile to iterate over the files within a specific folder.  Most problems require that you do not use loops at all in order to receive any credit.

1. Study the Recursion Notes
2. Reasoning About (Recursive) Code
3. flatten
4. findLargestFile
5. fractalMickeyMouse
6. solveABC
7. Bonus
   1. runMotionAfterefffect
   2. recursiveBubblesort
   3. solveSudoku
   4. factorizationAnimation
   5. sumOfSquaresOfResiduals (recursively)
   6. sieveOfErastothenes (recursively)

1. Study the Recursion Notes  [10 pts]
   You may work in groups of up to 4 students (yourself included).  Your task here is to meet in a group and to carefully work through the course notes from this week.  You are responsible for being able to write all the recursion examples in the notes from scratch, including:  rangeSum, listSum, power, interleave, powerWithNegativeExponents, interleaveWithDifferentLengths, fibonacci, towersOfHanoi, factorial, reverse, gcd, powerset, permutations, printFiles, listFiles, kochSnowflake, sierpinskiTriangle, selectionsort, insertionsort, quicksort, mergesort, and nQueens, and the selected portions of floodFill and mazeSolving.
   
   You may peek at the notes as needed, but it is expected that you will be able to completely write these easily from scratch under quiz conditions.  This is not a minor task, and we expect you to allocate about 4 hours for this.
   
   What to submit:  At the top of your hw10.py file, assuming you did in fact meet with your group, and that you invested hours of hard work into this, and that you can basically write the examples listed above from scratch under quiz conditions, then you should change this comment to read "I *DID* do #1, along with <andrewId's of your groupmates>".  That's it!
    
2. Reasoning About (Recursive) Code  [10 pts]
   From f11-hw5, do: the Reasoning About (Recursive) Code problems.  Place your solutions in a comment at the top of hw10.py.
    
3. flatten  [10 pts]
   From f11-hw5, do: flatten.  Place your solution in hw10.py.
    
4. findLargestFile  [10 pts]
   From f11-hw5, do: findLargestFile.  Place your solution in hw10.py.
    
5. fractalMickeyMouse  [10 pts]
   From f11-hw5, do: fractalMickeyMouse.  Place your solution in hw10.py.
    
6. solveABC [50 pts]
   This problem is inspired by the “ABC Path” problems at BrainBashers.com. For more (optional) info, check this out.
   
   Background: In what we will call an “ABC Puzzle”, you are given a 5x5 board like this:
   
   It is an empty board except that it contains a single “A” in an arbitrary cell. Also, the letters from “B” to “Y” are arranged around the outside of the board in an arbitrary order, along with arrows that constrain those letters to a certain row, column, or diagonal. For example, in the image, we see the “H” and “T” are constrained to column 0, “L” and “I” are constrained to row 0, and “C” and “G” are constrained to the column running from (0,0) to (4,4). The goal of this puzzle is to place every letter from “B” to “Y” on the board such that: (1) each letter from “B” to “Y” is placed in the row, column, or diagonal in which it is constrained; and (2) each letter from “B” to “Y” is placed adjacent (including diagonally) to the previous letter (so “B” is adjacent to “A”, and “C” is adjacent to “B”, and so on).
   
   A solution to the puzzle is here:
   
   Be sure you understand why this solves the puzzle! If you are unsure, go to the link at BrainBashers.com and read more about this kind of puzzle, including this help page, and maybe try to solve a few more of them (the puzzles include a button you can press to get the solutions!).
   
   Now, for us to represent one of these puzzles in Python, we have to represent the constraints. We’ll do that by reading them clockwise starting from the top-left corner. Thus, in the given example, the constraints are:
       constraints = "CHJXBOVLFNURGPEKWTSQDYMI"
   And we also need to specify the position of the “A”, which we will do as a (row,col) tuple, as such:
       aLocation = (0,4)
   
   With this in mind, write the function solveABC(constraints, aLocation), that takes constraints and the location of the “A”, which together define an ABC Puzzle, and returns a completed board which solves the puzzle, or None if no such board exists. Here is a test function that is based on the puzzle used in the example above (notice how the constraints and aLocation match the unsolved puzzle, and the resulting board matches the solved puzzle):
   
   def testSolveABC():
       print "Testing solveABC()...",
       constraints = "CHJXBOVLFNURGPEKWTSQDYMI"
       aLocation = (0,4)
       board = solveABC(constraints, aLocation)
       solution = [['I', 'J', 'K', 'L', 'A'],
                   ['H', 'G', 'F', 'B', 'M'],
                   ['T', 'Y', 'C', 'E', 'N'],
                   ['U', 'S', 'X', 'D', 'O'],
                   ['V', 'W', 'R', 'Q', 'P']
                  ]
       assert(board == solution)
       print "Passed!"
   
   Note:  To receive any credit for this problem, you must solve it recursively, even if you could dream up a non-recursive solution!
   Hint #1: This is a backtracking problem. Study nQueens. This is most like that problem.
   Hint #2: Our sample solution required about 50 lines of code. If you are ranging well past that, perhaps you should pause and rethink your approach. Probably in the vicinity of some blue hoodies!
    
7. Bonus [2 pts each; up to 12 pts]
   1. runMotionAfterefffect
      Write the function runMotionAfterefffect, which demonstrates the Motion Aftereffect as shown in the animation on this page. Actually, you are only responsible for the motion in the circle, and not for displaying the image (the Buddha).  You also do not need any buttons or to respond to any keypresses -- just play the animation.  You may wish to look into the canvas.create_arc method.  This is the only non-recursive exercise in this hw.
       
   2. recursiveBubblesort
      Read about bubblesort here, then write recursiveBubblesort(L), which non-destructively returns sorted(L) but uses the bubblesort algorithm to do the sorting.
       
   3. solveSudoku
      Write the function solveSudoku that takes a partially-completed Sudoku board (a 2d list with 0’s representing empty cells), and returns a solved version of the same puzzle, or None if no such solution exists.  Note:  you must use backtracking here.  Also, it will take way too long if you are not clever about the order in which you make your guesses.  For that, always find the cell that is the most constrained, that is, the one that has the fewest possible legal choices (resolving ties arbitrarily).
       
   4. factorizationAnimation
      Duplicate this animation (without looking at the Javascript, of course).
       
   5. sumOfSquaresOfResiduals (recursively)
      Write the function sumOfSquaresOfResiduals(points, f) which takes a list "points" of (x,y) pairs and a one-argument function f and returns the sum of squares of residuals (SSR) of this data set. Recall that the SSR is defined as the sum of the values (y - f(x))**2 for every (x,y) pair in the data set. If there are no points in the data set, your function should return 0.
      Hint: Consider using "map" and "reduce" (described here), two built-in functions specifically intended for use in functional programs. Also, you may find anonymous functions/closures very useful.
       
   6. sieveOfErastothenes (recursively)
      Write the function sieve(n) which returns a list of all primes up to but not including n. For any n < 2, your function should return an empty list. Your function should implement the Sieve of Eratothenes, described here.
      Hint: Consider using "filter", another built-in function intended for functional programming.
      More hints: Consider writing three functions: "doSieve", which performs one step of the sieve, "sieve", which is a wrapper for "doSieve", and "getNewP", which updates the value of your highest confirmed prime p.