Teaching 2500 F '12 Assignments The Hand In Set 1 Set 2 Set 3 Set 3h Set 4 Set 4h Set 5 Set 5h Set 6 Set 6h Set 7 Set 7h Set 8 Set 9 Set 8h Set 10 Set 9h Set 11 Set 12 Set 10h

### Problem Set 12

Due date: 12/3 @ 11:59pm

Programming Language: Intermediate Student Language with lambda

### Final HW Assignment

The goal of this problem set is to practice the design of generative recursive functions and accumulator-style functions.

Problem A1:

A number, n>1, is prime if it is not divisible by any numbers besides 1 and itself, such as 2, 3, 5 and 7.

#### Part 1:

Design the function `prime?` which consumes a Natural Number and returns true if it is prime and false otherwise. Use the fact that if n is not prime, one if its factors must be less than or equal to the square root of n.

#### Part 2:

Design the function `list-primes` which consumes a Natural Number, n, and produces the list of prime numbers up to n.

Problem A2:

A palindrome is a word, number or phrase that reads the same forward and backward.

#### Part 1:

Design the function `make-palindrome`, which consumes a non-empty String and constructs a palindrome by mirroring the String around the last letter. For example, (`make-palindrome "fundies"`) should produce "fundieseidnuf".

#### Part 2:

Design the function `is-palindrome?`, which consumes a non-empty String and determines whether the String is a palindrome or not.

Problem A3:

The Fibonacci numbers, which are the numbers in the following sequence:

```    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
```
are defined by the recurrence relation: Fn = Fn-1 + Fn-2, with seed values F0 = 0 and F1 = 1. (See here for more about Fibonacci numbers.)

#### Part 1:

Design the function `fibonacci`, (without accumulators) which consumes a Natural Number and produces its Fibonacci number. For example, (`fibonacci 11`) should produce 89.

#### Part 2:

Use accumulators to design a more efficient version of `fibonacci`.

#### Part 3:

Design a function, `list-fibonacci`, that consumes a Natural Number and produces the list of Fibonacci numbers from F0 to Fn.

Problem A4:

Here is a data definition for binary trees that contain Strings at every node of the tree, not just the leaves.

```;; A WordTree is one of:
;; -String
;; -(make-node WordTree String WordTree)

(define-struct node (left word right))
```

Here are two examples of WordTrees:

```(define holidays (make-node
(make-node "Christmas" "Labor Day" "MLK Day")
"Patriots Day"
(make-node "Presidents Day" Thanksgiving" "Veterans Day")))
```
```(define movies (make-node
(make-node "Argo" "Flight" "Life of Pi")
"Lincoln"
"Skyfall"))
```

Notice that the two example trees are ordered alphabetically. A WordTree is ordered if:

• all of the strings in its left child alphabetically precede the node's word,
• all of the strings in its right child alphabetically succeed the node's word,
• and the left and right subtrees are both ordered.

#### Part 1:

Use structural recursion to design the function `word-in-tree?`, which consumes an ordered WordTree and a String and produces true if the String is in the tree and false otherwise.

#### Part 2:

Use generative recursion to design the more efficient function `word-in-tree?.gen`, which consumes an ordered WordTree and a String and produces true if the String is in the tree and false otherwise.

 last updated on Sun Dec 2 14:52:34 EST 2012 generated with Racket