Study Guides (238,095)
Canada (114,916)
CS 115 (13)
Tian Kou (1)

CS 115 Final Review Sheet

10 Pages
Unlock Document

University of Waterloo
Computer Science
CS 115
Tian Kou

Computer Science 115 – SOS Final Exam Review Tutor: Jumana Bahrainwala ([email protected]) Coordinator: Erin Vanderstoep ([email protected]) STRUCTURES • A structure bundles data in a package together • Serves as a useful way to refer to data you define • Defining a structure is the first step (they usually do this for you) • Gives three useful functions Note: The contract should have the name of the structure rather than “structure” To define a structure: (define-struct sname (field1 field2.....)) Doing this gives you three functions: make-sname ;constructor sname-field1, sname-field2.... ;selectors sname? ;type predicate o Basically this is saying that you have created a structure called "sname" that has properties defined in f1....fn Structure Template (define (function-name a-struct) ... (structure-f1 a-struct)... ... (structure-f2 a-struct)... ... ... (structure-fn a-struct)...) A Data Definition: is a comment specifying the types of data ;;a posn in a structure (make-posn xcoord ycoord), where ;;xcoord is a number ;;ycoord is a number Structure Definitions: show what each item represents (define-struct contact (name email_address)) ;; A contact is a structure (make-contact n e) where ;; n is a non‐empty string representing a person's name and ;; e is a non‐empty string representing a person's email address.   1   Computer Science 115 – SOS Final Exam Review LISTS Formal Definition A list is either: • empty or • (cons f r), where f is a value and r is a list Examples of Lists in Scheme: => (cons ‘a (cons ‘b (cons ‘c (cons ‘d empty)))) => empty => (list ‘a ‘b ‘c ‘c) List Template (define (mylist alist) (cond [(empty? alist)...] [(cons? alist) ...])) Difference between Structures and Lists: • Structures are easier to select data • Lists are better for recursion INTRODUCTION TO RECURSION Base Case: The starting and ending point of the function. The first thing that the function checks in an “if” case. Function stops recursing when the base case is true. Recursive Part: Only if your base case fails. Ask “What do you want to change if your base case fails?” Keep doing this until your base case passes. A general recursive template (define (my-recurse int) Defining Base Case (cond [(base-case? int) ...] [else ...... (my-recurse ......)])) Store/Alter the variable Re-apply function on the changed variable   2   Computer Science 115 – SOS Final Exam Review Problem 1 Give the structure templates for the following structures. Then, define a function that consumes a list of CD structures and produces the total price, using the template for CD. (define-struct movie (title producer)) (define-struct CD (artist title price)) Solution (define (my-movie-fn a-movie) ...(movie-title a-movie)... ...(movie-producer a-movie)...) (define (my-CD-fn a-CD) ...(CD-artist a-CD)... ...(CD-title a-CD)... ...(CD-price a-CD)...) (define (total-price aloCD) (cond [(empty? aloCD) 0] [else (+ (CD-price (first aloCD)) (total-price (rest aloCD)))])) ___________________________________________________________________________ :: why did we choose this particular base case? We want the function to stop once we have added up ALL the prices. So we need to keep going until the list is empty. When it is empty, we aren't adding any price, so just add 0 to our price total. :: Or you can think about it another way. If we had an empty list in there, there would be no prices to add, and our total price is zero. LIST OF LISTS   3   Computer Science 115 – SOS Final Exam Review List of List Template (define (my-list-fn a-list) (cond ((empty? a-list) ...) ((cons? (first a-list)) ...) (else ...(first a-list)...(my-list-fn (rest a-list))))) Dictionaries/Association Lists o Each List contains smaller lists, with each smaller list having two elements o One represents a key, and other represents the value corresponding to the key o An al is either empty or (cons (list k v) alst) where k is a number (key), v is a string (value) and alst is a list o (list (list 5 a) (list 6 jumana) (list 19 computers)) Problem 2 Consume an association list and a key and find the value that corresponds to that key, or return false if the key is not found. Solution (define (find-val al k) (cond [(empty? al) false] [(= (first (first al)) k) (second (first al))] [else (find-val (rest al) k)])) PROCESSING TWO LISTS Three Methods for Processing Two Lists 1. Have a list “go along for the ride” 2. Processing in Lockstep (only for lists of equal lengths) 3. Processing Lists at Different Rates   4   Computer Science 115 – SOS Final Exam Review Each type of problem is described below: Lockstep Template (define (my-list-fn lst1 lst2) (cond [(empty? lst1) ...] [else ... (first lst1) ... (first lst2)... ... (my-lst-fn (rest lst1) (rest lst2))])) Different Rates Template (define (my-lst-fn lst1 lst2) (cond [(and (empty? lst1) (empty? lst2)) ...] [(and (cons? lst1) (empty? lst2)) ...] [(and (empty? lst1) (cons? lst2)) ...] [(and (cons? lst1) (cons? lst2)) ...])) Problem 3 Develop a function, cross, that consumes a list of symbols and a list of numbers and produces all possible pairs of symbols and numbers. Solution (cross (list 'a 'b 'c) (list 1 2)) => (list (list 'a 1) (list 'a 2) (list 'b 1) (list 'b 2) (list 'c 1) (list 'c 2)) (define (cross-helper
More Less

Related notes for CS 115

Log In


Don't have an account?

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.