Description
Exercise 1. In file ex1.rkt, define a procedure named sum-largest-squares that takes three
numbers as arguments and returns the sum of the squares of the largest two numbers. Your solution must
use of the square and sum-of-squares procedures that were presented in class.
Exercise 2. The operator in a Racket/Scheme combination can be a compound expression, as shown by
procedure a-b:
(define (a-b a b)
((cond [(> b 0) +]
[(= b 0) -]
[else *]) a b))
What does procedure a-b do for all integers a and b? Justify your answer by using the substitution
model of execution to illustrate the process generated by the procedure for different values of a and b.
Save your solution in file ex2.rkt.
Exercise 3. In file ex3.rkt, define a recursive procedure named sum-odd-digits that computes the
sum of the odd digits of a positive integer. For example, (sum-odd-digits 1285) computes 6.
Exercise 4. Each container in a warehouse is marked with a numeric code to indicate the quantity of
each type of item stored in the container. The code consists of an unlimited number of triples of integer
digits. In each triple, the last two digits specify the type of an item and the first digit specifies the
quantity of that item. For example, the code 812493 indicates that there are 8 type-12 items and 4
type-93 items. The code 915815715 indicates that there are 24 type-15 items (9 plus 8 plus 7).
In file ex4.rkt, define a recursive procedure (count-of-items code type) that returns the quantity
of items of the specified type in the container, as recorded in code. Return 0 if there are no items of
that type.
Exercise 5. The greatest common divisor (GCD) of two integers a and b is defined to be the largest
integer that divides both a and b with no remainder. For example, the GCD of 16 and 28 is 4.
Euclid’s Algorithm is a famous technique for efficiently calculates the GCD of two positive integers. The
basis of this algorithm is that observation that, if r is the remainder when a is divided by b, then the
common divisors of a and b are precisely the same as the common divisors of b and r. Thus, we can use
the equation
GCD(a, b) = GCD(b, r)
to successively reduce the problem of computing a GCD to the problem of computing the GCD of
smaller and smaller pairs of integers. For example,
GCD(206, 40) = GCD(40, 6) = GCD(6, 4) = GCD(4, 2) = GCD(2, 0) = 2
reduces GCD(206,40) to GCD(2,0), which is 2.
Starting with any pair of positive integers, performing repeated reductions will eventually produce a pair
where the second number is 0. The GCD is the other number in the pair.
2
Euclid’s Algorithm can easily be defined as a procedure:
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
Is the process generated by (gcd 279 15) is iterative or recursive? Justify your answer by using the
substitution model to illustrate the process generated by the procedure. Save your solution in file
ex5.rkt.
Exercise 6. Consider these procedures:
(define (increment a) (+ a 1))
(define (decrement a) (- a 1))
(define (add-ab a b)
(if (= a 0)
b
(increment (add-ab (decrement a) b))))
(define (sum-ab a b)
(if (= a 0)
b
(sum-ab (decrement a) (increment b))))
Both procedures use recursive procedure calls to perform the addition (+ a b).
For each of parts (a) and (b), justify your answer by using the substitution model to illustrate the process
generated by the procedure. Save your solution in file ex6.rkt.
(a) Is the process generated by (add-ab 3 4) iterative or recursive?
(b) Is the process generated by (sum-ab 3 4) iterative or recursive?
Exercise 7. A function f is defined as:
f(n) = n if n < 4
and
f(n) = 2f(n − 1) + 3f(n − 3) + 4f(n − 5) if n ≥ 4.
(a) Define a recursive procedure f-recursive that computes f by means of a recursive process.
(b) Define a recursive procedure f-iterative that computes f by means of an iterative process.
Save your procedures in file ex7.rkt.
3
Exercise 8. This higher-order summing procedure was developed in class:
(define (sum fn a next b)
(if (> a b)
0
(+ (fn a)
(sum fn (next a) next b))))
Given helper procedures identity and increment, we can define a procedure that calls sum to add
all the integers between a and b, inclusive:
(define (identity x) x)
(define (increment n) (+ n 1))
(define (sum-integers a b)
(sum identity a increment b))
Procedure sum generates a recursive process. In file ex8.rkt, reimplement sum so that it generates a
iterative process. Verify that the behaviour of sum-integers doesn’t change when it calls the new
implementation of sum.
4