Homework 4

Language: Beginning Student with List Abbreviations

1 Binary Search Trees

Do exercise 14.2.3 from HtDP.

2 Tail-Recursive Function

Consider the following function for summing the elements of a list:

(define (sum-list l)
  (cond
    [(empty? l) 0]
    [else (+ (first l) (sum-list (rest l)))]))

Write a tail-recursive version of this function (you may use an auxiliary function).

3 Sorted Lists

; A sorted-list is either
; - empty
; - (cons number[n] sorted-list[l])
; INVARIANT: each number in ‘l’ is larger than ‘n’

Write the following function:

; in? : sorted-list number -> boolean
; determines if ‘n’ is in ‘l’
(define (in? l n) ---)

You must exploit the sorted-list invariant.

4 Heap

; A heap is either
; - false
; - (make-node number[n] heap[l] heap[r])
; INVARIANT: each number in ‘l’ is larger than ‘n’
; INVARIANT: each number in ‘r’ is larger than ‘n’

Write the following functions:

; in-heap? : heap number -> boolean
; determines if ‘n’ is in ‘h’
(define (in-heap? h n) ---)

; insert-in-heap : heap number -> heap
; constructs a new heap that contains
; all of the numbers in ‘h’, plus ‘n’
(define (insert-in-heap h n) ---)

You must exploit/maintain the heap invariant in each function (as appropriate).