Homework 4

This is the archived website of SI 413 from the Fall 2012 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

- Print version, with cover page (pdf)
**Due Date**: 14 Sep- Relevant units: Unit 3

**Use a separate sheet of paper for your answers!** Many of these exercises are programming exercises, but you do not need to submit them electronically. Everything should be submitted in one packet, all printed out for me to see.

Write a function `(print-reverse L)`

that takes a list `L`

and prints its elements in reverse, one per line, and then returns `(void)`

.

For example, calling `(print-reverse '(1 2 3))`

should print

```
3
2
1
```

Write a function `(print-height inches)`

that takes a number of inches and prints the feet and inches nicely. For example, calling `(print-height 70)`

should cause the following to be printed:

`5 feet 10 inches`

Once this works, make it nicer so that, for example `(print-height 73)`

prints

`6 feet 1 inch`

(notice not inches) and `(print-height 8)`

just prints

`8 inches`

and any other cases which seem sensible to you.

A certain sports team scores points in varying increments (2, 3, 6, 7), and after each score, certain fans must perform a number of push-ups corresponding to the total score at that time.

Write a function `(pushups points)`

that takes the points from the most recent score, and returns the total amount of push-ups that must be performed at that time. (You will have to use mutation!)

For example, if we start with `(pushups 3)`

, the returned value is 3. But if the next call is `(pushups 7)`

, the returned value is 10, since that is the total score at that point.

Using your `pushups`

function from the last exercise, write a function `(total-pushups L)`

that takes a list of scores `L`

and returns the total number of pushups performed.

There are a number of ways you could write this, but I want you to do it by using your `pushups`

function from the last exercise, along with `map`

and `apply`

.

For example, `(total-pushups '(3 7))`

should return 13, but `(total-pushups '(7 3))`

should return 17.

In class we showed two versions of the Fibonacci function:

(define (fib n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2)))))

and the memoized version:

(define fib-hash (make-hash)) (define (fib-memo n) (cond [(not (hash-has-key? fib-hash n)) (hash-set! fib-hash n (if (<= n 1) n (+ (fib-memo (- n 1)) (fib-memo (- n 2)))))]) (hash-ref fib-hash n))

I want you to count how many times each of these functions is called recursively in order to compute the 30'th Fibonacci number. Create two global variables `fib-count`

and `fib-memo-count`

, each initialized to 0, and an instruction in each of the `fib`

function and the `fib-memo`

function to increment this counter (increase by 1) every time the function is called.

Tell me how many times `fib`

is called recursively to compute `(fib 30)`

, and how many times `fib-memo`

is called recursively to compute `(fib-memo 30)`

.

Write new definitions for the following two functions from Homework 2 so that they are tail-recursive:

- Write a recursive function
`split-digits`

that takes a number`n`

and returns a list with the digits of`n`

, in reverse. - Write a function called
`count-down`

which takes a positive integer`n`

and produces a list with the integers from`n`

down to`1`

, in that order.