CMU 15-112: Fundamentals of Programming and Computer Science
Homework 11 (Due Friday 13-Nov at 8pm ET)

  • To start:
    1. Create a folder named 'week11'
    2. Download all of these to that folder:
    3. Edit hw11.py
    4. When you have completed and fully tested hw11, submit hw11.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
  • Do not hardcode the test cases in your solutions.

  • A few more notes:
    1. Recursion-Only alternatingSum(L) [25 pts] [autograded]
      Write the function alternatingSum(L) that takes a possibly-empty list of numbers, and returns the alternating sum of the list, where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3). If L is empty, return 0. You may not use loops/iteration in this problem.

    2. Recursion-Only onlyEvenDigits(L) [25 pts] [autograded]
      Without using iteration and without using strings, write the recursive function onlyEvenDigits(L), that takes a list L of non-negative integers (you may assume that), and returns a new list of the same numbers only without their odd digits (if that leaves no digits, then replace the number with 0). So: onlyEvenDigits([43, 23265, 17, 58344]) returns [4, 226, 0, 844]. Also the function returns the empty list if the original list is empty. Remember to not use strings. You may not use loops/iteration in this problem.

      Hint:
      • We wrote a recursive helper function onlyEvens(n) that takes an integer n and returns the same integer but with all the odd digits removed. So onlyEvens(1234) returns 24.

    3. Recursion-Only powersOf3ToN(n) [25 pts] [autograded]
      Write the function powersOf3ToN(n) that takes a possibly-negative float or int n, and returns a list of the positive powers of 3 up to and including n. As an example, powersOf3ToN(10.5) returns [1, 3, 9]. If no such powers of 3 exist, you should return the empty list. You may not use loops/iteration in this problem.

      Hints:
      1. No matter how you solve this, it's crucial that you have just one additional recursive call per power of 3. So you can't just count up to n (or down from n) and include each value if it is a power of 3. That will stack-overflow.
      2. Our recommended approach to solving this uses a recursive helper function powersOf3ToNHelper(n, powerOf3) that takes both n and a powerOf3 (so 1, 3, 9, etc), and returns a list of the powers of 3 starting from that power up to the largest power of 3 up to an including n. So powersOf3ToNHelper(30, 9) returns [9, 27].
      3. Another approach which is perhaps less recommended (as you have to properly manage floating-point issues) does not use a helper function, but instead uses log_3(n) to determine the largest power of 3 up to n.

    4. Recursion-Only findLargestFile(path) [25 pts] [autograded]
      Without using os.walk, write the recursive function findLargestFile(path), which takes a string path to a folder and returns the full path to the largest file in terms of bytes in the folder (and all its subfolders). You can compute the size of a file using os.path.getsize(path). If there are no files, the empty string ("") is returned. You do not need to handle the case where the supplied path is not valid or is not a folder, and you may handle ties however you wish. You may not use loops/iteration in this problem.

      Note that file systems can be very large, so in this problem, efficiency is important! Therefore, you may not use listFiles (or anything similar) to gather all the files into one place, and you should avoid calling os.path.getsize on a single file more than once.

      To help test your code, here are some assertions for use with sampleFiles (available in sampleFiles.zip):

      assert(findLargestFile("sampleFiles/folderA") == "sampleFiles/folderA/folderC/giftwrap.txt") assert(findLargestFile("sampleFiles/folderB") == "sampleFiles/folderB/folderH/driving.txt") assert(findLargestFile("sampleFiles/folderB/folderF") == "")

      Hints:
      1. You also may need to get rid of those pesky .DS_Store files that Macs like to add to folders that you unzip. To do that, use removeTempFiles. Remember to be careful, since it removes without asking and it does not move the removed files to the trash (they are really gone).
      2. We used two helper functions (for three total functions).
      3. Here are the headers for each of the functions we wrote, with brief descriptions:
        def findLargestFile(path): # Wrapper to extract just the bestPath from the helper # function that returns both bestPath and bestSize ... def findLargestFileAndSize(path): # Returns (bestPath, bestSize) starting from this path, which could # be to either a folder or a file ... def findLargestFileAndSizeInDir(path, files): # This assumes that path is to a folder, and it returns # (bestPath, bestSize) for all the files/folders in this folder. # The second parameter, files, is a list of files in this folder, # as returned by os.listdir(). ...