Instructions
Please write and sign the Rice Honor
Pledge here:
1.
(10 pts total) Design
Templates:
2-3
sentences maximum!!
a.
(5 pts) Consider the design template that one derives
from a recursive (composite)
data structure. What major features particular to a recursive data
structure are reflected in the design template?
b. (5 pts) Again consider the design template of a recursive data structure. For the most part, does the template represent variant or invariant code? Why?
2.
(10 pts) Critiquing existing code: Consider the following data definitions:
;; A person is a structure a name and a mood ;; where name is a string and mood is a mood
structure ;; (make-person name mood) (define-struct person (name mood)) ;; Examples (define person1 (make-person “Ziggy” (make-happy
“What a beautiful day!”))) (define person2 (make-person “C. Manson”
(make-angry “Helter-skelter!”))) |
|
A mood is either -- happy -- angry |
|
;; happy is a structure that ;; has a greeting ;; where greeting is a string ;; (make-happy greeting) (define-struct happy (greeting)) ;; Example: (make-happy “Howdy!”) |
;; angry is a structure that ;; has a snarl ;; where snarl is a string ;; (make-angry snarl) (define-struct angry (snarl)) ;; Example: (make-angry “Get out of my face!”) |
Consider the following function:
;; converseWith:
person à string
;; Models
a conversation with the given person, a-person,
;;
and returns a string response corresponding to their mood.
(define
(converseWith a-person)
(cond
[(happy? (person-mood a-person)) (string-append
“Hi, my name is “
(person-name a-person) “! “
(happy-greeting (person-mood a-person)))]
[(angry? (person-mood a-person)) (string-append (angry-snarl (person-mood
a-person)))]))
"converseWith
test cases: (uses definition from the
above table)"
(string=?
“Hi, my name is Ziggy! What a beautiful day!” (converseWith person1))
(string=?
“Helter-skelter!” (converseWith person2))
Even though the above function always yields the correct results, do you see anything wrong or improper with its code body? If so, please explain clearly and completely what you feel is improperly implemented about this code and why it is improper. Assume that you are given the data definitions as well as the contract, purpose and header for the function and thus have no control over them.
2-3 sentences maximum!!
3. (20 pts) Natural Numbers: Write the following function. The contract, purpose, header and test cases are given below.
;;
divisorsOf: natnum natnum à
list-of-natnum
;;
Returns all the divisors of divisee less than or equal to maxDivisor
;;
including 1 and divisee, if it is less or equal to than maxDivisor.
(define
(divisorsOf divisee maxDivisor) …) ;; finish this below
"divisorsOf
test cases"
(equal?
empty (divisorsOf 5 0))
(equal?
(list 3 2 1) (divisorsOf 0 3))
(equal?
(list 10 5 2 1) (divisorsOf 10 10))
(equal?
(list 2 1) (divisorsOf 10 4))
(equal?
(list 12 6 4 3 2 1) (divisorsOf 12 48))
Hint: (modulo divisee divisor) returns 0 if divisor divides divisee evenly.
(define
(divisorsOf divisee maxDivisor) ;; fill in the rest.
4. (35 pts total) List of Lists: Consider a list that contains lists. For example, suppose we had the names of each person in a number of different teams. We’ll call this a list of team names or “LoTN” Here is an example, where the names are symbols:
(define myLoTN (list (list
‘John ‘Mary ‘Bubba)
(list ‘Moe ‘Curly ‘Larry
‘Shemp)
empty
(list ‘Stephen)
(list ‘Bubba ‘John ‘Kilroy
‘George_Dubya ‘John)))
Note that empty and (cons
empty empty) are
both examples of a LoTN as well. Multiple occurrences of
a name mean that multiple people have the same name.
THINK SIMPLY!! Don’t make the same type of mistake as shown in Problem #2!
a. (15 pts) Write the data definitions and templates for a list of team names (LoTN) where team names (TN) is a list of names (symbols) of the people in a team. Be sure to also write the data definitions for any structures that LoTN may contain. Assume the function is recursive and include anything additional that can be said about recursive functions on these data types.
b. (10 pts) Write the following function on a team names (TN) structure. Follow your template!
;; sameNameTN: TN sym à num
;; Returns the number of
times the given name, a-name, appears
;; in the given team names
structure, a-TN.
(define (sameNameTN a-TN a-name)
…) ;; finish this below
"sameNameTN test
cases:"
(= 0 (sameNameTN empty
‘John))
(= 0 (sameNameTN (list
‘Sally ‘Wendy) ‘Pocahontas))
(= 1 (sameNameTN (list ‘Batman
‘Curly ‘Robin) ‘Curly))
(= 2 (sameNameTN (list
‘Bubba ‘Roy ‘Yokum ‘Bubba) ‘Bubba))
(define
(sameNameTN a-TN a-name) ;; fill in the rest
c. (10 pts) Write the following function on a list of team names (LoTN). Follow your template(s)!
;; sameNameLoTN: LoTN sym à
num
;; Returns the number of times
the given name, a-name
;; appears in the given LoTN,
a-LoTN
(define (sameNameLoTN a-LoTN
a-name) …) ;; finish this below
(define myLoTN (list (list ‘John ‘Mary
‘Bubba)
(list ‘Moe ‘Curly ‘Larry
‘Shemp)
empty
(list ‘Stephen )
(list ‘Bubba ‘John ‘Kilroy
‘George_Dubya ‘John)))
"sameNameLoTN test
cases:"
(= 0 (sameNameLoTN empty
‘John))
(= 0 (sameNameLoTN myLoTN ‘Pocahontas))
(= 1 (sameNameLoTN myLoTN ‘Curly))
(= 2 (sameNameLoTN myLoTN ‘Bubba))
(= 3 (sameNameLoTN myLoTN ‘John))
(define
(sameNameLoTN a-LoTN a-name) ;;
fill in the rest
5. (25 pts total) Forward Accumulation: Consider the following notions about our base 10 placeholder system of writing numbers and the values that they represent:
6328
= 632*10 + 8
= (63*10 + 2)*10 + 8
= ((6*10 + 3)*10 + 2)*10 + 8
= (((6)*10 + 3)*10 + 2)*10 + 8
That is, the value of a number is the value of the
right-most digit plus 10 times the value of the rest of the left-side digits as
a single number. Notice how the evaluation of the digits proceeds from left to right. In general:
If a number is represented by the digits a, b,
c … y, z, then
the value of the number represented by writing “abc…yz” is given by:
abc…yz = (abc…y)*10 + z where the value of “abc…y” is recursively defined.
Suppose we are given a list of the digits, where the
digit corresponding to the largest placeholder is at the top of the list. For example:
List-of-digits |
Value |
(list
3 5 1) |
351 |
(list
8 0 4 2) |
8042 |
The data definition for a
list of digits is thus:
;;
A list-of-digits, “lod,” represents the digits of a natural number
;; and
is defined as
;;
(cons digit list-of-natnum)
a. (5 pts) Write the design template for a list-of-digits (“lod”).
b. (20
pts) Write the following function on a list of digits:
;; valueOf: list-of-digits à natNum
;; Returns the value of the represented by
;; the given list-of-digits, a-lod.
(define (valueOf a-lod)
…) ;; finish this below.
Test
cases:
(= 42 (valueOf (list 4 2)))
(= 503 (valueOf (list 5 0
3)))
(= 3170
(valueOf (list 3 1 7 0)))
Use forward
accumulation to write this function.
Be sure to follow your own
template!
Be sure to write the contract and
purpose for any helper functions you write. You may omit the test cases. Note:
this is not a recursive function on a natural number!
(define
(valueOf a-lod)
;; fill in the rest, plus any additional functions needed.