CSE 1729 – Introduction to Principles of Programming October 25, 2016 Laboratory Assignment 8
Ob jectives
• Mergesort and binary trees Activities
1. mergesort works recursively by splitting its input in halves, sorting each half recursively using mergesort, and using merge to combine the two sorted halves. In English: if the list has zero or one element,you are done, otherwise split the list into 2 equal-sized sublists, sort each sublist, and merge them into a sorted result. Notice that unlike Quicksort there is no pivot: we split the list so the two parts are equal size (within 1) without regard to the values in the list.
You wrote the merge function in Problem Set 6. Feel free to use that code, or the code in the posted Problem Set 6 solutions.
(a) Write a function (split l) that takes a list and partitions it into two equal-sized (within one) lists, and returns a list whose first element is the first list and whose second element is the second list.
You can use the built-in length function if you would like, but it should not be called more than once (in total) during split.
Solution:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; (split lst) returns list (a b) such that a and b
;; are equal lengths and partition list lst (every element ;; of lst is in either or b but not both.
(define (split lst)
(define (split-iter lst a b) (if (null? lst)
(list a b)
(split-iter (cdr lst) b (cons (car lst) a)))) (split-iter lst ’() ’()))
;; non-iterative alternative using length
;; split2 is stable in that it maintains the order within the ;; which is unnecessary for merge sort, but sometimes good (define (split2 lst)
(define (first-n lst n) (if (= 0 n)
’()
(cons (car lst)(first-n (cdr lst) (- n 1)))))
1
list
(define (list-without-first-n lst n) (if (= 0 n)
lst
(list-without-first-n (cdr lst) (- n 1)))) (let ((half (round (/ (length lst) 2))))
(list (first-n lst half) (list-without-first-n lst half))))
(b) Using split and your merge function from last week (or the one in the solution to problem set 6), write a function (mergesort l) as described above that takes a list and returns it sorted in ascending order.
Solution:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; mergesort using merge from last week and
;; split above. Sorts a list in ascending
;; order. Note there is a base case for
;; single-element lists (Why?)
(define (mergesort l) (cond ((null? l) l)
((null? (cdr l)) l) (else
(let ((parts (split l)))
(merge (mergesort (car parts))
(mergesort (cadr parts)))))))
2
2. This question involves working with trees. Recall the conventions we have adopted in class for maintaining trees. We represent the empty tree with the empty list (); a nonempty tree is represented as a list of three objects
(value left-subtree right-subtree)
where value is the value stored at the root of the tree, and left-subtree and right-subtree are the two subtrees. We introduced some standardized functions for maintaining and accessing this structure, which you should use in your solutions below.
(define (make-tree value left right)
;; produces a tree with value at the root, and ;; left and right as its subtrees.
(list value left right))
(define (value tree) (car tree))
(define (left tree) (cadr tree))
(define (right tree) (caddr tree))
Notably, you will need to use these functions to produce some test trees to test the following functions. For example, to produce the simple tree in Figure 1, you could use the following code:
(define testtree (make-tree 1 (make-tree 3
(make-tree 7 ’() ’())
(make-tree 9 ’() ’())) (make-tree 5 ’() ’())))
You will probably want to make some more complex trees than that, but you get the idea.
Finally, for all of these, figure out how to define the function recursively, as that should map fairly directly to code.
(a) A non-empty tree is made up of nodes: the root, and all of the nodes in its subtrees. Define a Scheme procedure (tree-node-count t) that calculates the number of nodes in tree t. It should also work for empty trees. (tree-node-count testtree) would be 5.
Solution:
;; tree node counter — recursive on subtrees
(define (tree-node-count t) (if (null? t)
0
3
1
35
79
Figure 1: Tree testtree produced by code in question 2.
(b) The height of a node in a tree is the length of the longest path from that node to a leaf – we can consider the height of a tree to be the height of its root. The height of the empty tree is undefined, the height of a node without children (leaf) is 0, otherwise the height of a node is one more than the maximum height of the trees rooted at its children.
Define a Scheme procedure (tree-height t) that calculates the height of a non-empty tree t. testtree has height 2.
(+ 1
(tree-node-count (left t)) (tree-node-count (right t)))))
Solution:
;; tree-height — returns length of longest path ;; note: convenient bogus answer for empty tree
(define (tree-height t) (if (null? t)
-1 ;; ensure that a leaf has height 0 (+ 1 (max (tree-height (left t))
(tree-height (right t))))))
(c) Define a Scheme procedure, named (tree-map f t), which takes two parameters, a func- tion, f and a tree t, and is analogous to the map function for lists. Namely, it returns a new tree with a topology identical to that of t but where each node in the new tree has the value f(v), where v is the value at the corresponding position in t. For example, if the input tree is testtree shown in Figure 1 then the tree returned by (tree-map (lambda(x)(* 3
4
3
9 15
21 27
Figure 2: Tree resulting from mapping (lambda(x)(* x 3)) over testtree. x)) testtree) is shown in Figure 2.
Solution:
;; (tree-map tree f) — produces tree with same
;; structure, and values equal to f applied to values
;; in original tree
(define (tree-map f t) (if (null? t)
’()
(make-tree (f (value t))
(tree-map f (left t)) (tree-map f (right t)))))
5