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: F_n = F_n-1 + F_n-2, with seed values F₀ = 0 and F₁ = 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 F₀ to F_n.

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.