Spring 2005

HW5: Scheme Programming

For this assignment, you are to define the following Scheme functions. For
simplicity, place all of your function definitions in a single file named
`hw5.scm`. Be sure to comment each function as to its behavior.

- Define functions for converting temperatures from Fahrenheit to Celsius,
and vice versa. The formula for converting from Fahrenheit to Celsius is:
tempInCelsius = (5/9) * (tempInFahrehneit - 32) For example,

`(fahr->celsius 212)`should evaluate to 100, while`(celsius->fahr 0)`should evaluate to 32.

- Define a function named
`wind-chill`that takes two inputs, a temperature (in degrees Fahrenheit) and a wind-speed (in miles per hour), and returns the corresponding wind-chill factor. The formula for computing the wind chill is:`wind-chill =`{ `temperature`*if windSpeed <= 3*`35.74 + 0.6215*temperature + (0.4275*temperature-35.75)*windSpeed`^{0.16}*otherwise*For example,

`(wind-chill 38 2)`should evaluate to 38 since a wind-speed of only 2 miles per hour has no effect on the temperature of 38 degrees Fahrenheit.

- Define a function named
`num-occur`that takes two inputs, an atom and a list, and returns a count of the number of times the atom appears in the list. For example,`(num-occur 'x '(z x e x))`should evaluate to 2.

- Define a function named
`remove`that takes two inputs, an atom and a list, and returns the list with each occurrence of the atom removed. For example,`(remove 'x '(z x e x))`should evaluate to`(z e)`.

- Define a function named
`subst`that takes three inputs, two atoms and a list, and returns the list with each occurrence of the second atom replaced by the first. For example,`(subst 'a 'x '(z x e x))`should evaluate to`(z a e a)`.

- Define a function named
`num-atoms`that takes one input, a list containing arbitrarily nested lists of atoms, and returns the number of atoms in the list. For example,`(num-atoms '(a b c))`should evaluate to 3, while`(num-atoms '(a (b (d e) c)))`should evaluate to 5.

- Define functions for converting roman numerals to numbers and back. One
function,
`roman->num`will have one input, a list of characters representing a roman numeral. It should return the number value represented by that roman numeral. For example,`(roman->num '(X V I))`should evaluate to 16. Conversely, the function`num->roman`will have an integer as input, and should return the list of characters representing the appropriate roman numeral. The following is a list of the roman letters and numbers they represent:M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5, I = 1. You may assume the old roman style of writing letters, where 4 is represented IIII and 90 is represented LXXXX. A harder problem, which you may attempt if you like, is to use the modern roman style where 4 is IV and 90 is XC.

- In class, we discussed how structured lists could be used to represent
binary trees. Define a function
named
`bst?`that takes one input, a list containing numbers, and returns true if that list represents a binary search tree (assuming the tree format described in class). Recall that a binary search tree is a binary tree in which, for every node, the data in that node is greater than or equal to all data in its left subtree, and less than all data in its right subtree. For example,`(bst? '(5 (3 () ()) (9 (8 () ()) (10 () ())))`should evaluate to`#t`, while`(bst? '(5 (3 () ()) (9 (4 () ()) (10 () ())))`and`(bst? '(5 (3 () ()) 9)`should evaluate to`#f`.

- The following function simulates a random 1-dimensional walk. Initially,
the
walker is assumed to be at position 0. Depending on a random value, the
walker
either moves to the right (in the positive direction) or to the left (in the
negative direction). The simulation ends when the walker reaches the
specified goal
distance, in
either direction.
(define (random-walk goal-dist) (define (random-walk-help position goal) (display position) (newline) (cond ((= (abs position) goal) #t) ((zero? (random 2)) (random-walk-help (add1 position) goal)) (else (random-walk-help (sub1 position) goal)))) (random-walk-help 0 goal-dist)) As is, this function displays each step in the walk and returns

`#t`when the walk ends. Modify the function so that it keeps track of the number of steps in the walk and returns this value instead. Your modification should only utilize tail-recursion.

- An interesting unsolved problem in mathematics concerns what is
called the hailstone sequence of integers. This sequence is
defined as follows: start with any integer. If that number is odd, then
multiply it by 3 and add 1. If it is even, then divide it by 2. Now,
repeat. For example, if we start with the number 5, we get the following
sequence: 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, . . .
Here, the subsequence 4, 2, 1 is reached which produces a loop. It is
conjectured that no matter what number you start with, you will always
end up stuck in the 4, 2, 1 loop. It has, in fact, been shown to hold
for all starting values less than 1,200,000,000,000 . However, it still
has not
been proven for all numbers. Define a function named
`hailstone`which has one input, the starting number, and which displays the hailstone sequence starting with that number and ending with 1. The function should return the length of the sequence. For example,`(hailstone 1)`should display the lone number 1 and evaluate to 1, while`(hailstone 5)`should display`5 16 8 4 2 1`and evaluate to 6. Your function should only utilize tail-recursion (perhaps a help function will be required).