Tutorial Problem Set 1

CS 152 – Abstractions and Paradigms in Programming

1. A quick question to wind up RSA encoding. Suppose that the RSA algorithm uses the prime

numbers p and q to generate the encryption, the encoding exponent is e and the code of

a message (a number) is c. Assume that e is a prime that does not divide (p − 1)(q − 1).

Write a function (decode p q e c) to decode the message.

2. Suppose we wanted to write the following functions, explained through examples of how

they may be called:

(a) (f0 1 100): Starting with 1, the sum of every 13th number in the interval 1 to 100.

(b) (f1 2 100): The sum of squares of all odd numbers between 2 and 100.

(c) (f2 1 100): The product of the factorials of multiples of 3 between 1 and 100.

(d) (f3 10 200): The sum of the squares of the prime numbers in the interval 10 to

200.

(e) (f4 50): The product of all positive integers less than 50 that are relatively prime

to 50.

Write a higher-order function called filtered-accumulate so that the functions described

above are instances of filtered-accumulate. Write the functions f0, f1, f2, f3 and

f4 in terms of filtered-accumulate. You can assume that the arguments to f0, f1,

f2, f3 and f4 are positive.

3. Simpson’s rule is an accurate method of numerical integration. Using Simpson’s rule, the

integral of a function f between a and b is approximated as

h/3 ∗ [y0 + 4 ∗ y1 + 2 ∗ y2 + 4 ∗ y3 + 2 ∗ y4 + … + 4 ∗ yn−1 + yn]

where h = (b−a)/n, for some even integer n, and yk = f(a+kh). (Increasing n increases

the accuracy of the approximation.)

Define a procedure (simpson f a b n) that returns the value of the integral, computed

using Simpson’s Rule.

4. Assume that we represent a rational number p/q as (cons p q). With this representation,

define the following functions on rational numbers.

(a) (simplify r) – converts a rational number r into its simplest form. 12/18 simplifies

to 2/3.

(b) (add r1 r2) – adds two rational numbers r1 and r2.

(c) (muliply r1 r2) – multiplies two rational numbers.

(d) (divide r1 r2) – divides r1 by r2.

5. Write a function (minchange n) which will return the minimum number of coins required

to give change of n paise. Assume that you have sufficient numbers of 1p, 2p, 3p, 5p, 10p,

20p, 25p and 50p coins. What is the highest value of n that you can go upto in 5 minutes

of CPU time. Read the simple solution from SICP and try to improve upon the solution.

6. Monte Carlo integration: Consider computing the area of a region of space described by

a predicate P(x, y) that is true for points (x, y) in the region and false for points not in

the region. For example, the region contained within a circle of radius 3 centered at (5, 7)

is described by the predicate that tests whether (x − 5)2 + (y − 7)2 ≤ 3

2

. To estimate

the area of the region described by such a predicate, begin by choosing a rectangle that

contains the region. For example, a rectangle with diagonally opposite corners at (2, 4)

and (8, 10) contains the circle above. The desired integral is the area of that portion of the

rectangle that lies in the region. We can estimate the integral by picking, at random, points

(x, y) that lie in the rectangle, and testing P(x, y) for each point to determine whether

the point lies in the region. If we try this with many points, then the fraction of points

that fall in the region should give an estimate of the proportion of the rectangle that lies

in the region. Hence, multiplying this fraction by the area of the entire rectangle should

produce an estimate of the integral. Implement Monte Carlo integration as a procedure

estimateintegral that takes as arguments a predicate P, upper and lower bounds x1, x2,

y1, and y2 for the rectangle, and the number of trials to perform in order to produce the

estimate. Use your estimate-integral to produce an estimate of π.

Use the function defined below to generate random numbers between x1 and x2.

(define (scaled-random x1 x2)

(+ x1 (* (random)

(- x2 x1))))

7. You all know what Fibonacci numbers are: They are given by the sequence: f ib(0) =

1, f ib(1) = 1, and f ib(n) = f ib(n − 1) + f ib(n − 2).

(a) Write a tail recursive version of f ib called fib-tr.

(b) There is a nice way to compute f ib(n) even faster than the tail recursive version. We

can write f ib as a matrix as:

f ib(n)

f ib(n − 1)

=

1 1

1 0 f ib(n − 1)

f ib(n − 2)

Therefore, a closed form version of the equation will be

f ib(n)

f ib(n − 1)

=

1 1

1 0 n

1

0

And you know how to do exponentiation very fast, don’t you? Using this idea, write

a version of f ib called fib-lightning.

## Reviews

There are no reviews yet.