15-105 SPRING 2009 [CORTINA]

HOMEWORK 5 - due Friday, February 27

WRITTEN PROBLEMS (8 pts)

Hand these problems in on paper in class on the due date specified.

(1 pt) Consider the following recursive Python function, where n ≥ 1:
```
def f(n):
	if n == 1:
		return 1
	else:
		return n + f(n-1)
```
1. Why is it recursive?
2. Determine the output of the following Python instruction by tracing its execution in the Python function above:
  print f(8)
3. What is this recursive function computing?
(1 pt) Let B(n) = the number of n-bit binary numbers that do not contain two adjacent 1's. When n = 1, there are two 1-bit binary numbers that do not contain two adjacent 1's: 0, 1. When n = 2, there are three 2-bit binary numbers that do not contain two adjacent 1's: 00, 01, 10. In general, B(n) is given by the following formulas for n ≥ 1:
B(n) = B(n-2) + B(n-1), n > 2
B(2) = 3
B(1) = 2
1. Draw a complete recursion tree to compute B(5).
2. Verify your answer from part (a) by writing out all 5-bit binary numbers and crossing out those numbers that have at least two 1's that are adjacent to each other. How many 5-bit binary numbers are left?
3. How are the values of B(n) related to multiplying pairs of rabbits? Explain.
(1.5 pt) The following algorithm creates a fractal given a square:
```
1. Divide the square into 9 equal sized squares (like a tic-tac-toe board).
2. Color in the middle square.
3. Recursively perform this algorithm on all of the non-colored squares.
```
1. Print out this sheet of grid paper and trace this algorithm with a square of size 27 X 27.
2. Determine the number of non-colored squares in your fractal WITHOUT counting all of the non-colored squares. Explain your answer.
(1 pt) Given the following recursive Scheme function:
```
(define (compute numlist)
   (if (null? numlist)
       1
       (* (first numlist) (compute (rest numlist)))
   )
) 
```
What does the following Scheme function return as its result?
```
(compute (list 2 3 5 7))
```
Show your work by performing a series of substitutions to show how Scheme evaluates the function.
(1 pt) Recall the following Prolog definitions given in class:
```
parent(alice, carol). 
parent(bob, carol). 
parent(bob, david). 
parent(carol, ethel). 
parent(carol, fred). 
parent(fred, gayle).
```
Using the parent relationship, define Prolog rule(s) for descendant. (Hint: Think recursively.)
(1 pt) Write a recursive Python function that returns 2ⁿ, for any integer n, n ≥ 0. (HINT: 2ⁿ = 2 * 2^n-1 when n > 0.)
(1.5 pts) This flowchart merges two sorted vectors A and B with n cells each into a new sorted vector C with 2n cells. Trace this flowchart for the two vectors shown (where n=4), showing the values for indexA, indexB, indexC and the contents of vector C each time you reach a camera symbol.

COMPUTER PROBLEM (2 pts)

Hand this in electronically using the Electronic Handin System by 11:59PM on the due date indicated.

Write a Python function that has two parameters representing the amount invested in a one-year certificate of deposit and the annual interest rate and returns the amount in the account after one year. For example, if the amount invested is 1000 dollars and the annual interest rate is 3.0 percent, then the function should return 1030. (NOTE: When we say "return", we don't mean "print" or "output". We mean "return" the result to the part of the program that calls this function.) This function is NOT recursive.

Now write a main function that asks the user for an initial amount to invest in a one-year certificate of deposit and the annual interest rate, and displays the amount in the certificate of deposit after each year for 30 years. Assume the user does not deposit or withdraw any money from this account during the 30 years.

Basic algorithm for main:

1. Input amount for initial investment and store this as your current amount.
2. Input annual interest rate.
3. Repeat the following 30 times:
   a. Call your other function with the current amount and rate,
      and store its returned value as your new current amount.
   b. Output the year number and current amount.

For example, here is a sample run of this program:

Input initial investment amount: 1000
Input annual interest rate: 3 
Year 	Amount
1 	1030.0
2 	1060.9
3 	1092.73
4 	1125.51
5 	1159.28
6 	1194.06
7 	1229.88
8 	1266.78
9 	1304.78
10 	1343.92
11 	1384.24
12 	1425.77
13 	1468.54
14 	1512.6
15 	1557.98
16 	1604.72
17 	1652.86
18 	1702.45
19 	1753.52
20 	1806.13
21 	1860.31
22 	1916.12
23 	1973.6
24 	2032.81
25 	2093.79
26 	2156.6
27 	2221.3
28 	2287.94
29 	2356.58
30 	2427.28

To round the amounts to the nearest cent, multiply the amount by 100.0, round it off to the nearest integer using the round function, and then divide by 100.0. You do not have to worry about the missing zeroes if the number of cents is a multiple of 10 (e.g. 2156.6 is ok).