Homework 5 (due 10/29)
CSC 243

We have talked a bit more about dictionaries, and sets(6.1/6.2), and then started talking about recursion (Chapter 10).

We will continue with recursion, and then move on to objects, classes and inheritance (Chapter 8).

Other topics I mentioned:

Submission: The homework is due by midnight (I will not accept late homeworks). You can submit your homework through d2l into the drop-box for this homework.

Please prepare your homework as a single file containing all answers (e.g. doc, docx, or pdf, not a zip file). When submitting programs, include the programs, together with screenshots of test-runs of your program (make sure screenshots are sized so the text is legible; resize and/or crop the images). For an example, see hwexample.docx. How to take screenshots? Check out screenshots for MAC, Windows, Linux. Unless I ask for it specifically, you do not have to submit separate files with program code or executables. If multiple files are necessary, please do not zip them up, just submit them separately.

1. (Reading Assignment) Read Sections 6.1, 6.2, and 10.1, 10.2. If you want to look ahead, continue with 10.3, and chapter 8.

2. (Lookup, 15pt) We want to know where to find words in a text. That calls for an index. In the past we've looked for words ad-hoc, reprocessing the file every time we looked for a word. With dictionaries we can be more efficient: we can store the index in a dictionary and reuse it as often as we need.

a) [8pt] Write a function index_lines(fname) that returns a dictionary in which the keys are all the words in file fname, and the values are the lines of fname, in which the words occur. See below for results of a test-run. The word innocent then occurs in 7 lines, the first one being 783. Hint: you need an indexed loop. Hint 2: Your dictionary will have lists as values. In a first step, you can try storing just a single line number per word. Hint 3: I use re.split('\W+', line) to get the words in a line. If you use split, you'll get slightly different results.

b) [7pt] Write a function look-up(fname) which calls index_lines to build the index for fname, and then runs an infinite loop, prompting a user for words, and returning the list of lines on which that word can be found. See below for test-runs.

For the following problem on recursion, you do have to use recursion. Do not use global variables and do not add arguments to  your functions.

3. (First Digit, 10pt) Write a recursive function first_digit(n) that returns the first digit on n. For this problem, you are not allowed to work with strings, for loops, or fancy arithmetic. Your function needs to be really recursive. Hint: start with the digit_sum example from class.

4. (Secret Messages, 15pt) This time the secret message hidden in the covertext is just all the upper case letters in the text. We want to find them recursively. In two steps. Do not use any type of loop for either of these problems. Using isupper() or islower() is fine.

a) [7pt] Write a recursive function print_hidden(s) that prints all the upper case letters in s, one per line. See screenshot below.

b) [8pt] Write a recursive function hidden(s) that concatenates the upper-case letters and returns the result. The structure is similar to a), but you need to work with returning the right results in each step. As usual, it helps if you've done an example by hand first.

Marcus Schaefer
Last updated: October 23rd, 2019.