## Description

Write a SCHEME expression to evaluate:

1. the sum of 4, 8, 15, 16, 23 and 42

2. the product of 653, 854, 321 and 241, 304, 201

3. 5+4+(2−(3−(6+

4

5

)))

3(6−2)(2−7)

Functions

1. Simple Functions

(a) Define a SCHEME function which takes a number as a parameter and returns the

absolute value of that number.

(b) Define a function to convert a temperature from Fahrenheit to Celsius, and another to

convert in the other direction. The two formulas are F =

9

5

C +32 and C =

5

9

(F −32).

(c) Define a SCHEME function named discount which takes a product’s price and discount (as a percent) and returns the discounted price of the product.

(d) Write a procedure to compute the tip you should leave at a restaurant. It should take

the total bill as its argument and return the amount of the tip. It should tip by 20%,

but it should know to round up so that the total amount of money you leave (tip plus

original bill) is a whole number of dollars. (Use the ceiling procedure to round

up.)

(e) Most latex paints cover approx. 400 sq. ft. of area. Stains and varnishes cover 500

sq.ft. of area. Write a SCHEME function that takes the length and width (or height)

of an area to be covered as well as if the area is to be painted or stained (a boolean

parameter would be useful here) and returns the number of gallons required to finish

one coat.

(f) Suppose you are contacted by a client who lives in a house where all of the ceilings

are hemispheres; he would like a SCHEME function that takes the radius of a ceiling

(in feet), plus whether it is to be painted or stained, and returns the number of gallons

1 CSE 1729

required to paint one coat on the ceiling. Feel free to use your function from part (e)

as a helper.

2. Recursion

(a) (Towers of Hanoi) The Towers of Hanoi is a famous puzzle with a recursive solution.

There are many versions of the legend. One version of the description tells of a

temple where the monks spend their days transferring large disks of different sizes

between three pegs (each forming a tower). Disks can only be moved according to

the following rules:

1. Can only move one disk at a time

2. Disks must be properly stacked, disks may only be placed on larger disks

3. All disks but one must be on one of the three pegs

The recursive solution to this problem labels the three pegs as the source, destination

and temporary pegs. The recursive decomposition follows the following form; a stack

of n disks on the source peg can be moved to the destination peg by moving the top

n − 1 disks to the temporary peg, moving the largest disk to the destination peg and

then moving the n−1 smallest disks to the destination peg. This gives us the following

algorithm for a function that takes four parameters. The pegs labeled source, temp

and dest as well as the number of disks to be moved.

(define (towers-of-hanoi n source temp dest)

1. (towers-of-hanoi n-1 source dest temp)

2. move disk n from source to dest

3. (towers-of-hanoi n-1 temp source dest))

Define a SCHEME function that lists steps one can follow to solve the Towers of Hanoi

puzzle. You can use the SCHEME function display to print a message indicating

which disk to move and which pegs to move it from and to (step (b) in the algorithm

above). Parameters representing pegs can accept integers identifying each of the pegs

(e.g. 1 2 and 3).

3. Tail Recursion

(a) Write 2 SCHEME functions that takes a list of numbers as a parameter and returns the

number of non-negative numbers. One should be tail-reursive, the other should not

be.

(b) Write a SCHEME function that takes two integers as parameters and returns their

greatest common divisor (GCD) using Euclid’s Algorithm. From Wikipedia: “The

GCD of two numbers is the largest number that divides both of them without leaving

a remainder. The Euclidean algorithm is based on the principle that the greatest

common divisor of two numbers does not change if the smaller number is subtracted

from the larger number. For example, 21 is the GCD of 252 and 105 (252 = 21 ×

12; 105 = 21×5); since 252 – 105 = 147, the GCD of 147 and 105 is also 21. Since the

2 CSE 1729

larger of the two numbers is reduced, repeating this process gives successively smaller

numbers until one of them is zero. When that occurs, the GCD is the remaining

nonzero number.”

4. Higher-Order Functions

(a) (SICP Exercise 1.43) If f is a numerical function and n is a positive integer, then we

can form the n

th repeated application of f , which is defined to be the function whose

value at x is f (f (…(f (x))…)). For example, if f is the function x 7→ x + 1, then

the n

