Exercises

Exercise 4.1.   [*] Develop the function random-interval. It consumes a number (MIN) and produces an interval:

(define-struct interval (left right))
;; An Interval is: 
;; --- (make-interval L R)
;; if (< L R) is true

The function returns an interval whose distance is less than MIN. 

Exercise 4.2.   [*] Assume DrScheme’s Definitions Window contains the definition for a mathematically continuous function f:

;; f : Number  →  Number
(define (f x) ...)

Just a reminder: continuous means for us “has no gaps.”

Design the function find0, which consumes an interval and determines a small interval (smaller than 1.0) where some top-level function f from Number to Number crosses the x-axis in this interval.

Hint 1: If f values at the two ends of the interval are at opposite sides of the x-axis, f is 0 somewhere in between. Take a look at the middle of the interval.

Hint 2: Your problem and data analysis may benefit from drawing a picture.

Note: The solution of this problem is the basis of binary search in vectors and similar data structures. 

Exercise 4.3.   (*) Develop a program that draw nested circles like these:

Hint: Use the following picture to figure out the mathematics for finding the center of the next nested circle:

Exercise 4.4.   Develop the function merge-sort, which sorts a list of numbers in ascending order using the following insight.

1. Construct a list of one-item lists from the given list of numbers. For example,

   (list 2 5 9 3)
   turns into 
   (list (list 2) (list 5) (list 9) (list 3))
   

2. Merge pairs of neighboring, sorted lists in the list of list so that the result is sorted. For example,

   (list (list 2) (list 5) (list 9) (list 3))
   turns into 
   (list (list 2 5) (list 3 9))
   and
   (list (list 2 5) (list 3 9))
   turns into 
   (list (list 2 3 5 9))
   

   In general, this step yields a list that is approximately half as long as the input. Why is the output not always half as long as the input?

3. Stop when the list of lists contains a single list. For example, for the above starting point, we should get

   (list (list 2 3 5 9))
   

Develop all necessary functions independently.