Study Guides (247,932)
Canada (121,168)
CS 115 (14)


5 Pages
Unlock Document

Computer Science
CS 115
Sandy Graham

CS 115 FINAL EXAM REVIEW MODULE 7: TREES Phylogenetic Trees - Phylogenetic tree: data structure recording information about evolution of species - Two kinds of information: modern species and ancient ancestors of modern species - Speciation event: leads to splitting of one species into two distinct species - Taxon: a t-modern or a t-ancient (define-struct t-modern (name pop)) (define-struct t-ancient (name age left right)) - T-modern: structure (make-t-modern n p), where n is string and p is number - T-ancient: structure (make-t-ancient n a l r), where n is string, a is number, and l and r are taxons Templates for t-modern and t-ancient: ;; my-taxon-fun: taxon  any (define (my-taxon-fun t) (cond [(t-modern? t) … ] … (t-modern-name t) … … (t-modern-pop t) … [(t-ancient? t) …] … (t-ancient-name t)… … (t-ancient-age t) … … (my-taxon-fun (t-ancient-left t)) … … (my-taxon-fun (t-ancient-right t)) … ])) Binary Search Trees (define-struct node (key val left right)) A bst (binary search tree, or BST) is either empty or a structure (make-node k v l r), where k is a number, v is a string, and l and r are bsts. - Keys in the left are all less than k - Keys in the right are all greater than k A BST Template: ;; my-bst-fun: bst  any (define (my-bst-fun t) (cond [(empty? abst) 0] [else … (node-key t) … … Inode-val t) … … (my-bst-fun (node-left t)) … … (my-bst-fun (node-right t)) … ])) General S-Expressions - An sexp is either empty, or it is (cons s1 s2), where s1 and s2 are both sexps, or it is (cons v s), where v is not a cons and s is an sexp. - S-expressions have a natural interpretation as leaf- labelled tree Template for S-Expressions (define (my-sexp-fun s) (cond [(empty? s) … ] [[cons? (first s)) … (my-sexp-fun (first s)) … … (my-sexp-fun (rest s)) …] [else … (first s) … (my-sexp-fun (rest s)) … ])) MODULE 8: MORE COMPLEX STRUCTURAL RECURSION General list template: (define (my-list-fun alist) (cond [(empty? list) … ] [else … (first alist) … … (my-list-fun (rest alist)) … ])) More complicated list template: (define (my-alongofrride-fun list1 list2) (cond [(empty? list1) … ] [else … (first list1) … … (my-alongforride-fun (rest list1) list2) … ])) Condensed Trace of total-value (total-value (cons 2 (cons 3 empty)) (cons 4 (cons 5 empty))) => (+8 (total-value (cons 3 empty) (cons 5 empty)) => (+8 (+ 15 (total-value empty empty))) => (+ 8 (+ 15 0)) => 23 M
More Less

Related notes for CS 115

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.