CSci 1301: Problem Set 9

Due: Monday, November 22 at 11:59pm by e-mail

As always, please include a contract, a purpose, examples, and tests for each function.

Problem 1 (6 points)

Exercise 21.1.1. Instead of (sub1 n) just write (- n 1). Make sure to write a contract for your general function.

Problem 2 (6 points)

Exercise 21.2.1 parts 1, 2, 3 only. Make sure to test your functions, submit your tests.

Below is an example of using build-list to produce the squares of the first 10 integer numbers. build-list takes a number of elements it needs to produce and a function from an integer n to the n-th element on the list, e.g. n -> square(n).

(define (square n) (* n n))

(build-list 10 square)

Problem 3 (5 points)

Write a function standard-dev that consumes a list of ummstudent records defined in the in-class example and computes their standard deviation according to the formula at http://en.wikipedia.org/wiki/Standard_deviation#Discrete_random_variable_or_data_set . Use any combination of the predefined list functions (map, foldr, etc).

Problem 4 (7 points)

Write a function map-tree that takes a function and a tree and "maps" the function over the tree. We change the definition of a tree node slightly to simplify the task by making just one data field instead of separate ssn and name fields:

;; a node of a binary tree
;; data contains data in the node (can be any datatype).
;; left and right are nodes for left and right subtree
(define-struct node (data left right))

;; define a sample tree
(define mytree
(make-node
     63
     (make-node 29  (make-node 15  (make-node 10  false false) 
                                       (make-node 24 false false)) 
                      false)
     (make-node 89 false false)))

The map-tree function takes a function that works on node data and a tree and returns a new tree made of the elements that result from applying the function to each element of the tree. Below are sample runs (you might want to draw the resulting trees for a better understanding):

(define (add-2 x)
  (+ x 2))

(map-tree add-2 mytree)

(map-tree even? mytree)

The results of the above calls:

(make-node
 65
 (make-node 31 (make-node 17 (make-node 12 false false) (make-node 26 false false)) false)
 (make-node 91 false false))


(make-node
 false
 (make-node false (make-node false (make-node true false false) (make-node true false false)) false)
 (make-node false false false))

Write the contract for map-tree, and then write and test the function itself.

Problem 5 (6 points)

Change the function fold-tree that we wrote in class to process a tree using inorder traveral (left subtree, root, right subtree). Show one example of using fold-tree that produces different results for the preorder and inorder tree traversal and one example in which the result doesn't depend on the order (use examples different from what we did in class on Monday).

Below is the in-class solution for fold-tree:

;; a node of a binary tree
;; data contains data in the node (can be any datatype).
;; left and right are nodes for left and right subtree
(define-struct node (data left right))

;; define a sample tree
(define mytree
(make-node
     63
     (make-node 29  (make-node 15  (make-node 10  false false) 
                                       (make-node 24 false false)) 
                      false)
     (make-node 89 false false)))


(define (fold-tree seed node-function combine a-tree)
  (cond
    [(false? a-tree) seed]
    [else (combine(node-function a-tree)
                  (fold-tree seed node-function combine (node-left a-tree))
                  (fold-tree seed node-function combine (node-right a-tree)))]))


(fold-tree 0 node-data + mytree)                   

CSci 1301 course web site.