CS 115 – SOS Review Package – Midterm.pdf

CS  115  –  SOS  Review  Package  –  Midterm     Dylan  Schnute  (Tutor)  –  [email protected]   Erin  Vanderstoep  (Coordinator)  –  [email protected]         DEFINING  FUNCTIONS   Similar  to  mathematics,  every  definition  of  a  function  has  three  main  components:   1. Name  of  the  function   2. Parameters  that  the  function  consumes   3. An  expression  that  uses  these  parameters     General  Format:   (define (function_name parameter1 parameter2 …)(function_expression)) Ex.   (define (f x) (* x x)) (define (g y z)(* (+ y z)(* y y)))   BUILT  IN  FUNCTIONS   (- 60 (* 5 5)(/ 45 5)(- 10 2))  ;  four  basic  math  functions  (+,   -­‐,  /,  *)   (quotient 70 8)  ;  gives  the  integer  value  when  dividing   (remainder 70 8)  ;  gives  the  remainder  when  dividing   (max 20 25)  ;  gives  the  maximum  of  a  group  of  numbers   (min 20 25)  ;  gives  the  minimum  of  a  group  of  numbers   (floor 20.8)  -­‐>  20   (ceiling 20.8)  -­‐>  21   (sqr 2)  -­‐>  4   (sqrt 4)  -­‐>  2     DEFINING  CONSTANTS   General  Format:   (define constant_name constant_value) Ex.    (define x 4) (define v (* 4 2 x))  ;  If  we  type  in  v,  we  would  get  32     Rules  when  defining  constants:   1. You  cannot  define  the  same  variable  name  twice:   (define x 4) (define x 5) 2. Scheme  keeps  track  of  variables.    Once  you  define   “x”,  you  can  use  the  definition  of  x  in  other  functions.   (define x 5) (define (y z) (* z y x))                 TRACING   A  step  by  step  simplification  of  a  scheme  function  by  applying  substitution  rules.   Remember  to  take  one  step  at  a  time.   Example  1:   1. (/ (+ 40 (* (min 5 6 9 3) 2)) 2) -> (/ (+ (* 3 2)) 2) -> (/ (+ 40 6) 2) -> (/ 46 2) -> 23 2. (define  (square  x  y)(+  (*  x  x)  (*  y  y)))   Using  the  above  definition,  trace:   (square (- 5 2) (* 3 4)) -> (square 3 (* 3 4)) -> (square 3 12) -> (+ (* 3 3) (* 12 12)) ;  substitute  all  parameters  into  the  function  at  once -> (+ 9 (* 12 12)) -> (+ 9 144) -> 153     THE  DESIGN  RECIPE   The  design  recipe  is  a  key  component  of  CS  115.    Particularly  on  midterms,  the  importance  of  the   design   recipe  can’t  be  undervalued,  and  can  result  in  a  lot  of  marks  for  you.     THE  CONTRACT   A  contract  is  a  simple  statement  of  the  function  name,  the  types  of  parameters  that  it  consumes  and  the  type  of   output.    You  are  telling  the  user  what  are  the  types  of  things  they  can  input  and  what  types  of  things  they  will   get  out  of  it.   Example   If  the  function  squarepower  takes  in  a  number  and  squares  it,  write:     ;; squarepower: num -> num Types  of  Numbers:   • num:  any  numeric  value   • int:  for  an  integer   • nat:  a  natural  number  (the  set  of  all  non -­‐negative  numbers)   • any:  any  scheme  value   • (int[>5]):  such  a  format  is  used  for  integers  with  given  restrictions     THE  PURPOSE   A  statement  that  describes  the  function,  its  parameters  (by  name)  and  what  the  function  should  prod     EXAMPLES   Provide  representations  of  all  the  possible  cases  and  outcomes  that  could  arise  with  the  function.     BODY   The  actual  code.     TESTING   (check-­‐expect  (function_name  sample_values)  expected_value)   If  your  function  output  and  the  expected  value  are   equal,  then  the  test  will  pass.    Scheme  will  tell  you  f  one  or   more  of  your  tests  have  passed  or  not.     Example  2:   Produce  a  function  called  sum_square  that  produces  the  sum  of  the  squares  of  any  two  real  numbers,  but  rounds   the  number  down  to  the  nearest  integer.   ;;sum_square: num num -> int ;;Purpose: the function consumes two numbers, a and b, produces the sum of the squares of these two numbers, rounded down to the nearest integer. ;;Examples: ;;(sum_square 2 4) -> 20 ;;(sum_square 3.4 6.3) -> 51 ;;(sum_square -5 6) -> 61   (define (sum_square a b) (floor (+ (* a a) (* b b)))) ;;Tests: (check-expect (sum_square 2 4) 20) (check-expect (sum_square 3.4 6.3) 51) (check-expect (sum_square -5 6) 61)   STRINGS   A  value  made  up  of  words,  letters,  numbers,  spaces,   and  punctuation  marks  that  are  enclosed  in  quotation   marks  (ex.  “computer”  “computers123”  “computer  science”  “sdalkfjhdf  34  jdhf  ) “Computer”   0    1    2      3    4    5    6    7       Built-­‐In  String  Functions:   (string-­‐append  “joe”  “clark”)  -­‐>  “joe  clark”   (string-­‐length  “joe  clark”)  -­‐>  9   (subtring  “computer”  0  4)  -­‐>  comp   (substring  “computer”  0  1)  -­‐>  “c”   (subtring  “computer”  1)  -­‐>  “omputer”   (string>?  “nowhere”  “here”)  -­‐>  true     HELPER  FUNCTION   A  helper  function  is  defined  before  the  main  function,  and  is  used  to  ge nerate  similar  expressions,  express   easy/repetitive  computations  in  clear  form,  and  to  avoid  really  long  complex  definitions.   • You  still  need  the  full  design  recipe  for  helper  functions   • Choose  meaningful  names  (not  just  helper1  etc.)     Example  3  (swap  parts):   Take  a  string  and  swap  the  front  of  the  string  with  the  back  of  it.    If  the  string  length  is  odd,  make  the  front   part  shorter.   ;;front_part: string -> string ;;Purpose: To take a string, str, and produce the front part of it ;;Examples: (front_part “comp uter”) -> “comp” ;;(front_part “compute”) -> “com” (define (front_part str) (substring str (floor (/ (string -length str) 2))))) ;;Tests: (check-expect (front_part “computer”) “comp”) (check-expect (front_part “compute”) “com”) ;;back_part: string -> string ;;Purpose: To take a string, str, and produce the back part of it ;;Examples: (back_part “computer”) -> “uter” ;;(back_part “compute”) -> “pute” (define (front_part str) (substring str (floor (/ (string -length str) 2)))) ;; Tests: (check-expect (front_part “computer”) “uter”) (check-expect (front_part “compute”) “pute”) ;;swap_parts: string -> string ;;Purpose: To take a string, str, and swap the front and back parts ;;Examples: (swap_parts “computer”) -> “utercomp” ;; (swap_parts “compute”) -> “putecom” (define (swap_parts str) (string -append (back_part str) (front_part str))) ;;Tests: (check-expect (swap_parts “computer”) “utercomp”) (check-expect (swap_parts “compute”) “putecom”)   BOOLEAN  VALUES   A  Boolean  value  is  either  true  or  false.   Boolean  functions  are  functions  that  produce  either  true  or  false.   Examples:     (=  x  y)     (<  x  y)     (>=  x  y)   Predicates:  Ask  questions  with  true  or  false  answers  (Ex.  zero?  number?  integer?  equal?)   We  can  also  build  our  own  predicates:     (define (long_name? name) (>= (string-length name) 8))   COMPLEX  RELATIONSHIPS   AND,  OR,  NOT   • AND  statements  mean  that  both  conditions  must  be  true  for  the  entire  statement  to  be  true   o Ex. (and (= 5 (+ 3 2))(= 1 1)) -> true   • OR  statements  indicate  that  only  one  of  the  conditions  must  be   true   o Ex. (or (= 5 5)(= 1 0)) -> true   • NOT  statements  require  the  inner  value  to  be  false,  for  the  NOT  statement  to  be  true   o Ex. (not (= 5 6)) -> true     Example  4  (Complex  Relationship  Trace):   (define str “computer”) (and (<= 6 (string-length str))(equal? “mpu t” (substring str 2 6)) -> (and (<= 6 (string-length “computer”))(equal? “mput” (substring str 2 6)) -> (and (<= 6 8)(equal? “mput” (substring str 2 6))) -> (and true (equal? “mput” (substring str 2 6))) -> (and (equal? “mput” (substring str 2 6)) -> (and (equal? “mput” (substring “computer” 2 6)) -> (and (equal? “mput” “mput”)) -> (and true) -> (and) -> true       CONDITIONAL  RELATIONSHIPS   Conditional  expressions  are  basically  a  series  of  questions  being  asked  and  answers  being  produced  if  the   answers  to  the  questions  are  true.    They  allow  you  to  analyze  functions  by  “cases”.   The  general  form  is:   (define (function parameter ...) (cond [(question 1) answer 1] [(question 2) answer 2] ... [else answer]))   Example  5:   Make  a  function  called   perfect_relationship, that  consumes  two  strings,  representing  the  names  of   two  people,  a  positive  integer,  and  a  number  representing  how  many  hours  the  two  people  have  been   together.  If  they  have  known  each  other  for  more  than  24  hours,  they  love  each  othe r.  If  they  have  known  each   other  for  less  than  24  hours,  but  the  positive  integer  is  even,  they  still  love  each  other.    Otherwise,  they  hate   each  other.    Make  your  function  produce   “name1 loves name2”. ;;perfect_relationship: string string int num[>=0] -> string ;;Purpose: create a string that represents the relationship status between two string, name1 and name2. If atime, is greater than 24, the function produces "name1 loves name2", if its less than or equal to 24, and int is even, then "name1 loves nam e2". otherwise, we get "name1 hates name2" ;;Examples: (perfect_relationship "miss universe" "Dylan" 5 42) => "miss universe loves Dylan" ;;(perfect_relationship "Dylan" “Scheme" 5 23) => "Dylan hates Scheme" (define (perfect_relationship name1 name 2 int atime) (cond [(> atime 24)(string-append name1 " loves " name2)] [(even? int)(string-append name1 " loves " name2)] [else (string-append name1 " hates " name2)])) ;;Tests (check-expect(perfect_relationship "Dylan" "Scheme" 5 23)"Dylan hates Scheme") (check-expect(perfect_relationship "miss universe" "Dylan" 5 42)"miss universe loves Dylan") SYMBOL   A  symbol  starts  with  the  quote  ‘  followed  by  something  (ex.  ‘blue,  ‘red).risons  ey  are  best  used  for  compa because  it  is  more  efficient  than  comparing  strings.    A  symbol  has  a  value  like  the  number  6.       Type  “symbol”  in  the  contract.     CHARACTER   Ex. #\space, #\1, #\a   Built-­‐in  Predicates:   • char-­‐upper-­‐case?   • char-­‐lower-­‐case?   • char-­‐numeric?   • char-­‐whitespace?   Type  “char”  in  the  contract.     INTRO  TO  STRUCTURES:  POSN  STRUCTURES   A  structure  is  a  way  of  bundling  data  together  to  form  a  single  package.   1. You  can  create  functions  that  consume  and/or  produce  structures   2. Define  our  own  structures   3. Each  has   • Constructor  function   • Selector  function   • Type  Predicate  Function     Example  6:   A  posn  is  a  structure  that  has  two  fields  containing  numbers  that  represent  x  and  y  coordinates.     Constructor  function:   (make-posn num1 num2)   Selector  functions:   (posn-x (make-posn num1 num2)) -> num1 (posn-y (make-posn num1 num2)) -> num2 Type  Predicate:     (posn? (make-posn num1 num2)) -> true     Ex.   (define point (make -posn 20 45)) (posn-x point) -> 20 (posn-y point) -> 45 (posn? point) -> true   DATA  DEFINITIONS  AND  STRUCTURE  DEFINITIONS   Data  Definition:  a  comment  specifying  the  types  of  data  being  used   Ex.   ;;a posn is a structure (make -posn xcoord ycoord), where ;;xcoord is a number ;;ycoord is a number     Structure  Definition:  a  code  defining  the  structure  (like  we  did  above)  and  allowing  us  to  then  use  constructor,   selector  and  predicate  functions  for  the  definition     (define-struct sname (field1 field2 ...))   Doing  this  gives  3  functions:   1. Constructor:  make-sname   2. Selectors:  sname-field1, sname-field2   3. Type  Predicate:  sname?     Example  7:   Write  a  function  called   reply that  consumes  an  email and  a  string  and  produces  an   email that  is  a  reply   to  the  email consumed  using  the  message  given.  The   contact that  sends  the  reply  email  will  be  the  same   as  the  contact that  received  the  original  email.  The  contactthat  receives  the  reply  email will  be  the   same  as  the  contact that  sent  the  original  email.  The  subject  of  the  reply  email will  be  the  same  as  the   subject  of  the  original  email except  that  it  will  start  with ".  The  message of  the  reply  email will   be  the  string  consumed  by  the   reply function,  followed  by  a  space,  followed  by  the   name of  the  sender,   followed  by  a  space,  followed  by  the  word  "said" followed  by  a  space  followed  by  the  original  message.     For  example:(reply (make-email (make-contact "Sandy Graham" "[email protected]") (make -contact "J.P. Pretti" "[email protected]") "Hello" "I love CS115!") "Me too.") produces(makeemail (make-contact "J.P. Pretti" "[email protected]") (make -contact "Sandy Graham" "[email protected]") "RE: Hello" "Me too. Sandy Graham said I love CS115!") (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 (define-struct email (from to subject message)) ;; An email is a structure (make-email f t s m) where ;; f is a contact representing who sent the email, ;; t is a contact representing who received the email, ;; s is a string representing the subject of the email, and ;; m is a non-­‐empty string representing the text of the message (define (reply an_email new_message) (make-email (email-to an_email) (email-from an_email) (string-append "RE: " (email -subject an_email)) (string-append new_message " " (contact -name(email-from an_email)) " said " (email-message an_email)))) ;Tests: (check-expect (reply (make-email (make-contact "Sandy Graham" "[email protected]") (make -contact "J.P. Pretti" "[email protected]") "Hello" "I love CS115!") "Me too.")(make -email(make-contact "J.P. Pretti" "[email protected]")(make -contact "Sandy Graham" "slgraha [email protected]") "RE: Hello" "Me too. Sandy Graham said I love CS115!")) LISTS   Formal  Data  Definition:   A  list  is  either:   • Empty  or   • (cons  f  r)  where   o f  is  a  value  and   o r  is  a  list     When  we  talk  about  a  list,  we  think  of  a  list  with  two  parts:   1. the  FIRST  element  of  the  list   2. the  REST  of  the  list  (which  is  a  list  as  well)     Ex.  (define list1 (cons ‘a (cons ‘b (cons ‘c (cons ‘d empty))))) (define list2 empty)   Using  the  definition  of  the  list  above:     (first list1) -> ‘a (r