1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
 2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
 3 12687dd9 2023-08-04 jrmu #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |29.1|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
 4 12687dd9 2023-08-04 jrmu ;Exercise 29.1.1.   A number tree is either a number or a pair of number trees. Develop the function sum-tree, which determines the sum of the numbers in a tree. How should we measure the size of a tree? What is its abstract running time?    Solution
 5 12687dd9 2023-08-04 jrmu ;
 6 12687dd9 2023-08-04 jrmu ;Exercise 29.1.2.   Hand-evaluate (maxi2 (list 0 1 2 3)) in a manner similar to our evaluation of (maxi (list 0 1 2 3)). What is the abstract running time of maxi2?    Solution
 7 12687dd9 2023-08-04 jrmu ;
 8 12687dd9 2023-08-04 jrmu ;A number tree (nt) is either
 9 12687dd9 2023-08-04 jrmu ;1. a number or
10 12687dd9 2023-08-04 jrmu ;2. (make-tree nt1 nt2)
11 12687dd9 2023-08-04 jrmu ;where nt1 and nt2 are number trees.
12 12687dd9 2023-08-04 jrmu 
13 12687dd9 2023-08-04 jrmu (define-struct tree (left right))
14 12687dd9 2023-08-04 jrmu 
15 12687dd9 2023-08-04 jrmu ;sum-tree : nt -> number
16 12687dd9 2023-08-04 jrmu ;Sums all the numbers in a number tree.
17 12687dd9 2023-08-04 jrmu (define (sum-tree ant)
18 12687dd9 2023-08-04 jrmu   (cond
19 12687dd9 2023-08-04 jrmu     [(number? ant) ant]
20 12687dd9 2023-08-04 jrmu     [else (+ (sum-tree (tree-left ant))
21 12687dd9 2023-08-04 jrmu              (sum-tree (tree-right ant)))]))
22 12687dd9 2023-08-04 jrmu 
23 12687dd9 2023-08-04 jrmu (define tree1 (make-tree (make-tree (make-tree 4 9)
24 12687dd9 2023-08-04 jrmu                                     (make-tree 2 7))
25 12687dd9 2023-08-04 jrmu                          (make-tree 5 -3)))
26 12687dd9 2023-08-04 jrmu 
27 12687dd9 2023-08-04 jrmu (sum-tree tree1)
28 12687dd9 2023-08-04 jrmu 
29 12687dd9 2023-08-04 jrmu The size of a tree can be measured either by the number of nested trees it contains or by the length of the most nested tree. (if so, then the running time is on the order of N) I prefer the first since its definition allows easier calculation of the abstract running time.  Or it could be considered the number of numbers (on the order of N?).
30 12687dd9 2023-08-04 jrmu 
31 12687dd9 2023-08-04 jrmu (+ (sum-tree (tree-left ant))
32 12687dd9 2023-08-04 jrmu    (sum-tree (tree-right ant)))
33 12687dd9 2023-08-04 jrmu 
34 12687dd9 2023-08-04 jrmu (+ (+ (sum-tree (tree-left ant))
35 12687dd9 2023-08-04 jrmu       (sum-tree (tree-right ant)))
36 12687dd9 2023-08-04 jrmu    (sum-tree (tree-right ant)))