Homework 8 (due 5/31)
CSC 401

We've looked at more complex examples of recursion, including generating permutations, and applications to searching in a list and in a folder structures (10.3), and we talked about linear and binary search (10.4). Other examples we saw included the Fibonacci numbers (with a discussion of run-time analysis, 10.3) and sorting (only a brief overview, see visualizations of different sorting algorithms). We finished by using recursion to solve the Towers of Hanoi problem (CS.10).

1. (Reading Assignment) Read Sections 10.3, 10.4, and CS.10 (Towers of Hanoi) of the textbook. If you want to read ahead, continue with CS.6 (Blackjack) and Chapter 8.

2. (Playing with words, 10pt) You have come up with a new idea for encrypting two texts: you mix them, by alternating between them, e.g. hello and world become hweolrllod (colors just so you can tell where each letter comes from). Write a function alt(s,t) that uses recursion to mix two strings s and t in this way (and returns the result). Check that s and t have the same length (otherwise return immediately). Not allowed are: any types of loops, string processing functions other than slicing, or global variables. Other bete-noires: remove, index, replace, ...

3. (Reporting, 7pt) Start by reviewing the program scan we saw in class which scans a folder structure for files containing a word; we want to extend it so that it scans for a list of words, instead of a single word. As it scans, it should print the name of the current directory it is scanning, and whenever it finds one, or multiple words, in a file it is scanning, it should print the full list of words it found in the file. Below is a sample run of this program scan(fname, words):

Hint: Start with the scan function we wrote; modify it so it prints the 'Scanning ...' part, that'll be useful for debugging. Then, in a first step, program scan(path, word) that looks for a single word in each file. Add an exception to ignore files you cannot open (so they don't stop execution of the program). Finally, extend this so it works a list containing a single word. Then try multiple words. You only want to scan once, so you need to check the content of each file for each word in the list. Hint 2: for each file you open, accumulate results in a list, remember the easy way we saw how to print a list without its brackets using str() and slicing.

4. (Stats, 15pt) Start by reviewing the space(path) example we saw in class. We want to do something similar here: we want to find out how many files and folders there are below a given path.

a) [10pt] Write a function files(path) which counts how many files there are below path, by recursively traversing all folders and subfolders, etc., just as in the class example we accumulated file size.

b) [5pt] Extending your work in a) write a function stats(path) which returns a pair of values: the number of files and the number of folders below path (the scan screenshot in 3 shows you all the folders on my USB stick).

Hint: start with your work from a), inactivate the file counting part, and instead add a folder counting part. Once you got that working, reactivate the file counting, and now work with the fact that you have to return a pair of numbers, and, when you call stats(path) recursively, you will get a pair of numbers that you have to process. Hint 2: (a,b) + (c,d) is not (a+c, b+d), it's tuple concatenation, so you have to add pairs "by hand" as it were.

5. (Depth, 8pt) For this problem, we want to understand another aspect of the folder structure on a computer: How deep is it. Recall that folders are arranged as a tree. We want to determine the depth of the tree, that is the deepest level of nesting that occurs within the folder structure, in other words, the largest distance from the root to a leaf in the structure. Below is a screenshot of me running it on my USB stick, where the deepest level is 4 levels deep (due to a system directory, __pycache__ that somehow made its way into my Week 8 folder):

The directory __pycache__ only contains files, so it has depth 1.

The file scan.txt contains the result of a scan on my USB stick, so you can get an idea of the folder structure. For another example, see Figure 10.8 (page 365).

5. (Exta Credit, 5pt) The last example in problem 2 shows that interleaving two words can result in an actual English word. Can you find another example of that with at least 8 letters? Can you find a longer example? What if we don't insist that both words have the same length? (E.g. if we allow 'clue' and 'old' to interlace to 'collude'?). words.txt may come in handy.