Homework 7 (due 5/24)
CSC 401

We talked about scope and namespaces (Section 7.1, 7.2), exceptions (Section 7.3), and, very briefly, about modules (Section 7.4). Most of our time was spent on a new computational problem solving technique: recursion. We programmed various examples (many of which can be found in Sections 10.1 and 10.2 of the book). We will continue next week with additional examples of recursion, including applications to searching in a list and in a folder structures (10.3/10.4). We will skip Chapters 8 (on the object-oriented programming in Python) and Chapter 9 (on GUIs).

More on the Koch snowflake, including a discussion showing that it has infinite length (a phenomenon also known as the coastline paradox). (Not CS: some beautiful pictures of real snowflakes.)

1. (Reading Assignment) Read Sections 7.1,-7.4, 10.1 and 10.2 of the textbook. If you want to read ahead, continue with 10.3, 10.4 and 10.5.

2. (Exceptions, 10pt) You've written a short program that allows a user to enter a number and then calculates the square root using math.sqrt. Here is the program:

The program has some problems: for example, if we enter numbers that are too large, then sqrt cannot handle them, since floating point values are limited in size, or you may enter a string which does not represent a number by mistake. Finally, the user may decide not to use the program, and precc ctrl-c to interrupt execution before entering a number. Treat all of these cases using exceptions. Which exceptions? Carefully watch the error messages you get, or check out Python's built-in Exceptions. Below are some testruns of the modified squareroot() program. Do not use any if statements.

3. (Triangles, 10pt). You'll be redoing a problem we saw in class: writing a function triangle(n) which prints triangles. Here is a screenshot of two test-runs.

So what's the difference? This time do it without using any loops, but using recursion instead. You are allowed, however, to use string multiplication: n*'*' to create the string for each line. Hint: make sure you the recursion stops. You can start with the countdown example, it's very similar, except it prints numbers instead of asterisks.

4. (Upper Case letters, 10pt) Write a function upperct(s) that returns the number of upper case letters in a string s. Do not use any type of loops for this, do not use count() method. Do use recursion.

Hint: remember that your function needs to return a value, not print it. isupper() will be useful.

5. (Joining, 10pt) Write a function join(lst) that takes a list of strings and concatenates the string into a single string. Do not use any loops for this, and do not use the built-in method join (which does exactly the same thing). See the test-runs below.

Hint: first think about the base case (it's actually one of the sample-runs above). How do you recognize the base case? What do you return in that case? (Do that part first.). Then analyze the recursive case. Since the list isn't empty, there's a first element in lst, and the remaining list (how do you write first element in list and remaining list in Python?). Process remaining list recursively, and combine results. The digitsum example we saw is the closest one in structure to this problem, but the processing is different, of course, since there we were dealing with numbers, not lists of strings.

6. (Extra Credit, 5pt) You've gotten lots of data: a file containing a million pairs of numbers: list.txt (don't click on the link, it may crash your browser; right-click on it, and save the file; if you open the file, use a reasonably strong text-editor, or it'll crash). Here's the begining of the file:

You've also written a program smaller() that counts how many pairs in a list of pairs have the smaller value first (this includes code to load the list as a file and run the program):

However, your program crashes:

Use exceptions to trace down the root of the problem, eliminate it, and run smaller() on the repaired list. Note: You can solve this without exceptions, but for credit, write a solution that uses exceptions.