Study Guides
(238,455)

Canada
(115,142)

University of Waterloo
(5,557)

Computer Science
(327)

CS 115
(13)

Final

# CS 115 Final Exam Review Package- General

Unlock Document

University of Waterloo

Computer Science

CS 115

Barry Mc Clinchey

Fall

Description

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