Instructions

1. This is a closed-notes, closed-book exam.
2. You will not be penalized on trivial syntax errors, such as a missing parenthesis. Multiple errors or errors that lead to ambiguous code will have points deducted, however.
3. In all of the questions, feel free to write additional helper methods to get the job done.
4. The emphasis is on correctness of the code, not efficiency or on simply generating the right result.
5. Use the back of the sheet the question is on if you need additional space.
6. You may write your functions using either forward or reverse accumulation unless otherwise directed.

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?

Answer:

The design template will reflect the base case and inductive cases of the recursive data structure. The recursive call will be accepted as part of an answer, though it technically is not required by 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?

Answer:

The design template, for the most part, represents invariant code because it is used over and over again, independent of what the function on that data does.

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!!

Answer:

It violates the encapsulation of the mood structure by 1) checking for the actual type of mood and 2) by then pulling out the internal data of a mood.

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 than or equal to 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.

Answer:

(define (divisorsOf divisee maxDivisor)

(cond

[(zero? maxDivisor) empty]

[(< 0 maxDivisor)

(cond

[(= 0 (modulo divisee maxDivisor))

(cons maxDivisor (divisorsOf divisee (sub1 maxDivisor)))]

[else (divisorsOf divisee (sub1 maxDivisor))])]))

Note: forward accumulation solutions exist, see the DrScheme solution file.

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.

Answer:

;; A LoTN represents all the names in all the teams and is either

;; - empty

;; - (cons TN LoTN)

(define (f-LoTN a-LoTN …)

(cond

[(empty? a-LoTN) …]

[(cons? a-LoTN) …(f-TN (first a-LoTN)…)…

(f-LoTN (rest a-LoTN)…)…]))

;; A TN (team names) is a list of the names on a single team and is either

;; - empty

;; - (cons sym TN), where sym is symbol representing the name of a person.

(define (f-TN a-TN …)

(cond

[(empty? a-TN) …]

[(cons? a-TN) …(first a-TN)…(f-TN (rest a- TN)…)…]))

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

Answer:

(define (sameNameTN a-TN a-name)

(cond

[(empty? a-TN) 0]

[(cons? a-TN) (+ (cond

[(symbol=? a-name (first a-TN)) 1]

[else 0])

(sameNameTN (rest a-TN) a-name ))]))

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

Answer:

(define (sameNameLoTN a-LoTN a-name)

(cond

[(empty? a-LoTN) 0]

[(cons? a-LoTN) (+ (sameNameTN (first a-LoTN) a-name)

(sameNameLoTN (rest a-LoTN) a-name))]))

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”).

Answer:

(define (f-lod a-lod …)

(cond

[(cons? a-lod) …(first a-lod)…(f-lonatnum (rest a-loa) …)…]))

n the cond statement is optional.

n NO empty case – a lod is a non-empty list!

n Helper functions are not part of the template.

n Note the function on rest is not a f-lod because rest is not a 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.

Answer:

(define (valueOf a-lod)

(valueOf_help (rest a-lod) (first a-lod))) ;; follows template

;; valueOf_help: list-of-natnum natnum à natnum

;; Returns the given value times 10 to power of the number of elements in

;; the a-lonn, plus the value of the number represented by the a-lonn.

(define (valueOf_help a-lonn value)

(cond

[(empty? a-lonn) value]

[(cons? a-lonn) (valueOf_help (rest a-lonn) (+ (* value 10)(first a-lonn)))]))

· Helper function follows template for a list of natnums, not a lod because rest is a lonn, not a lod.

· Notice that a new value of the accumulator is calculated for the recursive call.

· Notice that the helper is tail-recursive.