CS 61A: Quiz 2

Due by 11:59pm on Thursday, 11/6

Instructions: Download, complete, and submit the quiz2.scm starter file before the deadline above. You must work alone, but you may talk to the course staff (see Asking Questions below). You may use any course materials, including an interpreter, course videos, slides, and readings. Please do not discuss these specific questions with your classmates, and do not scour the web for answers or post your answers online.

Submit with submit quiz2. You may submit more than once before the deadline; only the final submission will be scored. See Lab 1 for submission instructions.

Your submission will be graded automatically for correctness. Your implementations do not need to be efficient, as long as they are correct.

Asking Questions. If you believe you need clarification on a question, make a private post on Piazza. Please do not post publicly about the quiz contents. If the staff discovers a problem with the quiz or needs to clarify a question, we will email the class via Piazza. You can also come to office hours to ask questions about the quiz or any other course material, but no answers or hints will be provided in office hours.

Readings: You might find the following references useful:

Table of Contents

Scheme does not have a built-in testing framework. To verify behavior, we will use the following assert-equal procedure, which tests whether an expression evaluates to an expected value.

(define (assert-equal value expression)
  (if (equal? value (eval expression))
    (print 'ok)
    (print (list 'for expression ':
                 'expected value
                 'but 'got (eval expression)))))

When you evaluate your solution, a long sequence of ok should be displayed. Any test failures will describe the error instead.

Question 1

(1 point) Implement equal-answer, which takes two single-argument procedures f1 and f2 and returns a procedure that takes one argument x. This returned procedure will return true (#t) if f1 and f2 return equal values when called on argument x and false (#f) otherwise.

Assume that the input procedures f1 and f2 always take and return numbers. Test for equality using the = procedure.

(define (equal-answer f1 f2)
  'YOUR-CODE-HERE  (lambda (x) 'replace-this))

(define (test-equal-answer)
  (print (list 'testing 'equal-answer))
  ; (add-two 2) evaluates to 4, (square 2) also evaluates to 4
  (assert-equal true  '((equal-answer add-two square) 2))
  ; (add-two 3) evaluates to 5, (square 3) instead evaluates to 9
  (assert-equal false '((equal-answer add-two square) 3))

  )

(test-equal-answer)

Question 2

(1 point) Implement num-adjacent-matches, which takes as input a list of numbers s and returns the number of adjacent elements that are equal.

(define (num-adjacent-matches s)
  'YOUR-CODE-HERE  'replace-this)

(define (test-num-adjacent-matches)
  (print (list 'testing 'num-adjacent-matches))
  ; no pairs
  (assert-equal 0 '(num-adjacent-matches '(1 2 3 4)))
  ; one pair of 1's
  (assert-equal 1 '(num-adjacent-matches '(1 1 2 3)))
  ; one pair of 1's, one pair of 2's
  (assert-equal 2 '(num-adjacent-matches '(1 1 2 2)))
  ; three pairs of 1's
  (assert-equal 3 '(num-adjacent-matches '(1 1 1 1)))

  )

(test-num-adjacent-matches)

Question 3

(2 points) Implement tally, which takes a list of names and returns a list of pairs, one pair for each unique name in names. Each pair should contain a name and the number of times that the name appeared in names. Each name should appear only once in the output, and the names should be ordered by when they first appear in names.

Hint: Use the eq? procedure to test if two names are the same.

(define (tally names)
  'YOUR-CODE-HERE  'replace-this)

(define (test-tally)
  (print (list 'testing 'tally))
  (assert-equal '((obama . 1))
                '(tally '(obama)))
  (assert-equal '((taft . 3))
                '(tally '(taft taft taft)))
  (assert-equal '((jerry . 2) (brown . 1))
                '(tally '(jerry jerry brown)))
  (assert-equal '((jane . 5) (jack . 2) (jill . 1))
                '(tally '(jane jack jane jane jack jill jane jane)))
  (assert-equal '((jane . 5) (jack . 2) (jill . 1))
                '(tally '(jane jack jane jane jill jane jane jack)))

  )

Hint: You may want to use apply-to-all and keep-if in your solution.

(define (apply-to-all fn s)
  (if (null? s) nil
      (cons (fn (car s))
            (apply-to-all fn (cdr s)))))

(define (keep-if fn s)
  (cond ((null? s) nil)
        ((fn (car s)) (cons (car s)
                            (keep-if fn (cdr s))))
        (else (keep-if fn (cdr s)))))

Partial Credit: One way to implement tally is to first find the list of unique elements in names and then count each one. You are not required to implement tally in this way, but 1 point of partial credit will be given for a correct implementation of unique that returns the elements in the order that they first appear in names.

; Using this helper procedure is optional. You are allowed to delete it.
(define (unique s)
  'YOUR-CODE-HERE  'replace-this)

; Using this helper procedure is optional. You are allowed to delete it.
(define (count name s)
  'YOUR-CODE-HERE  'replace-this)

; Passing these tests is optional. You are allowed to delete them.
(define (test-tally-helpers)
  (print (list 'testing 'unique))
  (assert-equal '(jane)  '(unique '(jane jane jane)))
  (assert-equal '(jane jack jill)  '(unique '(jane jack jane jack jill jane)))
  (assert-equal '(jane jack jill)  '(unique '(jane jack jane jill jane jack)))

  (print (list 'testing 'count))
  (assert-equal 3 '(count 'jane '(jane jane jane)))
  (assert-equal 0 '(count 'jill '(jane jane jane)))
  (assert-equal 2 '(count 'jack '(jane jack jane jack jill jane)))
  )

(test-tally-helpers)
(test-tally)