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

CS 115 FINAL EXAM REVIEW.docx

5 Pages
806 Views
Unlock Document

Department
Computer Science
Course
CS 115
Professor
Sandy Graham
Semester
Winter

Description
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


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit