Abstract run times (HTDP)

[Sean Kemplay]

Hi all,

I trying to work out the ART of the sum-tree question from HTDP2e.

I have worked through the book before however am going through it again, this time am doing every exercise - this is not homework!

Here is my data defenitions, examples, a function ror summing up the contents and tests -

; A Pair is a list of two items

; A Number-Tree is one of:
; Number
; [Pair-of Number-Tree]
; Examples -
; 0
; (list 0 1)
; (list (list 1 2) 3)
; (list (list 1 2) (list 3  4))
; (list (list (list 1 2) (list 3 4)) (list (list 5 6) (list 7 8)))
; (list (list (list (list (list (list (list 8 7) 6 ) 5) 4) 3) 2) 1)

; Number-Tree -> Number
; Sum up all numbers in nt
(check-expect (sum-list 0) 0)
(check-expect (sum-list (list 1 2)) 3)
(check-expect (sum-list (list (list 1 2) (list 3  4))) 10)
(check-expect (sum-list(list (list (list 1 2) (list 3 4)) (list (list 5 6) (list 7 8)))) 36)
(check-expect (sum-list (list (list (list (list (list (list (list 8 7) 6 ) 5) 4) 3) 2) 1)) 36)
(define (sum-list nt)
  (cond [(number? nt) nt]
        [else (+ (sum-list (first nt))
                 (sum-list (second nt)))]))

Using a balanced tree my analysis shows an ART of n^2 to run sum-list where n is the depth of the tree

(sum-list(list (list (list 1 2) (list 3 4)) (list (list 5 6) (list 7 8))))

Using avery unbalanced tree with all nodesheading down to the left my analysis shows an ART of 2n - or just n when the constant is removed.

(sum-list (list (list (list (list (list (list (list 8 7) 6 ) 5) 4) 3) 2) 1))

So the unbalanced tree in this case where all nodes need to be visited would be better?

A BST a search function would be better with a balanced tree but not sum-tree?

Could someone possibly comment whether I am on the right track here?

Kind regards,

Sean

[Matthias Felleisen]

Equally good.

> A BST a search function would be better with a balanced tree but not sum-tree?

Yes.

> Could someone possibly comment whether I am on the right track here?

Good job.

[Sean Kemplay]

Thanks Matthias, I think I have it now, much appreciated.

On Friday, May 24, 2019 at 2:24:57 PM UTC+1, Matthias Felleisen wrote: