Study Guides (248,018)
Canada (121,232)
CS 135 (14)
Final

CS 135 final exam review

56 Pages
1886 Views
Likes
Unlock Document

Department
Computer Science
Course
CS 135
Professor
Ian Goldberg
Semester
Fall

Description
CS  135  Exam  Review  Package   This  package  includes  the  packages  from  the  first  and  second  midterm  sessions.   CS  135  Midterm  1  Review  Package   Introduction  to  Scheme   Writing  Arithmetic  Expressions   • 4  -­‐  5  *  (3  +  2)  =>  (-­‐  4  (*  5  (+  3  2)))   • 3  *  5  /  (2  +  7)  +  3  =>  (+  3  /  (*  3  5)  (+  2  7))   Things  to  Remember:   • Extra  parentheses,  while  okay  in  mathematics,  affect  expressions  in   Scheme   • Operations  are  written  before  the  associated  arguments   • Operations  need  two  arguments   • Substitutions  are  done  left  to  right   Functions  in  Scheme   (define  (f  x  y)  (+  (*  x  x)  y))   • The  word  define  is  used  to  bind  a  name  to  an  expression   • f  is  the  name  of  the  function   • x  and  y  are  the  parameters   • Values  that  are  passed  as  x  and  y  are  the  arguments  of  the  function   • (+  (*  x  x)  y)  is  the  body  expression,  and   tells  us  what  the  function  does   • x  and  y  have  no  meaning  in  any  other  part  of  the  program   (define  b  “constant”)   • b  is  a  constant   • If  b  is  used  in  any  body  expressions,  “constant”  will  be  used   • Constants  can  make  programs  easier  to  understand             Design  Recipe   Contract   • Describes  the  arguments  that  your  function  takes  as  well  as   the  type  that  your  function  will   produce   • Some  possibilities  are  Int,  Nat,  Symbol,  String,  Posn,  etc.   • For  the  output  of  your  function,  None  is  also  a  possibility   Examples:     Symbol  -­‐>  None     String  Int  -­‐>  Boolean     Posn  Symbol  Int[>=  7]  -­‐>  Posn   Purpose   • Explains  what  your  function  does  using  the  names  of  your  parameters   • Purpose  comes  from  the  question   Example:    The  unit  of  speed  most  often   used  in  physics  is  meters  per  second  ( m/s).  A  common   Imperial  unit  of  speed  is  miles  per  hour  ( mph).  Write  a  function  mph-­‐>m/s  which   consumes  a  speed  in  the  units  of   mph  and  produces  the  same  speed  in  units  of   m/s.   Purpose:  converts  the  given  speed,  s,   from  mph  to  m/s   Examples   • Used  to  make  sure  you  understand  how  the  function  is  supposed  to  work   • Written  below  the  purpose  and  above  the  function   • Don’t  necessarily  test  all  cases ;  mostly  try  and  get  a  general  idea  about  what  your  function   should  do   Example:    Write  a  function   final-­‐cs135-­‐grade  that  consumes  four  numbers:   (a)  the  first  midterm  grade  (10%),   (b)  the  second  midterm  grade  (20%),   (c)  the  final  exam  grade  (45%),  and   (d)  the  assignments  grade  (20%).   This  function  should  produce  the  final  grad e  in  the  course.  You  may  need  to  review  the  mark   allocation  in  the  course.  You  can  assume  that  all  input  marks  are  percentages  and  are  given   as  integers  between  0  and  100,  inclusive.  Also,  assume  a  grade  of  100  for  participation  (5%).   Examples:     (check-­‐expect  (final-­‐cs135-­‐grade  50  50  50  50)  52.5)   (check-­‐expect  (final-­‐cs135-­‐grade  75  87  72  83)  78.9)   Definition   • This  is  where  you  write  your  function   • Must  include  the  header  and  the  body   • The  header  is  the  name  of  your  function  as  well  as  the  parameters   • The  body  is  the  expression :  what  your  function  actually  does  with  the  parameters   • The  header  should  be  written  before  your  purpose  is  written  so  that  you  can  refer  to   parameters  in  your  purpose   • Examples  should  be  written  after  your  header  is   complete  so  that  you  know  all  necessary   parameters   Example:     (define  (final-­‐cs135-­‐grade  mid1  mid2  final  assign)       (+  (*  mid1  0.10)  (*  mid2  0.20)  (*  final  0.45)  (*  assign  0.20)  5))   • Note:  using  constants  for  the  weight  of  each  section   would  make  your  program  more  readable   Tests   • Tests  are  written  at  the  very  end  of  the  design  recipe   • Used  to  find  any  errors  in  code  or  logic   • Use  check-­‐expect  to  test  your  function   • Form  of  check-­‐expect  is:   o (check-­‐expect  (function-­‐name  argument1  argument2  …)  answer )   o If  the  function  evaluates  to  the  given  answer,  it  will  produce  true   o Otherwise  check-­‐expect  evaluates  to  false ,  and  you  then  need  to  check  your  calculations   and/or  your  code   • Make  sure  to  test  helper  functions  as  well  to  better  locate  any  errors   • Test  one  or  two  general  cases   in  addition  to  all  special  cases,  or  those   cases  with  the  potential  to   cause  problems   Example:   For  the  previous  function:   (check-­‐expect  (final-­‐cs135-­‐grade  0  0  0  0)  5)   (check-­‐expect(final-­‐cs135-­‐grade  100  100  100  100)  100)   (check-­‐expect(final-­‐cs135-­‐grade  100  0  0  0)  15)   (check-­‐expect(final-­‐cs135-­‐grade  0  100  0  0)  25)   (check-­‐expect(final-­‐cs135-­‐grade  0  0  100  0)  50)   (check-­‐expect(final-­‐cs135-­‐grade  0  0  0  100)  25)         Helper  Functions   • Helper  functions  are  smaller  functions  in  your  program  that  perform  specific  tasks   • Make  code  easier  to  read  and  understand,  especially  for  larger  programs   • Breaking  down  a  problem  into  smaller  functions  can  make  it  easier  to  think  about   • Facilitate  the  debugging  of  specific  sections  of  code  and  help  reduce  errors  for  computations   done  multiple  times   • Need  to  use  the  design  recipe   when  creating  helper  functions  as  well   Example:     For  Assignment  2,  question   four  you  could  use  a  helper  function  that  takes  in  a  note  and   converts  it  to  a  natural  number.  This  would  then  make  it  easier  to  check  the  number  of  tones   between  the  three  notes  given.                                               Data  Types   Symbols  and  Strings   • Symbols  are  indicated  with  a  ‘    (‘blue,  ‘green,  ‘omg  are  all  examples  of  symbols)   • The  word  used  after  the  symbol  mark  only  has  meaning  to  the  user,  not  to  Scheme   • Strings  are  similar  to  symbols  on  the  surface     o Strings  are  actually  a  sequence  of  characters  (written  with  “”  around  the  character   sequence,  such  as  “blue”,  “grey”,  “elephant”)   o Strings  can  use  characters  that  symbols  cannot ,  such  as  spaces   o Strings  have  more  built-­‐in  functions  (string-­‐append,  string-­‐length,  etc)   • Symbols  are  used  for  fixed  label s;  strings  are  used  when  the  data  may  change  or  when   specific   parts  of  the  data  are  needed   Boolean  Values  and  Predicates   • There  are  two  Boolean  values:  true  and  false   • All  relational  operators  evaluate  to  either  true  or  false   • Some  relational  operators  are  =,  >,  =   • There  are  functions  called  predicates  which  produce  true  or  false  depending  on  the  argument   o Some  are  built  into  Scheme  (even?,  negative?,  zero?,  equal?,  symbol=?)   o Predicates  can  also  be  written  by  the  programmer   o Basically,  predicates  answer  a  question  with  true  or  false   Examples:     (=  x  0)     (<=  3  19)  =>  evaluates  to  true     (even?  5)  =>  evaluates  to  false     (symbol=?  ‘blue  ‘green)  =>  evaluates  to  false     (define  (multiple-­‐of-­‐4?  num)       (=  (%  num  4)  0))                 Conditional  Expressions   Compound  Conditions   • and,  or,  and  not  allow  for  a  broader  range  of  comparisons  (for  example ,  to  determine  whether  a   value  x  is  between  0  and  100 ,  you  can  write  (and  (>  x  0)  (<  x  100))   • and   o Can  have  more  than  2  arguments   o Evaluates  to  true  when  all  arguments  are  true   o If  any  argument  is  false,  Scheme  will  stop  evaluating  the  arguments  and  produce  false   • or   o Can  have  more  than  2  arguments   o Evaluates  to  true  when  at  least  one  argument  evaluates  to  true   o If  all  arguments  are  false,  then  evaluates  to  false   o Once  Scheme  evaluates  a  true  argument ,  it  stops  and  produces  true   • not   o Takes  one  argument   o Evaluates  to  true  when  the  argument  is  false   o Evaluates  to  false  when  the  argument  is  tru e   Examples:     (and  (symbol=?  ‘blue  ‘blue)  (<=  4  8))  =>  evaluates  to  true,  since  both  arguments  are  true     (not  (negative?  -­‐4))  =>  evaluates  to  false     (or  (>  (+7  4)  (*7  4))  (<  (+7  4)  (*7  4)))  =>  evaluates  to  true ,  since  the  second  argument  is  true                         Conditional  Expressions   • For  these,  we  use  cond   • These  expressions  are  a  group  of  arguments,  each  one  consisting  of  a  question  and  answer   o The  question  is  always  a  Boolean  expression   o The  answer  is  only  evaluated  if  the  Boolean  expression  is  true   o The  questions  are  evaluated  from  top  to  bottom   • There  must  always  be  one  argument  that  evaluates  to  true   • Many  times,  the  last  argument  in  a  conditional  expression  contains  the  question  else ,  which   automatically  evaluates  to  true   • Once  a  question  evaluates  to  true,  the   answer  associated  with  that  question  becomes  the  value   of  the  entire  expression   • To  write  tests  for  conditional  expressions:   o Write  a  test  for  each  boundary  condition  (for  example,  if  one  question  is  (<=  x  6) ,  you   should  test  for  values  less  than  6,  equal  to  6  and  greater  than  6)   o Write  a  test  for  a  value  that  satisfies  each  question   o Make  sure  all  code  has  been  tested  (DrRacket  will  highlight  any  code  that  hasn’t  been   tested)   Examples:     (cond  [(>  x  500)  ‘largest]     [(>=  x  100)  ‘medium]     [else  ‘smallest])     (cond       [(cond         [(p1?  x)  (p2?  x)]         [else  (p1?  x)])           (cond                                [(p3?  x)  ’Three]                                [else  ’Four])]       [else  ’Five])   Note:  The  third  cond  expression  is  the  answer  to  the  first  question -­‐answer  pair  of  the  main  cond   expression.             Syntax  and  Semantics   • Identifiers  (names  of  constants,  parameters,  functions)  cannot  contain  a  space  or  (  )  ,  .  ;  {  }  [  ]  ‘  “   • The  semantic  rules  of  Scheme  allow  for  only  one  interpretation  of  a  program   • Using  the  rules  of  the  semantic  model,  we  can  step  through  a  program  to  get  to  its  most  basic   level   Examples:   1) (+  4  6)  =>  10   2) (define  (multiply  x  y)  (*  x  y))   (multiply  3  6)   ð (*  3  6)   ð 18   3) (define  (my-­‐fn  x  y)   (cond  [(<  x  y)  x]     [(=  x  y)  ‘equal]     [(>  x  y)  y]))     (my-­‐fn  10  10)   ð (cond  [(<  10  10)  x]   [(=  x  y)  ‘equal]     [(>  x  y)  y])   ð (cond  [false  x]   [(=  x  y)  ‘equal]     [(>  x  y)  y])   ð (cond  [(=  x  y)  ‘equal]     [(>  x  y)  y])   ð (cond  [(=  10  10)  ‘equal]     [(>  x  y)  y])   ð (cond  [true  ‘equal]     [(>  x  y)  y])   ð ‘equal     Stepping  Through  Compound  Conditions   • And   o (and  true  expr2    .  .  .  )  =>  (and  expr2    .  .  .  )   o (and  false  expr2    .  .  .  )  =>  false   o (and)  =>  true,  since  there  are  no  false  arguments  in  the  expression   • Or   o (or  true  expr2    .  .  .  )  =>  true   o (or  false  expr2    .  .  .  )  =>  (or  expr2    .  .  .  )   o (or)  =>  false,  since  there  are  no  true  arguments  in  the  expression   Structures   • Allow  you  to  store  several  values  in  one   • A  predefined  structure  in  Scheme  is  the  posn   Posn   • A  posn  is  a  structure  containing  two  numbers,  given  the  names  x  and  y   • There  are  built-­‐in  functions,  a  constructor  function  and  selector  functions   • The  constructor  is  make-­‐posn  and  has  the  contract:   o make-­‐posn:  Number  Number  -­‐>  Posn   • The  selector  functions  allow  you  to  access  either  number  using  posn -­‐x  and  posn-­‐y   o posn-­‐x:  Posn  -­‐>  Number   o posn-­‐y:  Posn  -­‐>  Number   • Just  like  with  a  number  or  a  symbol,  (make -­‐posn  4  5)  is  a  value  and  cannot  be  simplified  further   General  Structures   • To  create  a  structure,  we  use  define -­‐struct  instead  of  define   o (define-­‐struct  posn  (x  y))   • When  defining  a  structure ,  you  need  a  name,  and  the  names  of  the  fields  in  parentheses   • The  functions  associated  with  any  structure  are  the  constructor,  selectors,  and  the  predicate   o Constructor:  make-­‐(the  name  of  your  structure)   o Selectors:  (for  posn)  posn -­‐x,  posn-­‐y   o Predicate:  (the  name  of  your  structure)?  (for  example,  posn?)   § The  predicate  returns  true  if  the  argument  is   a  structure  of  that  type,  and  false   otherwise   Structures  and  the  Design  Recipe   (define-­‐struct  student  (first  last  id))   ;;  a  student  =  (make-­‐student  String  String  Number)   ;;  my-­‐student-­‐fn:  Student  -­‐>  Any   (define  (my-­‐student-­‐fn  data)     …  (student-­‐first  data)  …     …  (student-­‐last  data)  …     …  (student-­‐id  data)  …)   • The  above  is  what  is  needed  in  the  design  recipe  for  each  new  structure   • You  must  define  the  structure   • Write  the  data  definition  (communicate  what  type  each  field  is  requir    to  be) • Create  a  template  for  a  function  that  consumes  the  structure   o Your  actual  function  may  not  use  all  the  fields ,  but  it  is  good  practice  to  write  the   template  to  avoid  forgetting  a  field   Practice  Problems   HTDP,  Section  2,  Question  1:  Write  the  contract,  purpose,  and  header  for  a  function  that  computes   the  area  of  a  rectangle  given  its  length  and  width.  Write  three  examples  for  the  behaviour  of  this   program.     Solution:     ;;  area:  Number  Number  -­‐>  Number   ;;  Purpose:  calculates  the  area  of  a  rectangle  given  the  length,  l,  and  the  width,  w   ;;  Examples:   (check-­‐expect  (area  5  3)  15)   (check-­‐expect  (area  1  1)  1)   (check-­‐expect  (area  10  15)  150)     (define  (area  l  w))     HTDP,  Section  2,  Question  11: The  nation  of  Progressiva  has  a  simple  tax  code.  The  tax  you  pay  is   your  salary  times  the  tax  rate,  and  the  tax  rate  is  1/2%  per  thousand  dollars  of  salary.  For  example,  if  you   make  $40,000,  your  tax  rate  is  1/2%  times  40,  which  is  20%,  so  you  pay  20%  of  $40,000,  which  is  $8,000.   Develop  a  function  to  compute  the  net  pay  (i.e.  pay  after  taxes)  of  a  person  with  a  given  salary.  HINT:   develop  one  or  two  auxiliary  functions  as  well  as  net  pay.     Solution:   To  start  this  problem,  break  it  into  smaller,  workable  pieces.  The  simplest  place  to  start  is   by  computing   the  tax  rate  for  a  given  salary.   (define  tax-­‐rate-­‐percent  0.5)  ;;0.5  is  a  constant  provided  in  the  question     Start  with  the  contract,  the  only  piece  of  information  that  needs  to  be  passed  to  the  function  is  the  salary.   ;;  tax-­‐rate:  Number  -­‐>  Number   ;;  Purpose:  compute  the  tax  rate  for  the  given  salary,  s ,  as  a  decimal     For  the  examples,  test  the  case  given  in  the  question  as   well  as  cases  with  numbers  that  are  relatively   simple  to  work  out  so  you  can  get  a  feel  of  how  the  function  works.   ;;  Examples:   (check-­‐expect  (tax-­‐rate  40000)  .20)   (check-­‐expect  (tax-­‐rate  10000)  .05)   (check-­‐expect  (tax-­‐rate  100000)  .50)     From  the  question,  we  know  that  the  tax  rate  =  [0.5  *  (s/1000)]/100.  The  division  by  100  gives  the   decimal  representation  of  the  percentage.  Now  convert  this  to  a  Scheme  expression:   (define  (tax-­‐rate  s)   (/  (*  tax-­‐rate-­‐percent  (/  s  1000))  100))     For  tests,  find  special  cases  that  may  show  errors  in  your  code.  Most  general  cases  will  be  covered  by   examples.   ;;  Tests:   (check-­‐expect  (tax-­‐rate  0)  0)   (check-­‐expect  (tax-­‐rate  1000)  0.005)   (check-­‐expect  (tax-­‐rate  200000)  1.00)     The  second  part  of  this  problem  is  to  calculate  how  much  of  the  salary  is  taken  as  taxes.  Start  with  the   contract;  again,  the  only  piece  of  information  passed  is  the  salary.  The  function  tax -­‐rate  is  part  of  the   body  of  the  function.   ;;  taxes:  Number  -­‐>  Number   ;;  Purpose:  compute  the  amount  of  tax  paid  for  the   given  salary,  s     Again,  for  examples,  test  simple  cases  as  well  as  the  case  given  in  the  question.  Here  I  chose  to  use  the   same  salaries  as  the  examples  in  the  above  function.   ;;  Examples:   (check-­‐expect  (taxes  40000)  8000)   (check-­‐expect  (taxes  10000)  500)   (check-­‐expect  (taxes  100000)  50000)     To  calculate  the  amount  of  money  taken  for  taxes,  simply  multiply  the  salary  by  the  tax  rate.  Notice  that   in  the  body  of  taxes,  the  function  tax-­‐rate  is  called.   (define  (taxes  s)   (*  s  (tax-­‐rate  s)))     Again,  I  chose  the  same  salaries  to  test  as  I  did  in  tax -­‐rate.  This  helps  to  follow  the  problem  through  and   makes  any  errors  easier  to  spot.   ;;  Tests:   (check-­‐expect  (taxes  0)  0)   (check-­‐expect  (taxes  1000)  5)   (check-­‐expect  (taxes  200000)  200000)     Finally,  put  everything  toget her.  From  the  question,  we  know  that  the  only  piece  of  information  supplied   to  net-­‐pay  is  the  salary.   ;;  net-­‐pay:  Number  -­‐>  Number   ;;  Purpose:  given  a  salary,  s,  produce  the  amount  the  person  is  paid  after  taxes     ;;  Examples:   (check-­‐expect  (net-­‐pay  40000)  32000)   (check-­‐expect  (net-­‐pay  10000)  9500)   (check-­‐expect  (net-­‐pay  100000)  50000)     Because  of  the  helper  functions  we  created,  net -­‐pay  is  simply  the  result  of    taxes  applied  to  the  salary,   subtracted  from  the  initial  salary.   (define  (net-­‐pay  s)   (-­‐  s  (taxes  s)))     ;;  Tests:   (check-­‐expect  (net-­‐pay  0)  0)   (check-­‐expect  (net-­‐pay  1000)  995)   (check-­‐expect  (net-­‐pay  200000)  0)     HTDP,  Section  4,  Question  1:   Develop  the  function  within?,  which  consumes  three  numbers   representing  the  x  and  y  coordinates  of  a  point  and  the  radius  r  of  a  circle  centred  around  the  origin.    It   returns  true  if  the  point  is  within  or  on  the  circle.  It  returns  false  otherwise.  The  distance  of  the  point  to   2 2 the  origin  is  the  square  root  of  x  +  y .     Solution:   Start  with  the  contract  of  the  function.  From  the  question,  we  know  that  it  takes  in   three  numbers  and   will  produce  a  Boolean  based  on  the  relationship  between  the   three  arguments   ;;  within?:  Number  Number  Number  -­‐>  Boolean   ;;  Purpose:  produce  true  if  the  point  represented  by  x  and  y  lies  within  or  on  a  circle  centered  about  the   origin  with  a  radius  r     Choose  simple  examples  to  illustrate  the  different  outputs  that  are  expected.   ;;  Examples:   (check-­‐expect  (within?  3  4  5)  true)   (check-­‐expect  (within?  5  6  3)  false)   (check-­‐expect    (within?  2  2  8)  true)     To  simplify  the  problem,  we  will  create  a  helper  function  called  sqr -­‐distance  to  compute  the  square  of  the   distance  from  the  origin  to  the  point  ( x,  y).  By  comparing  this  value  to  the  square  of  the  radius,  inexact   numbers  no  longer  need  be   considered.   (define  (within?  x  y  r)      (<=  (sqr-­‐distance  x  y)  (sqr  r)))     Be  sure  to  test  different  cases  that  were  not  covered  by  the  examples.   ;;  Tests:   (check-­‐expect  (within?  0  0  5)  true)   (check-­‐expect  (within?  7  4  9)  true)     Our  helper  function  takes  in  the  coordinates  of  the  point  and  computes  the  square  of  the  distance  from  it   to  the  origin.  If  we  found  the  distance,  we  would  end  up  with  inexact   numbers  that  would  cause   problems  for  close  comparisons.   ;;  sqr-­‐distance:  Number  Number   -­‐>  Number   ;;  Purpose:  computes  the  square  of  the  distance  of  the  point,  represented  by  x  and  y,  to  the  origin     Again,  I  chose  simple  numbers  to  illustrate  the  point  of  this  function.   ;;  Examples:   (check-­‐expect  (sqr-­‐distance  3  4)  25)   (check-­‐expect  (sqr-­‐distance  2  2)  8)     This  function  is  fairly  simple :  just  use  the  formula  given  in  the  question  and  add  the  squares  of  the   coordinates.   (define  (sqr-­‐distance  x  y)      (+  (sqr  x)  (sqr  y)))     ;;  Tests:   (check-­‐expect  (sqr-­‐distance  0  0)  0)   (check-­‐expect  (sqr-­‐distance  7  4)  65)   HTDP,  Section  4,  Question  2:   A  local  discount  store  has  a  policy  of  putting  labels  with  dates  on  all  of   its  new  merchandise.  If  an  item  has  not  sold  within  two   weeks,  the  store  discounts  the  item  by  25%  for   the  third  week,  50%  for  the  fourth  week,  and  75%  for  the  fifth  week.  After  tha t,  no  additional  discounts   are  given.  Develop  the  function  new-­‐price,  which  takes  the  initial  price  of  an  item  and  the  number  of   weeks  since  the  item  was  dated  and  produces  the  selling  price  of  the  item.     As  always,  start  with  the  contract.  From  the   question,  we  know  the  function  will  take  in  a  number  for  the   initial  price,  and  a  number  for  the  number  of  weeks  the  item  has  been  on  sale.   ;;  new-­‐price:  Number  Number  -­‐>  Number   ;;  Purpose:  using  the  initial  price,  iprice,  and  the  number  of  weeks  the  item  has  go ne  unsold,  week,     ;;                                    produce  the  new  selling  price  of  the  item     Work  through  some  simple  examples  to  get  a  feel  for  what  the  function  does.   ;;  Examples:   (check-­‐expect  (new-­‐price  10.00  4)  5)   (check-­‐expect  (new-­‐price  16.60  5)  4.15)     To  make  the  program  more  readable,  I’ve  included  constants  for  the  discount  for  weeks  3 -­‐5.   (define  week3  0.25)   (define  week4  0.50)   (define  week5  0.75)     Depending  on  how  many  weeks  the  item  has  been  on  sale,  the  new  price  of  the  item  will  vary.   Therefore,   we  need  to  use  a  conditional  expression .  If  the  item  has  been  on  sale  for  less  than  3  weeks,  no  discount  is   applied.  For  three  weeks,  we  apply  the  week  3  discount.  At  four  weeks,  we  apply  the  week  4  discount,   and  after  that,  the  week  5  discount  is  applied.  To  further  improve  readability,  and  to  reduce  the  chance   for  error,  a  helper  function  could  be  used  to  calculate  the  new  price.   (define  (new-­‐price  iprice  week)      (cond  [(<  week  3)  iprice]                            [(=  week  3)  (-­‐  iprice  (*  week3  iprice))]                            [(=  week  4)  (-­‐  iprice  (*  week4  iprice))]                            [else  (-­‐  iprice  (*  week5  iprice))]))     For  the  tests,  be  sure  to  check  when  week  is  smaller  than  3,  equal  to  3,  equal  to  4,  equal  to  5  and  greater   than  5.  This  ensures  that  no  value  of  week  will  cause  an  error.  Testing  the  case  where   week  is  equal  to  0   is  an  extra  precaution.   ;;  Tests:   (check-­‐expect  (new-­‐price  133  0)  133)   (check-­‐expect  (new-­‐price  8.40  3)  6.30)(check-­‐expect  (new-­‐price  16.60  7)  4.15)       HTDP,  Section  6,  Question  4:   Provide  a  structure  definition  and  a  data  definition  for  an  online  auction   entry,  which  is  characterized  by  four  pieces  of  information:  the  item  number,  the  highest  bidder,  the   current  bid,  and  'Open  or  'Closed.  Develop  a  function  that  consumes  a  bidder,  a  bid  amount,  and  an   auction  entry  and  then  returns  a  new  entry.  If  the  bid  amount  is  less  than   or  equal  to  the  current  bid  or   if  the  auction  is  closed,  then  the  original  entry  is  returned.   This  is  part  of  the  design  recipe  for  structures.  You  m ust  define  your  structure,  explain  the  argument   types,  and  create  a  template  for  a  function  that  uses  the  structure.   (define-­‐struct  auction-­‐entry  (item-­‐num  high-­‐bid  curr-­‐bid  status))   ;;  a  auction-­‐entry  =  (make-­‐auction-­‐entry  Number  Symbol  Number  Symbol)   ;;  my-­‐auction-­‐entry-­‐fn:  Auction-­‐entry  -­‐>  Any   ;(define  (my-­‐auction-­‐entry-­‐fn  data)   ;    ...  (auction-­‐entry-­‐item-­‐num  data)  ...   ;    ...  (auction-­‐entry-­‐high-­‐bid  data)  ...   ;    ...  (auction-­‐entry-­‐curr-­‐bid  data)  ...   ;    ...  (auction-­‐entry-­‐status  data)  ...)     Start  with  the  contract.  From  the  question,  we  know  that  it  takes  in  a  name  (in  this  case,  let’s  assume  it’s   a  symbol  since  it  wasn’t  specified  in  the  question),  a  number  corresponding  to  the  new  bid,  and  an   auction  entry.  It  then  returns  an  updated  auction  entry.   ;;  update-­‐entry:  Symbol  Number  Auction -­‐entry  -­‐>  Auction-­‐entry   ;;  Purpose:  update  and  return  the  given  auction-­‐entry,  ae,  with  the  new  bidder,  name,  and  new  bid,  bid,     ;;                                    unless  the  new  bid  is  less  than   or  equal  to  the  current  bid,  or  the  auction  is  closed     Create  a  couple  of  examples  to  ensure  you  understand  what  the  question  is  asking  before  writing  the   body  of  the  function.   ;;  Examples:   (check-­‐expect  (update-­‐entry  'Jack  1800  (make-­‐auction-­‐entry  20332  'Jane  1600  'Open))                                (make-­‐auction-­‐entry  20332  'Jack  1800  'Open))   (check-­‐expect  (update-­‐entry  'Alice  12  (make-­‐auction-­‐entry  20332  'Jane  1600  'Open))     (make-­‐auction-­‐entry  20332  'Jane  1600  'Open))     From  the  question,  we  know  that  if  the  auction  is  closed,  or  the  new  bid  is  less  than  or  equal  to  the   current  bid,  we  produce  the  original  auction -­‐entry.  The  first  two  questions  could  be  combined  into  one   ‘or’  statement.  If  neither  of  these  conditions  are   met,  the  auction -­‐entry  is  changed  to  reflect  the  new   bidder  and  bid.  To  access  a  specific  field  from  your  structure,  hyphenate  the  structure  name  with  the  field   you  need  to  access.   (define  (update-­‐entry  name  bid  ae)      (cond  [(equal?  (auction-­‐entry-­‐status  ae)  'Closed)  ae]                            [(<=  bid  (auction-­‐entry-­‐curr-­‐bid  ae))  ae]                            [else  (make-­‐auction-­‐entry  (auction-­‐entry-­‐item-­‐num  ae)  name  bid  (auction -­‐entry-­‐status  ae))]))     Use  the  tests  to  check  that  all  conditions  from  the  question  are  met.  Have  on e  test  where  the  auction  is   closed,  one  where  the  new  bid  is  less  than  the  current  bid,  one  where  the  bids  are  equal,  and  one  where   the  new  bid  is  larger  than  the  current  bid.   ;;  Tests:   (check-­‐expect  (update-­‐entry  'Jack  1800  (make-­‐auction-­‐entry  20332  'Jane  1600  'Closed))                                (make-­‐auction-­‐entry  20332  'Jane  1600  'Closed))   (check-­‐expect  (update-­‐entry  'Pete  300  (make-­‐auction-­‐entry  20332  'Mary  1800  'Open))                                (make-­‐auction-­‐entry  20332  'Mary  1800  'Open))   (check-­‐expect  (update-­‐entry  'Jack  1800  (make-­‐auction-­‐entry  20332  'Jane  1800  'Open))                                (make-­‐auction-­‐entry  20332  'Jane  1800  'Open))   (check-­‐expect  (update-­‐entry  'Jack  1800  (make-­‐auction-­‐entry  20332  'Jane  0  'Open))                                (make-­‐auction-­‐entry  20332  'Jack  1800  'Open))     HTDP,  Section  7,  Question  2:   Develop  data  and  structure  definitions  for  a  collection  of  3D  shapes.  The   collection  includes   • cubes,  with  relevant  properties  being  the  length  of  an  edge;   • prisms,  which  are  rectangular  solids  and   with  relevant  properties  being  length,  width,  and   height;   • spheres,  with  relevant  property  being  the  radius.   Develop  the  function  volume.  The  function  consumes  a  3D  shape  and  produces  the  volume  of  the  object.   The  volume  of  a  cube  is  the  cube  of  the  length  of  one  of  its  edges.  3he  volume  of  a  prism  is  the  product   of  its  length,  width,  and  height.  The  volume  of  a  sphere  is  4/3  *  PI  *  r .     Solution:   Data  definition  and  function  template  for  a  cube.   (define-­‐struct  cube  (edge))   ;;  a  Cube  =  (make-­‐cube  Number)   ;;  my-­‐cube-­‐fn:  Cube  -­‐>  Any   ;(define  (my-­‐cube-­‐fn  data)   ;    (...(cube-­‐edge  data)...))     Data  definition  and  function  template  for  a  prism.   (define-­‐struct  prism  (length  width  height))   ;;  a  Prism  =  (make-­‐prism  Number  Number  Number)   ;;  my-­‐prism-­‐fn:  Prism  -­‐>  Any   ;(define  (my-­‐prism-­‐fn  data)   ;    (...(prism-­‐length  data)...   ;      ...(prism-­‐width  data)...   ;      ...(prism-­‐height  data)...))     Data  definition  and  function  template  for  a  sphere.   (define-­‐struct  sphere  (radius))   ;;  a  Sphere  =  (make-­‐sphere  Number)   ;;  my-­‐sphere-­‐fn:  Sphere  -­‐>  Any   ;(define  (my-­‐sphere-­‐fn  data)   ;    (...(sphere-­‐radius  data)...))     A  3D-­‐shape  also  needs  a  data  definition  and  function  template.  The  data  definition  is  slightly  different   from  a  structure.   ;;  A  3D-­‐shape  is  either:   ;;  *  a  cube   ;;  *  a  prism   ;;  *  a  sphere   ;;my-­‐3D-­‐shape-­‐fn:  3D-­‐shape  -­‐>  Any   ;(define  (my-­‐3D-­‐shape-­‐fn  data)   ;    (cond  [(cube?  data)  (...(cube-­‐edge  data)...)]   ;                          [(prism?  data)  (...(prism-­‐length  data)...   ;                                                                                ...(prism-­‐width  data)...   ;                                                                                ...(prism-­‐height  data)...)]   ;                          [(sphere?  data)  (...(sphere-­‐radius  data)...)]))     Define  the  constant  PI  for  calculations  involving  the  sphere.   (define  PI  3.14159)     Start  with  the  contract  as  usual.  Use  th e  data  definition  of  a  3D-­‐shape  in  the  contract.   ;;  volume:  3D-­‐shape  -­‐>  Number   ;;  Purpose:  consume  a  3D-­‐shape  and  produce  the  volume  of  the  shape     Your  examples  should  show  what  happens  with  each  different  3D -­‐shape.   ;;  Examples:   (check-­‐expect  (volume  (make-­‐cube  3))  27)   (check-­‐expect  (volume  (make-­‐prism  3  4  5))  60)   (check-­‐expect  (volume  (make-­‐sphere  3))  (*  (/  4  3)  PI  (expt  3  3)))     The  function  itself  is  fairly  short.  I  used  the  function  template  for  a  3D -­‐shape  and  filled  in  the  necessary   details.  Remember,  each  structure  has  a  predicate  you  can  use  to  test  whether  you  have  that  structure  or   not  (example:  cube?).     (define  (volume  shape)   (cond                [(cube?  shape)  (expt  (cube-­‐edge  shape)  3)]                  [(prism?  shape)  (*  (prism-­‐length  shape)  (prism-­‐width  shape)  (prism -­‐height  shape))]                  [(sphere?  shape)  (*  (/  4  3)  PI  (expt  (sphere -­‐radius  shape)  3))]))     Make  sure  to  thoroughly  test  each  3D -­‐shape.  Check-­‐within  is  not  usually  used  in  most  progr ams  in  CS   135  as  these  programs  rarely  deal  with  comparing  inexact  numbers.  To  use  it,  the  answer  you  expect  is   followed  by  the  error  you  allow  in  the  answer.  In  this  case,  my  last  test  allows  the  answer  to  be  between   523.597  to  523.599.   ;;  Tests:   (check-­‐expect  (volume  (make-­‐cube  0))  0)   (check-­‐expect  (volume  (make-­‐prism  0  0  0))  0)   (check-­‐expect  (volume  (make-­‐sphere  0))  0)   (check-­‐expect  (volume  (make-­‐cube  5))  125)   (check-­‐expect  (volume  (make-­‐prism  2  2  2))  8)   (check-­‐within  (volume  (make-­‐sphere  5))  523.598  0.001)                                             CS  135  Midterm  2  Review  Package   Structures   • Allow  you  to  store  several  values  in  one  entity   • A  predefined  structure  in  Scheme  is  the  posn   General  Structures   • To  create  a  structure,  we  use   define-­‐struct  instead  of  define   o (define-­‐struct  posn  (x  y))   • When  defining  a  structure,  you  need  a  name,  and  the  names  of  the  fields  in  parenthes   • The  functions  associated  with  any  structure  are  the  constructor,  selectors,  and  the  predicate   o Constructor:  make-­‐(the  name  of  your  structure)   o Selectors:  (for  posn)  posn -­‐x,  posn-­‐y   o Predicate:  (the  name  of  your  structure)?  (for  example,  posn?)   § The  predicate  returns  true  if  the  argument  is  a  structure  of  that  type,  and  false   otherwise   Structures  and  the  Design  Recipe   (define-­‐struct  student  (first  last  id))   ;;  a  student  =  (make-­‐student  String  String  Number)   ;;  my-­‐student-­‐fn:  Student  -­‐>  Any   (define  (my-­‐student-­‐fn  data)     …  (student-­‐first  data)  …     …  (student-­‐last  data)  …     …  (student-­‐id  data)  …)   • The  above  is  what  is  neede d  in  the  design  recipe  for  each  new  structure   • You  must  define  the  structure   • Write  the  data  definition  (communicate  what  type  each  field  is  required  to  be)   • Create  a  template  for  a  function  that  consumes  the  structure   o Your  actual  function  may  not  use  all  the  fields,  but  it  is  good  practice  to  write  the   template  to  avoid  forgetting  a  field             Lists   • More  flexible  than  structures   • Used  for  varying  amounts  of  data   • It  is  possible  to  hold  different  data  types  in  a  general  list,  although  it  is  usually  specified  in   comments  what  type(s)  all  the  values  should  be   What  is  a  List?   • empty  is  a  value  in  Scheme  that  represents  an  empty  list   • The  built-­‐in  predicate  empty?  returns  true  for  an  empty  list  and  false  otherwise   • The  built-­‐in  predicate  cons?  returns  true  for  a  list  and  false  otherwise   • The  keyword  cons  is  used  to  build  lists   o Takes  two  arguments  which  are  a  Scheme  value  and  a  list  (the  list  could  be  empty)   o Example:  (cons  ‘blue  empty)   • The  data  definition  is:   ;;  A  List  is  one  of:   ;;  *  empty   ;;  *  (cons  Any  List)   • This  definition  is  recursive   o At  least  one  part  of  the  definition  (in  this  case  empty)  must  not  refer  back  to  the  list;  this   is  the  base  case   o The  other  part  of  the  definition  (in  this  case  (cons  Any  List))  is  the  recursive  part  of  the   definition   • The  first  item,  Any,  cannot  be  empty   • When  stepping  through  code,  a  list,  like  structures,  cannot  be  simplified  a    further Example:  (cons  1  (cons  2  (cons  3  (cons  4  (cons  5  empty)))))     The  first  cons  contains  1  and  a  list  which  is  a  cons  that  contains  2  and  a  list  …  and  the  last  cons       contains  5  and  an  empty  list.   Selectors   • First  and  rest  are  selectors  for  lists   • First  returns  the  first  item  in  the  list   o For  the  list  in  the  above  example,  first  would  return  1   • Rest  returns  everything  after  the  first  item  in  the  list   o For  the  list  in  the  above  example,  rest  would  return  (cons  2  (cons  3  (cons  4  (cons  5   empty))))   • For  stepping  through  a  program  with  first  or  rest,  the  following  rules  hold  for  a   list  (cons  a  b)   where  a  is  Any  and  b  is  a  list:   o (first  (cons  a  b))  =>  a   o (rest  (cons  a  b))  =>  b   Visualizing  Lists   • One  method  is  to  use  nested  boxes   Example:  (cons  ‘blue  (cons  ‘green  (cons  ‘pink  empty)))     first   rest   first   rest   first   rest   ‘blue   ‘green     Nested  boxes   ‘pink   empty     • Another  method  is  box-­‐and-­‐pointer   Example:  (cons  ‘blue  (cons  ‘green  (cons  ‘pink  empty)))     first   rest   first   rest   first   rest     ‘blue     ‘green     ‘pink       ‘blue     ‘green     ‘pink             Coding  with  Lists   • The  data  definition  above  can  be  tailored  to  suit  any  type  of  list  by  replacing  List  with  any  of  the   following  and  Any  with  the  corresponding  data  type:   o (listof  Symbol)  for  a  list  containing  only  symbols   o (listof  Number)  for  a  list  containing  only  numbers   o (listof  (union  …))  for  a  list  containing  multiple  types,  replace  the  ellipsis  with  the  types  in   the  list   o (listof  Any)  for  a  general  case   • There  is  a  template  for  functions  using  lists:   ;;  my-­‐lst-­‐fn:  (listof  Any)-­‐>Any   (define  (my-­‐lst-­‐fn  lst)   (cond     [(empty?  lst)  .  .  .  ]     [else  .  .  .  (first  lst)  .  .  .     .  .  .  (my-­‐lst-­‐fn  (rest  lst))  .  .  .  ]))   • This  is  for  a  general  list;  it  can  be  made  more  specific  depending  on  what  type(s)  your  list   contains         Stepping  with  Lists   • Stepping  through  a  program  as  before  requires  too  much  writing  to  actually  do  for  programs   involving  lists   • Instead  we  use  a  condensed  trace  for  these  recursive  functions   • Steps  included  in  a  condensed  trace  for  a  function,  my -­‐recurs-­‐fn:   o Any  time  my-­‐recurs-­‐fn  is  applied  to  a  value   o The  first  line  that  does  not  include  my -­‐recurs-­‐fn   o The  final,  simplified  value   Example:  (define  (scale  lon  num)      (cond  [(empty?  lon)  empty]                  [else  (cons  (*  (first  lon)  num)  (scale  (rest  lon)  num))]))   (scale  (cons  1  (cons  2  (cons  3  (cons  4  (cons  5  e mpty)))))  2)   ð (cons  2  (scale  (cons  2  (cons  3  (cons  4  (cons  5  empty))))  2))   ð (cons  2  (cons  4  (scale  (cons  3  (cons  4  (cons  5  empty)))  2)))   ð (cons  2  (cons  4  (cons  6  (scale  (cons  4  (cons  5  empty))  2))))   ð (cons  2  (cons  4  (cons  6  (cons  8  (scale  (cons  5  empty)  2)))))   ð (cons  2  (cons  4  (cons  6  (cons  8  (cons  10  (scale  empty  2))))))   ð (cons  2  (cons  4  (cons  6  (cons  8  (cons  10  empty)))))   Design  Recipe   • Just  as  with  structures,  a  data  definition  is  required  for  each  different  type  of  list   o At  least  one  part  of  the  definition  must  not  refer  back  to  the  definition;  these  are  base   cases   • You  must  also  include  a  template  for  a  function  that  takes  the  list  as  an  argument   o These  functions  will  use  a  cond  expression  with  each  question  dealing  with  one  part  of  the   data  definition   • Use  the  function  templates  when  creating  your  function   o Fill  in  base  cases  first,  as  these  are  usually  easiest  to  deal  with   o The  recursive  parts  involve  thinking  about  how  you  need  to  combine  values  after  each   step           Built-­‐in  List  Functions   • empty?   o Consumes  a  list   o Checks  whether  the  given  list  is  empty   o Returns  true  if  the  list  is  empty,  or  false  if  it  is  not   o (empty?  lst)   • cons?   o Consumes  anything   o Checks  whether  the  argument  is  a  list  or  not   o Returns  true  if  the  argument  is  a  list,  or  false  otherwise   o (cons?  data)   • first   o Consumes  a  list   o Produces  the  first  element  of  the  list   o (first  lst)   • rest   o Consumes  a  list   o Produces  the  list  without  the  first  element   o (rest  lst)   • length     o Consumes  a  list   o Produces  the  length  of  the  given  list   (excluding  empty)   o (length  lst)   • member?   o Consumes  an  element  of  any  type  and  a  list   o Checks  whether  the  element  is  in  the  list   o Returns  true  if  the  element  is  in  the  list,  or  false  otherwise   o (member?  elem  lst)   • reverse   o consumes  a  list   o produces  the  list  in  reverse   o (reverse  lst)             More  Complex  Lists   • While  lists  may  contain  simple  data  types,  lists  can  also  be  more  complicated   • Some  lists  can  contain  structures   o Example:  (define-­‐struct  posn  (x  y))         (define  structlist  (cons  (make-­‐posn  2  3)  (cons  (make-­‐posn  1  4)  empty)))   • A  list  can  also  be  a  list  of  lists   o Example:  (define  lst-­‐of-­‐lst  (cons  (cons  3  (cons  4  empty))  (cons  (cons  ‘blue  (cons  ‘green   empty))  empty)))   § (cons  3  (cons  4  empty))  is  the  first  list  in  lst -­‐of-­‐lst   § (cons  (cons  ‘blue  (cons  ‘green  empty))  empty)    is  the  rest  of  the  list  in  lst -­‐of-­‐lst   List  Abbreviations   • Instead  of  writing  a  long  list  using  cons  (example  (cons  1  (cons  2  (cons  3  empty))))  we  can  use  list   to  make  a  list  (example  is  now  (list  1  2  3))   • You  can  also  write  a  list  as  ‘(exp1  exp2  …  expn)  for  lists  containing  only  symbols,  strings  and   numbers   o Example:  ‘(red  blue  green)   • The  keyword  list  creates  a  list  of  fixed  length  while  cons  is  used  to  add  a  new  element  to  the   front  of  a  list   • A  list  of  lists  is  now  much  easier  to  visualize   o Example:  (cons  (cons  3  (cons  4  empty))  (cons  (cons  ‘blue  (cons  ‘gr een  empty))  empty))  is   equivalent  to  (list  (list  3  4)  (list  ‘blue  ‘green))  and  ‘((3  4)  (blue  green))   Types  of  Lists   • There  are  flat  lists   o These  contain  elements  that  are  not  lists   o Example:  (list  1  2  3  4  5)   • There  are  lists  of  lists   o These  contain  elements  tha t  are  lists   o Example:  (list  (list  1  2)  (list  3  4))   • There  are  nested  lists   o These  contain  elements  that  are  lists  containing  elements  (can  be  lists)  to  any  depth   o Example:  (list  (list  (list  ‘colour  ‘blue)  (list  ‘colour  ‘pink))  (list  (list  ‘sport  ‘soccer)))           Dictionaries   • These  are  keys  that  are  associated  with  a  value   • Three  operations  that  can  be  used  with  dictionaries  are   o lookup   § Consumes  a  key   § Produces  the  value  associated  with  the  given  key   o add   § Consumes  a  key  and  value   § Adds  the  pair  to  the  dictionary   o remove   § Consumes  a  key   § Removes  the  key  and  associated  value  from  the  dictionary   Association  Lists   • In  this  way,  a  dictionary  is  a  stored  list  of  pairs   o A  pair  is  a  two  element  list   o The  first  element,  for  this  course,  is  a  number  for  the  key   o The  second,  for  this  course,  is  a  string  for  the  value   • The  data  definition  for  an  association  list  is:   ;;  An  association  list  (AL)  is  one  of:   ;;  *  empty   ;;  *  (cons  (list  Number  String)  AL)   • Every  key  is  unique  although  some  keys  might  have  the  same  values   • In  a  contract,  since  there  is  a  data  definition,  we  could  use  AL  instead  of  (listof  (list  Number   String))   • The  template  for  an  association  list  is   ;;  my-­‐al-­‐fn:  AL  -­‐>  Any   (define  (my-­‐al-­‐fn  alst)   (cond   [(empty?  alst)  .  .  .  ]   [else  .  .  .  (first  (first  alst))  .  .  .  ;;  first  key   .  .  .  (second  (first  alst))  .  .  .  ;;  first  value       .  .  .  (my-­‐al-­‐fn  (rest  alst))]))         Recursion   Structural  Recursion   • This  is  what  is  used  for  the  data  definition  and  template  for  lists   • For  this  type  of  recursion,  each  recursive  call  leaves  all  parameters  unch anged  or  moves  the   recursion  one  step  closer  to  a  base  case   Natural  Numbers   • A  natural  number  has  a  recursive  definition   ;;  A  Nat  is  one  of:   ;;  *  0   ;;  *  (add1  Nat)   • A  template  can  also  be  made  for  this  definition,  just  like  with  lists   • The  template  can  be  changed  to  make  the  base  case  any  integer  larger  than  0   Accumulative  Recursion   • This  is  quite  close  to  structural  recursion  except  that  at  least  one  parameter  is  an  accumulator   and  does  not  follow  the  rules  of  structural  recursion   • A  wrapper  function  sets  th e  initial  value  of  the  accumulator  and  then  sends  it,  along  with  the   other  parameters,  to  a  helper  function   Generative  Recursion   • Parameters  are  calculated  at  each  step   • Much  harder  to  code  and  debug   • Also  harder  to  know  that  the  function  will  always  terminat e                 Processing  Two  Lists   • Four  cases  for  the  cond  expression   o list1  is  empty  and  list2  is  empty   o list1  is  empty  and  list2  is  not  empty   o list1  is  not  empty  and  list2  is  empty   o list1  is  not  empty  and  list2  is  not  empty   Processing  Just  One  List   • Only  one  list  is  processed  by  the  function   • Just  two  possibilities  to  look  at,  either  list1  is  empty  or  not  empty   • Example:  appending  one  list  to  another   Processing  in  Lockstep   • Both  lists  are  consumed  by  the  function  at  the  same  rate   • This  means  that  the  lists  must  be  the   same  length   • Only  the  same  two  possibilities  need  to  be  examined,  since  list2  will  be  empty  (or  not  empty)  at   the  same  time  that  list1  is  empty  (or  not  empty)   • Example:  calculating  the  dot  product  of  two  vectors  inputted  as  lists   o The  first  element  of  each  li st  is  multiplied  together  and  added  to  the  product  of  the   second  element  from  each  list  and  so  on  until  the  last  element  of  each  list   Processing  at  Different  Rates   • All  four  possibilities  must  be  considered  since  either  list  could  be  empty  at  any  time   • When  both  lists  are  empty,  it  is  a  base  case   • The  possibilities  where  either  list1  or  list2  are  empty  may  be  base  cases  as  well  depending  on   the  function  you  are  writing   • The  fourth  possibility  can  have  many  different  templates  depending  on  the  program   • Example:  merging  two  lists  into  one  sorted  list                 Practice  Problems   HTDP,  Section  6,  Question  4:   Provide  a  structure  definition  and  a  data  definition  for  an  online  auction   entry,  which  is  characterized  by  four  pieces  of  information:  the  item  number,  the  highest  bidder,  the   current  bid,  and  'Open  or  'Closed.  Develop  a  function  that  consumes  a  bidder,  a  bid  amount,  and  an   auction  entry  and  then  returns  a  new  entry.  If  the  bid  amount  is  less  than   or  equal  to  the  current  bid  or   if  the  auction  is  closed,  then  the  original  entry  is  returned.   This  is  part  of  the  design  recipe  for  structures.  You  must  define  your  structure,  explain  the  argument   types,  and  create  a  template  for  a  function  that  uses  the  structure.   (define-­‐struct  auction-­‐entry  (item-­‐num  high-­‐bid  curr-­‐bid  status))   ;;  a  auction-­‐entry  =  (make-­‐auction-­‐entry  Number  Symbol  Number  Symbol)   ;;  my-­‐auction-­‐entry-­‐fn:  Auction-­‐entry  -­‐>  Any   ;(define  (my-­‐auction-­‐entry-­‐fn  data)   ;    ...  (auction-­‐entry-­‐item-­‐num  data)  ...   ;    ...  (auction-­‐entry-­‐high-­‐bid  data)  ...   ;    ...  (auction-­‐entry-­‐curr-­‐bid  data)  ...   ;    ...  (auction-­‐entry-­‐status  data)  ...)     Start  with  the  contract.  From  the  question,  we  know  that  it  takes  in  a  name  (in  this  case,  let’s  assume  it’s   a  symbol  since  it  wasn’t  specified  in  the  question),  a  number  corresponding  to  th e  new  bid,  and  an   auction  entry.  It  then  returns  an  updated  auction  entry.   ;;  update-­‐entry:  Symbol  Number  Auction -­‐entry  -­‐>  Auction-­‐entry   ;;  Purpose:  update  and  return  the  given  auction-­‐entry,  ae,  with  the  new  bidder,  name,  and  new  bid,  bid,     ;;                                    unless  the  new  bid  is  less  than  or  equal  to  the  current  bid,  or  the  auction  is  closed     Create  a  couple  of  examples  to  ensure  you  understand  what  the  question  is  asking  before  writing  the   body  of  the  function.   ;;  Examples:   (check-­‐expect  (update-­‐entry  'Jack  1800  (make-­‐auction-­‐entry  20332  'Jane  1600  'Open))                                (make-­‐auction-­‐entry  20332  'Jack  1800  'Open))   (check-­‐expect  (update-­‐entry  'Alice  12  (make-­‐auction-­‐entry  20332  'Jane  1600  'Open))     (make-­‐auction-­‐entry  20332  'Jane  1600  'Open))     From  the  question,  we  know  that  if  the  auction  is  closed,  or  the  new  bid  is  less  than  or  equal  to  the   current  bid,  we  produce  the  original  auction -­‐entry.  The  first  two  questions  could  be  combined  into  one   ‘or’  statement.  If  neither  of  these  conditions  are  met,  the  auction -­‐entry  is  changed  to  reflect  the  new   bidder  and  bid.  To  access  a  specific  field  from  your  structure,  hyphenate  the  structure  name  with  the  field   you  need  to  access.   (define  (update-­‐entry  name  bid  ae)      (cond  [(equal?  (auction-­‐entry-­‐status  ae)  'Closed)  ae]                            [(<=  bid  (auction-­‐entry-­‐curr-­‐bid  ae))  ae]                            [else  (make-­‐auction-­‐entry  (auction-­‐entry-­‐item-­‐num  ae)  name  bid  (auction -­‐entry-­‐status  ae))]))     Use  the  tests  to  check  that  all  conditions  from  the  question  are  met.  Have  one  test  where  the  auction  is   closed,  one  where  the  new  bid  is  less  than  the  current  bid,  one  where  the  bids  are  equal,  and  one  where   the  new  bid  is  larger  than  the  current  bid.   ;;  Tests:   (check-­‐expect  (update-­‐entry  'Jack  1800  (make-­‐auction-­‐entry  20332  'Jane  1600  'Closed))                                (make-­‐auction-­‐entry  20332  'Jane  1600  'Closed))   (check-­‐expect  (update-­‐entry  'Pete  300  (make-­‐auction-­‐entry  20332  'Mary  1800  'Open))                                (make-­‐auction-­‐entry  20332  'Mary  1800  'Open))   (check-­‐expect  (update-­‐entry  'Jack  1800  (make-­‐auction-­‐entry  20332  'Jane  1800  'Open))                                (make-­‐auction-­‐entry  20332  'Jane  1800  'Open))   (check-­‐expect  (update-­‐entry  'Jack  1800  (make-­‐auction-­‐entry  20332  'Jane  0  'Open))                                (make-­‐auction-­‐entry  20332  'Jack  1800  'Open))                                                   HTDP,  Section  7,  Question  2:   Develop  data  and  structure  definitions  for  a  collection  of  3D  shapes.  The   collection  includes   • cubes,  with  relevant  properties  being  the  length  of  an  edge;   • prisms,  which  are  rectangular  solids  and   with  relevant  properties  being  length,  width,  and   height;   • spheres,  with  relevant  property  being  the  radius.   Develop  the  function  volume.  The  function  consumes  a  3D  shape  and  produces  the  volume  of  the  object.   The  volume  of  a  cube  is  the  cube  of  the  length  of  o ne  of  its  edges.  The  volume  of  a  prism  is  the  product   of  its  length,  width,  and  height.  The  volume  of  a  sphere  is  4/3  *  PI  *  r .     Solution:   Data  definition  and  function  template  for  a  cube.   (define-­‐struct  cube  (edge))   ;;  a  Cube  =  (make-­‐cube  Number)   ;;  my-­‐cube-­‐fn:  Cube  -­‐>  Any   ;(define  (my-­‐cube-­‐fn  data)   ;    (...(cube-­‐edge  data)...))     Data  definition  and  function  template  for  a  prism.   (define-­‐struct  prism  (length  width  height))   ;;  a  Prism  =  (make-­‐prism  Number  Number  Number)   ;;  my-­‐prism-­‐fn:  Prism  -­‐>  Any   ;(define  (my-­‐prism-­‐fn  data)   ;    (...(prism-­‐length  data)...   ;      ...(prism-­‐width  data)...   ;      ...(prism-­‐height  data)...))     Data  definition  and  function  template  for  a  sphere.   (define-­‐struct  sphere  (radius))   ;;  a  Sphere  =  (make-­‐sphere  Number)   ;;  my-­‐sphere-­‐fn:  Sphere  -­‐>  Any   ;(define  (my-­‐sphere-­‐fn  data)   ;    (...(sphere-­‐radius  data)...))     A  3D-­‐shape  also  needs  a  data  definition  and  function  template.  The  data  definition  is  slightly  different   from  a  structure.   ;;  A  3D-­‐shape  is  either:   ;;  *  a  cube   ;;  *  a  prism   ;;  *  a  sphere   ;;my-­‐3D-­‐shape-­‐fn:  3D-­‐shape  -­‐>  Any   ;(define  (my-­‐3D-­‐shape-­‐fn  data)   ;    (cond  [(cube?  data)  (...(cube-­‐edge  data)...)]   ;                          [(prism?  data)  (...(prism-­‐length  data)...   ;                                                                                ...(prism-­‐width  data)...   ;                                                                                ...(prism-­‐height  data)...)]   ;                          [(sphere?  data)  (...(sphere-­‐radius  data)...)]))     Define  the  constant  PI  for  calculations  involving  the  sphere.   (define  PI  3.14159)     Start  with  the  contract  as  usual.  Use  the  data  definition  of  a  3D -­‐shape  in  the  contract.   ;;  volume:  3D-­‐shape  -­‐>  Number   ;;  Purpose:  consume  a  3D-­‐shape  and  produce  the  volume  of  the  shape     Your  examples  should  show  what  happens  with  each  different  3D -­‐shape.   ;;  Examples:   (check-­‐expect  (volume  (make-­‐cube  3))  27)   (check-­‐expect  (volume  (make-­‐prism  3  4  5))  60)   (check-­‐expect  (volume  (make-­‐sphere  3))  (*  (/  4  3)  PI  (expt  3  3)))     The  function  itself  is  fairly  short.  I  used  the  function  template  for  a  3D -­‐shape  and  filled  in  the  necessary   details.  Remember,  each  structure  has  a  predicate  you  can  use  to  test  whether  you  have  that  structure  or   not  (example:  cube?).     (define  (volume  shape)   (cond                [(cube?  shape)  (expt  (cube-­‐edge  shape)  3)]                  [(prism?  shape)  (*  (prism-­‐length  shape)  (prism-­‐width  shape)  (prism-­‐height  shape))]                  [(sphere?  shape)  (*  (/  4  3)  PI  (expt  (sphere -­‐radius  shape)  3))]))     Make  sure  to  thoroughly  test  each  3D -­‐shape.  Check-­‐within  is  not  usually  used  in  most  programs  in  CS   135  as  these  programs  rarely  deal  with  comparing  inexact  num bers.  To  use  it,  the  answer  you  expect  is   followed  by  the  error  you  allow  in  the  answer.  In  this  case,  my  last  test  allows  the  answer  to  be  between   523.597  to  523.599.   ;;  Tests:   (check-­‐expect  (volume  (make-­‐cube  0))  0)   (check-­‐expect  (volume  (make-­‐prism  0  0  0))  0)   (check-­‐expect  (volume  (make-­‐sphere  0))  0)   (check-­‐expect  (volume  (make-­‐cube  5))  125)   (check-­‐expect  (volume  (make-­‐prism  2  2  2))  8)   (check-­‐within  (volume  (make -­‐sphere  5))  523.598  0.001)             HTDP, Section 9, Question 4: Develop  the  function  string-­‐append-­‐n*,  which  consumes  a  non-­‐empty   list  of  strings  and  produces  a  single  string  resulting  from  appending  all  of  the  strings  together.  Use  the   built-­‐in  function  string-­‐append:  String  String  -­‐>  String,  which  appends  two  strings.   Now  develop  the  more  general  function  string-­‐append*,  which  consumes  any  list  of  strings  and   produces  a  single  string  as  described  above.  This  new  function  must  handle  empty  in  a  reasonable  way.   Be  sure  to  include  the  template  for  list  functions  in  your  code  unless  otherwise  stated.   ;;  my-­‐lst-­‐fn:  (listof  String)-­‐>  Any   ;(define  (my-­‐lst-­‐fn  lst)   ;    (cond  [(empty?  lst)  .  .  .  ]   ;                          [else    .  .  .  (first  lst)  .  .  .   ;                                              .  .  .  (my-­‐lst-­‐fn  (rest  lst))  .  .  .  ]))     The  contract,  purpose  and  examples  are  the  sam e  as  always,  we  just  have  a  new  type  to  use  in  the   contract,  (listof  String).   ;;  string-­‐append-­‐n*:  (listof  String)  -­‐>  String   ;;  Purpose:  append  all  the  strings  in  the  non-­‐empty  list,  strlst,  to  form  one  single  string   This  program  is  fairly  simple  with  regards  to  examples,  as  there  are  really  only  two  things  to  check.  One   is  that  your  program  can  handle  a  general  number  of  strings  with  different  characters  and  spaces,  and   the  other  is  if  your  list  is  of  length  one.   ;;  Examples:   (check-­‐expect  (string-­‐append-­‐n*  (list  "wow  "  "it's  "  "a  "  "sentence"))                              "wow  it's  a  sentence")     This  function  is  recursive.  The  function  does  not  take  an  empty  list,  so  your  base  case  should  look  at  the   result  just  before  a  list  is  empty.  In  this  case,  return  the  last  string  remaining.  There  are  no  other  cases  to   be  considered  except  the  general  case.  For  the  else  part  of  your  cond  expression,  you  append  the  first   string  in  the  list  to  the  recursive  calls.  The  recursive  calls  will  p roduce  more  strings,  and  once  the  base   case  is  reached,  the  function  terminates.   (define  (string-­‐append-­‐n*  strlst)      (cond  [(empty?  (rest  strlst))  (first  strlst)]                  [else  (string-­‐append  (first  strlst)                                                              (string-­‐append-­‐n*  (rest  strlst)))]))     ;;  Tests:   (check-­‐expect  (string-­‐append-­‐n*  (list  "short"))  "short")   (check-­‐expect  (string-­‐append-­‐n*  (list  "  "  "twospaces"  "  "))                              "  twospaces  ")     I  did  not  do  a  contract,  purpose  or  example  for  this  function  since  it  is  quite   similar  to  the  previous   function.  DO  NOT  DO  THIS  unless  specifically  told  you  only  need  certain  parts  of  the  design  recipe.  This   function  can  have  an  empty  list  as  its  argument,  but  is  otherwise  the  same  as  the  previous  function.  The   else  statement  stays  the  same  as  string-­‐append-­‐n*,  but  now  we  need  to  check  if  the  list  is  empty  for  our   base  case.  To  keep  the  function  simple,  return  “”.  This  will  be  accepted  by  string -­‐append  and  will  not   change  the  string  output.  Additionally,  if  the  list  is  empty  to  begin   with,  this  outputs  only  an  empty  string.     (define  (string-­‐append*  strlst)      (cond  [(empty?  strlst)  ""]                  [else  (string-­‐append  (first  strlst)                                                  
More Less

Related notes for CS 135

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