th repeated application of f is the function x 7→ x + n. If f is the operation of

squaring a number, then the n

th repeated application of f is the function that raises

its argument to the 2n

th power. Write a procedure that takes as inputs a procedure

that computes f and a positive integer n and returns the procedure that computes

the n

th repeated application of f . Your procedure should be able to be used as follows:

(( repeated square 2) 5)

625

Hint: You may find it convenient to use compose from exercise 1.42.

(b) (SICP Exercise 1.44) The idea of smoothing a function is an important concept in

signal processing. If f is a function and d x is some small number, then the smoothed

version of f is the function whose value at a point x is the average of f (x − d x),

f (x), and f (x +d x). Write a procedure smooth that takes as inputs a procedure that

computes f and a number d x and returns a procedure that computes the smoothed

f .

List Processing

1. Pairs

(a) Define a function that takes two pairs, representing two points, as parameters and

returns a pair consisting of the slope and y-intercept of the line intersecting those two

points.

(b) (Unusual Canceling) The fraction 64

16 exhibits the unusual property that its reduced

value of 4 may be obtained by “canceling” the 6 in the numerator with the 6 in the

denominator. Define a SCHEME function which takes a fraction represented as a pair

and returns a boolean value indicating whether the value of the fraction remains

unchanged after this unusual canceling.

If x y is the two digit number (e.g. if n = 64 then x = 6 and y = 4) then

1. n = 10x + y

2. x = (floor (/ n 10))

3. b = (modulo n 10)

3

2. Lists

(a) Write a function that computes the largest distance between any two adjacent elements of a list.

(b) Write a function that, given a list (a1

. . . ak

), returns the list (b1

. . . bk−1

) so that bi =

ai+1 − ai

.

(c) Write a function which takes a list of numbers as parameters and returns a pair representing the range of the numbers in the list. That is, the first in the pair returned

should be the minimum element of the list and the second should be the maximum.

(d) Define a SCHEME function which uses the solution to the Pairs question b to produce

a list of pairs representing all of the fractions which exhibit the unusual canceling

property. Note: you may limit yourself to fractions which have only two digits in

their numerators and denominators.

(e) (The Knapsack problem.) You and a friend are going backpacking, and must bring

along a bunch of equipment. You’d like to split the equipment between the two of

you as evenly as possible. Write a SCHEME function to do this. Specifically, given a

list of weights (w1 w2

. . . wn

), find a subcollection of the weights (a1 a2

… ak

P

) so that

i

ai

is as close as possible to half the total weight of the wi

.

(f) Define a SCHEME function list-insert, taking three arguments: a list, the new

item, and the numerical position where you want the new item to be, starting at 1.

So (list-insert ’(a b c) ’d 4) evaluates to (a b c d), and (list-insert

’(a b c) ’d 1) evaluates to (d a b c). This function should use no destructive

modification.

(g) Define a SCHEME function list-insert!, taking three arguments: a non-empty

list, the new item, and the numerical position where you want the new item to be,

