Study Guides (238,455)
Canada (115,142)
CS 115 (13)

CS 115 Final Exam Review Package- General

16 Pages
Unlock Document

University of Waterloo
Computer Science
CS 115
Barry Mc Clinchey

CS 115 Final Exam Review Sheet Module 1 Programming languages: Imperative: Frequent changes to data ( C++, Java, Python) Functional: computation of new value, not transformations of old ones ( R,XSLT, etc) Function Definitions Consist of:  Name ( f)  Parameters( x,y)  Mathematical Expressions( f( x, y)= x +y ) A function application: supplies arguments for the parameters. Math expression is evaluated by substitution. Scheme follows BEDMAS! Prefix vs Infix Notation Prefix Notation: The operator comes before the operands ( ex + 2 3 ) Infix Notation : The operator is between the operands ( ex 2 +3 ) Important observations: You can change the name of the parameters, does not change anything about the function 2 2  F(x)= x is the same as F(cookies)= cookies  Order of the arguments must be the same in the function. 2 2 2 2  Ex: f( x, y)= x +y must be in that order, cannot be f( y, x)= x +y Define : a special form ( not all arguments are evaluated), Binds a name to an expression Values: something that cannot be further simplified.  4 cannot be further simplified, therefore value  4+1 can be simplified to 5, so not value yet. Tracing: step by step simplification of a problem by applying substitution rules. Module 2 Comments: Important information to humans but ignored by the computer (starts with ;; in scheme) Code: Machine-readable code that is not commented. Design Recipe Contract, conditons, and function header : Pre and Post conditions of the function Purpose: What does the function do? Examples: Examples of the function Body: the major code of the function. Test: Multiple tests to see if the function works well as it should. In later Modules, Add: Template: For lists, see what you do in each of the cases. String : Anything between 2 “” Built-in functions for String: (string-append “cookies” “hi”) => “cookieshi” (substring “cookies” ( # of letter to start at *indexed at 0+) # of letter to go up to, but not include )  “CAKE” : (C 0) (A 1)(K 2)(E 3) -> ( Substring “cake” 0 2) => (C 0) (A 1)=> “CA” String-length : gets the length of the string  CAKE: (C 1) (A 2)(K 3)(E 4) => 4 letters => 4 Module 3 Boolean: Either true or false Boolean function (predicate) produces a Boolean Value. Comparison : a function that consumes 2 numbers and produces a Boolean.  ( > 3 1) => true, because 3 is greater than 1. Complex relationships: AND, NOT, OR ( these are special forms)  AND: all values must be true o Rules : ( and true exp )=> throw away the true, keep looking o If it gets to the end , then its true. o If it finds a false, then it is false.  OR: only 1 of the values needs to be true, all else can be false. o Rules: (or true exp) => gives insta true, as one of them is true o If it gets to the end, it produces false, as none of them where true. o If it gets to a false, throws it away and keeps looking.  NOT: Essentially, takes result and negates it. o NOT (AND true true) => NOT ( true) => False Predicates: A function that produces a Boolean answer. Usually start end with ?  Even? Checks to see if the given input is even. o (Even? 2) => true o (Even? 3)=> False Conditionals Uses special form called cond Each argument in this is a question, answer pair, and it must be a Boolean question.  Example : *(even? 2) “HI”+  There should always be 2. One should be a question answer pair, and the second is an else statement, that tells the program to do X if the previous question(s) are unsatisfied. Else prevents the programming from crashing.  Conds work like this, for stepping o If the question is true, then do the answer o If its false, throw both of them away, and continue down the list of Q & A. Testing Black-Box: based on the different cases. ( mostly just given examples) White-box : tests everything of your function, all possible combinations.  Clear box: you know what should be in the box, but you need to make sure it is. Symbol A symbol starts with a single ‘, such as ‘cookies Symbol vs String:  Strings are compound, so they are huge to process  Symbols are essentially values. General Predicates for equality testing:  Equal?/Eq? => checks if the 2 inputs are the same  Symbol=? => checks to see if 2 symbols are the same  String=? => checks to see if 2 strings are the same Structures You essentially bundle a bunch of data together. General call : (define-struct person name age height)  This gives you o Constructor: (make-person Martin “Martin” 19 190) o Selectors:  (person- name Martin) => “Martin”  (person- age Martin) => 19  (person- height Martin) => “190 o Predicate (person? cookies) => false. POSN struct : used to get the x and y postion. (make-posn 1 2) => this point is at : (1,2) (make-posn “Cookie” “Monster”)=> Dynamic Typing, so it will work, but wont evaluate.  Dynamic typing: the errors are only caught at run time. Design Recipie Addtions Data Definitions ;; A Person is a structure (make-person n a h) ;; Where: n is a String of the person`s name ;; a is a Nat which is their age. ;; h is an Int that is their height. Template (define (name of function dealing with a struct) ( arguments)) …(person- name Argument) …. …(person- age Argument) …. …(person- height Argument) …. Module 5 : Lists Data Definitons of lists: A list is either:  Empty or  (Cons l alist ), where o L is a value , and o Alist is a list Example of A list (define (my-length alist) (cond  Conditional opening [(empty? alist) 0]  Base case ( in this case, we want to add 0 when it gets to the end) [else (+ 1 (my-length (rest alist))) ])) recursive case( add 1, and then go through the remaining list. First and Rest: Name: hi (list 1 2 3 4 ) or (cons 1 (cons 2 (cons 3( cons 4)))) (first hi) => 1 , (first (rest hi)) => 2( rest(rest hi))=>(list 3 4) Structural recursion: when the recursion matches the form of data . Additions to Design Recipe: List Templates Essentailly, this asks “what am I doing at each step?” Questions  What do I do in the base case?  What do I do with the first of the list  What do I do on the recursive call? (define (my-length alist) (cond *(empty? alist) ….+ *else (… (my-length (rest alist))) ])) Module 6 To add 1 : (add1 Num) To sub1 : (sub1 Num) Function Insert and Sort Insert (define (insert n alon) (cond  condition opener [(empty? alon) (cons n empty)] if its empty, end the list with the number [else (cond  If its not empty, there are 2 cases. [(<= n (first alon)) (cons n alon)]  if the first number is greater than n, put n before the number [else (cons (first alon) (insert n(rest alon)))]  if its not, just recurse again, putting the first number. )])) Sort (define (sort alon) (cond [(empty? Alon) empty]  Empty? Then just stop [else (insert (first alon)(sort(rest alon)))])) else, run insert on the function Association Lists These are lists that go in the following order:  Either they are Empty,
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.