Sample exam 2

Recursion problems

Problem 1

Consider the roman-sum procedure from Appendix B of the case study. It has two base cases; one tests for an empty number sentence, the other for a sentence of length 1. In the case study, however, we assumed that the argument represented a legal Roman numeral and was therefore nonempty. Suppose we omitted the first base case, recoding roman-sum as

(define (roman-sum number-sent)
  (cond
    ((empty? (bf number-sent)) (first number-sent))
    ((not (starts-with-prefix? number-sent))
     (+ (first number-sent) (roman-sum (bf number-sent)) ) )
    ((starts-with-prefix? number-sent)
     (+
       (- (first (bf number-sent)) (first number-sent))
       (roman-sum (bf (bf number-sent))) ) ) ) )

Indicate which of the following is true, and explain your choice.

  1. The revised procedure still works correctly.
  2. The revised procedure will crash for some sentences representing legal Roman numerals (describe all such sentences below, and explain how it crashes).
  3. The revised procedure will not crash. It will, however, produce the wrong result value for some sentences representing legal Roman numerals (describe all such sentences below).

Your choice:

Explanation:

Problem 2

Part a

Supply the arguments to the recursive helper calls in the following version of the dupls-removed procedure you wrote for for an early recursion exercise. Recall that dupls-removed returns the result of removing duplicate words from a sentence; for example, given (A B A), it should return (A B) or (B A).

Your code should maintain the order of the list elements that aren't removed; for example, (dupls-removed '(A B C)) should return (A B C).

(define (dupls-removed sent)
  (helper sent '( )) )
 
(define (helper sent so-far)
  (cond
    ((empty? sent) so-far)
    ((member? (first sent) (butfirst sent))
     (helper 
       __________________________________
       __________________________________  ) )
    (else
     (helper 
       __________________________________
       __________________________________  ) ) ) )

Part b (graded only if part a is essentially correct)

Use your code to evaluate the expression

(dupls-removed '(A B C B))

and give the result below.

Higher-order procedures problems

Problem 3

Identify, as descriptively and accurately as possible, the type of value returned by each procedure below. Assume that the argument for each procedure is a sentence of triples that could be produced by a call to find-triples. (The first-if-any and pivots procedures appear in the Tic-Tac-Toe program.)

Possible types include but are not limited to a triple, a sentence of triples, a square number (1, 2, ..., 9), and a player (x or o). You will lose points for an insufficiently descriptive identification, for instance by saying "an integer" instead of a "square number".

procedure

result type

(define (f1 triples)
  (keep 
    (lambda (t) (not (number? t)))
    (every first triples) ) )

(define (f2 triples)
  (first-if-any (pivots triples 'x)) )

Problem 4

A CS 3 student proposes to code roman-sum as follows:

(define (roman-sum number-sent)
  (accumulate
    (lambda (n so-far)
      (if (< n so-far)   ; is n a prefix?
        (- so-far n)
        (+ so-far n) ) )
    number-sent) )
Unfortunately, this procedure is flawed.

Part a

Give a value for number-sent that represents a legal Roman numeral and for which the procedure above returns the wrong answer.

Part b

Describe, as completely as possible, the set of Roman numerals that, when translated to integers and passed as an argument to roman-sum, result in roman-sum returning the wrong answer.

Problem 5

Consider a hand of cards in the following format. Each card in the hand is a word whose first letter specifies the card's suit (s for spade, h for heart, d for diamond, c for club) and whose butfirst specifies the card's rank (one of a, 2, ..., 10, j, q, or k).

Fill in the blanks in the procedure below so that its return value is a sentence of the ranks of all the cards in the hand of the given suit. Examples:
expression desired value
(ranks '(sq ha c10 h4 sk s3) 's) (q k 3)
(ranks '(sq ha c10 h4 sk s3) 'h) (a 4)
(ranks '(sq ha c10 h4 sk s3) 'd) ( )
(ranks '(sq ha c10 h4 sk s3) 'c) (10)
The blanks numbered 1 and 3 should each be filled in with the name of a higher-order procedure. Use placeholder names that are as descriptive as possible.

(define (ranks hand suit)
  ( __________________  ; blank #1 (a higher-order procedure name)
      _________________ ; blank #2
    ( __________________ ; blank #3 (a higher-order procedure name)
        _________________ ; blank #4
        hand) ) )