starting at 1 (if the position is larger than the length of the list the item should be

put at the end of the list. This should add the item using destructive modification, so

any variable that refers to the list and any structure containing that list (the tail of an

append, e.g.) will be changed. Example:

> ( define a ‘( a b c ))

> ( define b ‘( d e f ))

> b

( d e f )

> ( define c ( append a b ))

> c

( a b c d e f )

> ( insert-list ! b ‘z 1)

( z d e f)

> b

( z d e f)

> c

4

( a b c z d e f )

> ( insert-list ! b ‘w 4)

( z d e w f )

> d

( a b c z d e w f )

Hint: draw a box-and-arrow diagram first.

(h) (The Josephus Problem) The Josephus problem resembles the game of musical chairs,

a version of the problem is as follows:

A travel agent selects n customers to compete in the finals of a contest for a two week

vacation in Maui. The agent places the customers in a circle and then draws a number

m out of a hat. the game is played by having the agent walk clockwise around a circle

and stopping at every mth customer and asking that customer to leave the circle, until

only one remains. The one remaining customer is the winner.

Define a SCHEME function that takes a circular linked list as a parameter, generates a

pseudo-random number and follows the Josephus algorithm to eliminate all but one

node in the list and returns the value in the last remaining node in the list. Note:

you will need to build a circular linked list by setting the cdr of a list to the list itself

(using set-cdr! – you should probably write a function that takes a list and turns

it into a circular list.

3. Trees

( define ( maketree v left-tree right-tree )

( list v left-tree right-tree ))

( define ( value T ) ( car T ))

( define ( left T ) ( cadr T ))

( define ( right T ) ( caddr T ))

( define ( insert x T )

( cond (( null ? T ) ( make-tree x ‘() ‘()))

(( eq ? x ( value T )) T )

(( < x ( value T )) ( make-tree ( value T ) ( insert x ( left T )) ( right T ))) (( > x ( value T )) ( make-tree ( value T )

( left T )

( insert x ( right T ))))))

(a) Define a SCHEME function named count-one-child which returns the number of

internal nodes of a binary search tree which have exactly one child.

(b) Define a SCHEME function named count which given a binary search tree and a value,

returns the number of occurrences of the value in the tree.

5 CSE 1729

(c) Given a heap as defined in lecture, where all of the h-min values are positive, write a

SCHEME function that returns the maximum value in the heap.

4. Streams

(a) Write a function that, given a stream containing numbers (a1a2

. . .), returns the stream

(b1 b2

. . .) so that bi = ai+1 − ai

. This should work for both finite and infinite streams,

and should be written in terms of stream operators.

(b) (Sieve of Eratosthenes) In ancient Greece, Eratosthenes gave the following algorithm

for finding all prime numbers up to a specified number M:

1. Write down the numbers 2, 3, . . . M.

2. Cross out the numbers as follows:

(a) Keep 2 but cross out all multiples of 2 (i.e. cross out 4, 6, 8, . . .).

(b) Keep 3 but cross out all multiples of 3 (i.e. cross out 6, 9, 12, . . .).

(c) Since 4 is already crossed out, go on to the next number that is not crossed

out.

(d) Keep 5 but cross out all multiples of 5.

Modifying this approach to streams, we can get the stream of all primes. Write a

SCHEME function that generates the stream of prime numbers using the Sieve of

Eratosthenes as follows: starting with the stream of all integers from 2 up, return

primes-from that stream. primes-from takes a stream and cons-stream’s the

stream-car of that list with the result of calling primes-from on the stream with

all multiples of the stream-car filtered out.

Note: we saw the code in lecture, but better if you write this from scratch and really

understand how it works.

5. Objects

(a) Modify the following code from Lab 8 to require a password (by adding another

parameter) for balance inquiries, deposits and withdrawals on the (new-account)

object. The password should be set as an additional parameter to the new-account

function.

( define ( new-account initial-balance )

( let (( balance initial-balance )

( interestrate 0.01))

( define ( deposit f)

( begin

( set ! balance

(+ balance f ))

balance ))

( define ( withdraw f )

( begin

6 CSE 1729

( set ! balance

(- balance f ))

balance ))

( define ( bal-inq ) balance )

( define ( accrue ) ( begin ( set ! balance

(+ balance

(* balance

1

interestrate )))

balance ))

( define ( setrate r) ( set ! interestrate r ))

( lambda ( method )

( cond (( eq ? method ‘ deposit ) deposit )

(( eq ? method ‘ withdraw ) withdraw )

(( eq ? method ‘ balance-inquire ) bal-inq )

(( eq ? method ‘ accrue ) accrue )

(( eq ? method ‘ setrate ) setrate )))))

(b) Add a method to the new-account object to change the password. It should take

the old password and new password as parameters.

(c) Write a SCHEME function that implements an object representing a rational number.

It should use the GCD function (number b in the Tail Recursion question) to reduce

the fraction represented by the object.

(d) Define a SCHEME object to model a traffic-light that is always in one of four states,

represented by the symbols ’red, ’yellow, ’green, and ’flashing-red. A traffic light can

respond to four messages:

show: which returns the current state.

emergency! , which sets the state to ’flashing-red, regardless of what it was before.

set-light , which takes one argument – one of the symbols ’red, ’yellow, or ’green –

and sets the state to that symbol.

cycle , which has no effect if the current state is ’flashing-red, but changes a ’green

state to ’yellow, a ’yellow state to ’red, and a ’red state to ’green.

7 CSE 1729