diff options
| -rw-r--r-- | coding-exercises/2/59.rkt | 1 | ||||
| -rw-r--r-- | coding-exercises/2/60.rkt | 2 | ||||
| -rw-r--r-- | coding-exercises/2/61.rkt | 14 | ||||
| -rw-r--r-- | coding-exercises/2/62.rkt | 15 | ||||
| -rw-r--r-- | coding-exercises/2/63.rkt | 102 | ||||
| -rw-r--r-- | coding-exercises/2/64.rkt | 20 |
6 files changed, 152 insertions, 2 deletions
diff --git a/coding-exercises/2/59.rkt b/coding-exercises/2/59.rkt index 2b10a66..e5f3289 100644 --- a/coding-exercises/2/59.rkt +++ b/coding-exercises/2/59.rkt @@ -24,6 +24,5 @@ ((not (element-of-set? (car set1) set2)) (cons (car set1) (union-set (cdr set1) set2))) - (else (union-set (cdr set1) set2)))) (union-set (list 1 2 3) (list 2 3 'c)) diff --git a/coding-exercises/2/60.rkt b/coding-exercises/2/60.rkt index 87eb7be..3effe1c 100644 --- a/coding-exercises/2/60.rkt +++ b/coding-exercises/2/60.rkt @@ -18,7 +18,7 @@ (define (intersection-set set1 set2) (define (iter s1 s2 result) (cond ((or (null? s1) (null? s2)) result) - ((and + ((and (not (element-of-set? (car s1) result)) (element-of-set? (car s1) s2)) (iter (cdr s1) s2 (cons (car s1) result))) diff --git a/coding-exercises/2/61.rkt b/coding-exercises/2/61.rkt new file mode 100644 index 0000000..71d773d --- /dev/null +++ b/coding-exercises/2/61.rkt @@ -0,0 +1,14 @@ +#lang racket + +;; linear scan required for this one, but on average we save some time because sometimes we can quickly +;; adjoin small values and other times a full linear scan is required to add a high value. +(define (adjoin-set x myset) + (cond ((null? myset) (cons x '())) + ((= (car myset) x) myset) + ((> (car myset) x) (cons x myset)) + (else (cons (car myset) + (adjoin-set x (cdr myset)))))) + +(define test-set (list 1 2 3 4 5 7)) +(adjoin-set 6 test-set) +(adjoin-set 8 test-set) diff --git a/coding-exercises/2/62.rkt b/coding-exercises/2/62.rkt new file mode 100644 index 0000000..705dcbd --- /dev/null +++ b/coding-exercises/2/62.rkt @@ -0,0 +1,15 @@ +#lang racket + +;; In each branch of the problem we either terminate the process or we reduce the problem to a subproblem with set - (car set) +(define (union-set set1 set2) + (cond ((and (null? set1) (null? set2)) '()) + ((null? set1) (cons (car set2) (union-set set1 (cdr set2)))) + ((null? set2) (cons (car set1) (union-set (cdr set1) set2))) + ((= (car set1) (car set2)) (cons (car set2) (union-set (cdr set1) (cdr set2)))) + ((> (car set1) (car set2)) (cons (car set2) (union-set set1 (cdr set2)))) + ((< (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) set2))))) + +(define test-list (list 1 2)) +(define test-list2 (list 4 5 6 7)) +(union-set test-list test-list2) + diff --git a/coding-exercises/2/63.rkt b/coding-exercises/2/63.rkt new file mode 100644 index 0000000..6a8fd88 --- /dev/null +++ b/coding-exercises/2/63.rkt @@ -0,0 +1,102 @@ +#lang racket + +(define (entry tree) (car tree)) +(define (left-branch tree) (cadr tree)) +(define (right-branch tree) (caddr tree)) +(define (make-entry entry left right) + (list entry left right)) + +(define (element-of-set? x mset) + (cond ((null? mset) false) + ((= x (entry mset)) true) + ((> x (entry mset)) + (element-of-set? (right-branch mset))) + ((< x (entry mset)) + (element-of-set? (left-branch mset))))) + +(define (adjoin-set x mset) + (cond ((null? mset) (make-tree x '() '())) + ((= x (entry mset)) mset) + ((< x (entry mset)) + (make-tree + (entry mset) + (adjoin-set x (left-branch mset)) + (right-branch mset))) + ((> x (entry)) + (make-tree + (entry mset) + (left-branch mset) + (adjoin-set x (right-branch mset)))))) + +(define (tree->list-1 tree) + (if (null? tree) + '() + (append (tree->list-1 (left-branch tree)) + (cons (entry tree) + (tree->list-1 (right-branch tree)))))) + +(define (tree->list-2 tree) + (define (copy-to-list tree result-list) + (if (null? tree) + result-list + (copy-to-list (left-branch tree) + (cons (entry tree) + (copy-to-list (right-branch tree) + result-list))))) + (copy-to-list tree '())) + + +;; depth of a balanced tree with n elements is log n.. right? Because every level you need 2*(level-1) elements, so the total levels is how many time we can do that step until 2*levels > n. +;; So it is the log a where a is the smallest number that only has factor 2 and > n. +;; Both procedure 1 and 2 are levelwise reducing the problem. +;; Only the overhead spent at each level is greater for 1, because append is used in the linear recursive process. +;; Since at every level we do a linear scan of all left elements, it is n*logn. +;; 1 is a linear iterative procedure and has almost no overhead at every level except a cons operation so it is logn. +((lambda () + (define test216a (make-entry + 7 + (make-entry + 3 + (make-entry + 1 '() '()) + (make-entry 5 '() '())) + + (make-entry + 9 + '() + (make-entry + 11 + '() + '())))) + (println (tree->list-1 test216a)) + (println (tree->list-2 test216a)) + (newline) + (define test216b (make-entry + 3 + (make-entry 1 '() '()) + (make-entry + 7 + (make-entry 5 '() '()) + (make-entry + 9 + '() + (make-entry + 11 + '() + '()))))) + (println (tree->list-1 test216b)) + (println (tree->list-2 test216b)) + (newline) + (define test216c (make-entry + 5 + (make-entry 3 (make-entry 1 '() '()) '()) + (make-entry + 9 + (make-entry 7 '() '()) + (make-entry + 11 + '() + '())))) + (println (tree->list-1 test216c)) + (println (tree->list-2 test216c)) + (newline))) diff --git a/coding-exercises/2/64.rkt b/coding-exercises/2/64.rkt new file mode 100644 index 0000000..90994e8 --- /dev/null +++ b/coding-exercises/2/64.rkt @@ -0,0 +1,20 @@ +#lang racket +(define (list->tree elements) + (car (partial-tree elements (length elements)))) + +(define (partial-tree elts n) + (if (= n 0) + (let ((left-size (quotient (- n 1) + 2))) + (let ((left-result (partial-tree elts left-size))) + (let ((left-tree (car left-result)) + (non-left-elts (cdr left-result)) + (right-size (- n (+ left-size 1)))) + + (let ((this-entry (car non-left-elts)) + (right-result (partial-tree (cdr non-left-elts) + right-size))) + (let ((right-tree (car right-result)) + (remaining-elts (cdr right-result))) + (cons (make-tree thientry left-tree right-tree) + remaining-elts)))))))) |