CMU 15-112: Fundamentals of Programming and Computer Science
Homework 10 (Due Thu 4-Nov at 10pm ET)

1. This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
2. There is no Early-Bird Bonus on this hw, and no Friday Lab in week10 (note that Fri 5-Nov is CMU Community Engagement Day, with no classes).
3. The same rules about recursion from hw9 apply to this hw, with one exception: Unlike last hw, in this hw you can use for loops or while loops, as long as you also use recursion meaningfully in each problem.
4. You will need these starter files:
   • hw10.py
   • cs112_f21_week10_linter.py
   • sampleFiles.zip
5. For this hw, you may submit to Autolab up to 5 times, but only your last submission counts.
6. Do not hardcode the test cases in your solutions.

1. TA-Led Mini-Lecture [10 pts]
2. findLargestFile(path) [40 pts]
3. knightsTour(rows, cols) # with backtracking [50 pts]

1. TA-Led Mini-Lecture [10 pts]
   Attend one of the TA-Led Mini-Lectures. These are separate from recitations, small-groups, large-groups, etc. See the course schedule for a list of your many fine options to attend. Also, look to Piazza for descriptions and additional information. As always, to receive full credit, you must show up on time, stay the whole time, be focused and uni-tasking (not multi-tasking), and fully participating.


2. findLargestFile(path) [40 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.
   
   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.
   
   Also note that some file systems list files in different orders than other file systems. Because of this, you need to be sure that your solution does not depend on the order in which your file system lists the files in a folder.
   
   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 found the following functions to be especially helpful:
      • os.path.isdir(path)
      • os.listdir(path)
      • os.path.getsize(path)
   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 ...


3. knightsTour(rows, cols) # with backtracking [50 pts] [autograded]
   First, read about the Knight's Tour problem here. Next, write the function knightsTour(rows, cols) that takes a non-negative int n and returns a 2d list of a knight's tour on a rows-by-cols board, or None if this does not exist. This is a slight generalization since here we will allow non-square rectangular boards.
   
   Following these instructions, knightsTour(4, 5) should return a legal 4x5 knight's tour, such as this one:

   [
    [ 1, 14,  5, 18,  7], 
    [10, 19,  8, 13,  4],
    [15,  2, 11,  6, 17],
    [20,  9, 16,  3, 12]
   ]
   

   Here we see that the tour started at 1, which is at the top-left corner. Then following the sequence 1,2,3,... to follow each move in order.
   
   Note that it is possible for some dimensions that there is a legal knight's tour, only not one starting at the top-left corner. You will have to account for that in your solution.
   
   Also: backtracking can be slow, and your solution will probably not run fast enough after 6-by-6 or so. That's ok. :-)
   
   Optional extra challenge: speed this up! There are techniques that can make this work fast enough for somewhat larger boards (though they still bog down eventually). You can do some pondering of your own, or some internet sleuthing, but in any case, try to make this run faster. Or not, since it is optional.
   
   In any case, have fun!