[plt-scheme] HtDP exercise 29.1.1 | I don't understand ART.

From: Horace Dynamite (horace.dynamite at googlemail.com)
Date: Tue Jun 1 11:09:33 EDT 2010

If posting my answer to this problem violates the rules, I'm sorry,
please delete my mail; I can't explain myself properly without posting
it.

My answer to "What is the abstract running time?" is N. But this
doesn't agree with my intuition, since I believe this procedure to
have a faster growth rate than contains-doll?

I have the following data definition for a number tree,
;; exercise 29.1.1
; A number tree (short: nt) is either,
; 1. a number; or
; 2. (list nt nt)

Therefore, I have the following template,

(define (fun-for-nt ant)
  (cond [(number? ant) ...]
           [else ... (fun-for-nt (first ant)) ....
                   ... (fun-for-nt (first (rest ant))) ...]))

Filling in the blanks for sum-tree, I obtain,

;; sum-tree : nt -> number
;; To compute the sum of all the numbers in a number tree
(define (sum-tree ant)
  (cond [(number? ant) ant]
        [else (+ (sum-tree (first ant))
                 (sum-tree (first (rest ant))))]))
;; examples
(check-expect (sum-tree 0) 0)
(check-expect (sum-tree 5) 5)
(check-expect (sum-tree (list 1 9)) 10)
(check-expect (sum-tree (list (list 3 4) 2)) 9)
(check-expect (sum-tree (list 7 (list 12 8))) 27)
(check-expect (sum-tree (list (list 1 5) (list 6 7))) 19)

So, I should measure the size of a number tree by the number of LISTs
it contains, since on meeting a LIST, I have to recur twice.

Therefore, for a number tree containing N (nested) LISTs, I have at
worst 2*N recursions to execute. But due to the discussion in the
text, I can fudge the constant 2 and say this has on the order of N
steps. Is all this correct? I think not. Can someone help me with
this?

Thanks for your time,

Horace.


Posted on the users mailing list.