C211 Introduction to Computer Science Fall 2000

Assignment 4: More Recursion, Let, and Letrec

Due Sun Sep 24 11:00:00 2000

Reading Assignment

Instructions

Save your solutions to these exercises in a file named a4.ss. Your file MUST be named a4.ss or it will be rejected by the current web-based handin system.

Include the following information as a comment at the top of the file you submit:

Label the parts of your solutions by including problem numbers as comments just before the corresponding Scheme expressions. For each procedure, include a comment that describes what the procedure does (not how it is done).

Test your code on a wide range of inputs. Many of the exercises show sample inputs and the expected results. Use these examples as a starting point. Keep in mind that we will use a wider variety of inputs when grading your assignments.

Save your work often by selecting ``Save Definitions as Text'' from the ``File'' menu. Do not simply click on the Save button. You should save your work on your student locker and on a floppy disk.

When you are ready to hand in your assignment, review the Assignment 1 handin instructions or go directly to the submissions page.

Exercises

  1. We begin with a review of a hand trace of the procedure fact that computes the factorial of a number. Here is a definition of fact:
        (define fact
      (lambda (n)
        (if (zero? n)
             1
            (* n (fact (- n 1))))))
    And here is a hand trace of (fact 2):
        ; (fact 2)
    ;   = (* 2 (fact 1))
    ;   = (* 2 (if (zero? 1) 1 (* 1 (fact (- 1 1)))))
    ;   = (* 2 (* 1 (fact 0)))
    ;   = (* 2 (* 1 (if (zero? 0) 1 (* 0 (fact (- 0 1))))))
    ;   = (* 2 (* 1 1))
    ;   = (* 2 1)
    ;   = 2

    This problem tests your ability to read code and determine what the procedure does with its arguments. Here are the definitions of the procedure mystery and its helping procedure myst-help:

        (define mystery
      (lambda (x ls)
        (cond
          [(null? ls) #f]
          [(equal? (car ls) x) 0]
          [else (myst-help (mystery x (cdr ls)))])))

    (define myst-help
      (lambda (expr)
        (if (not expr)
            #f
            (+ 1 expr))))
    1. As comments in a4.ss, write a hand trace of the procedure call (mystery 'c '(a b c d e)). The final line of the hand trace should be the value returned by the procedure call. You can check your result by running the code in DrScheme.

    2. Also as comments, do a hand trace of the procedure call (mystery 'c '(a b)). Then from the results you have gotten and by running the code for some other arguments, write as comments your verbal description of what the procedure mystery does for any valid arguments.

  2. You work for a credit card company that issues cards to customers. Each card contains an individual identification number having 16 digits. In order to prevent people from using fake credit card numbers, your company has adopted a scheme to test whether the number is a valid number. In fact, all such companies do have some validation scheme for their card numbers. The scheme your company has adopted for its 16-digit numbers is that the sum of the digits should be a multiple of 10. As usual, the first digit of a number can not be zero. You have been given the job of writing a Scheme program to test the validity of a number. You want your procedure valid? to test whether the number has 16 digits and whether the sum of its digits is exactly divisible by 10. Your boss suggests that you first define a helping procedure digit-sum and use it in the definition of valid?. You may define digit-sum either locally or globally. He also insists that for efficiency the procedure you define does not use the procedure length. Here are examples of some sample imputs for valid?:
       > (valid? 2135340034971134)
   #t
   > (valid? 5437651012035600)
   #f
   > (valid? 212324759860048)
   #f
   > (valid? 55503988104811002)
   #f

  3. Define a procedure named inventory-pockets that takes a list of symbols representing the contents of someone's pockets and returns the total value (in cents) of the coins found. Your procedure should skip over any symbols that do not correspond to common U.S. coinage: penny, nickel, dime, and quarter. (Hint: it may be handy to define a helping procedure that takes any symbol and returns its value (or zero if none) in cents.)

    Here are some sample inputs to try.

       > (inventory-pockets '())
   0
   > (inventory-pockets '(penny))
   1
   > (inventory-pockets '(nickel penny))
   6
   > (inventory-pockets '(dime nickel penny))
   16
   > (inventory-pockets '(quarter dime nickel penny))
   41
   > (inventory-pockets '(lint toad pen-knife))
   0
   > (inventory-pockets
       '(penny
          quarter
          ticket-stub
          dime
          receipt
          quarter
          gum-wrapper
          nickel
          penny
          string))
   67
  4. Define a procedure named change that takes a nonnegative integer and returns a list of symbols representing coins whose values sum to the given integer. In other words, your procedure should take a number and return a list of coins that equals that amount in change. Use only the coin symbols: quarter, dime, nickel, and penny.

    The list you return may contain duplicates (more than one penny, for example), but should contain the least number of coins possible. Thus returning a list containing n occurrences of penny is not acceptable if n is greater than 4.

    In this exercise we want you to compute the list one coin at a time. For example, if you need more than one quarter to make change, just cons one quarter on and let recursion take care of any remaining quarters. (We could be a bit more clever using quotient and remainder.)

    Tips: If you use cond, pay attention to the order of the clauses. Pay attention to computation of the argument for each recursive call. Beware of cut-and-paste bugs.

    Here are some examples.

       > (change 0)
   ()
   > (change 1)
   (penny)
   > (change 30)
   (quarter nickel)
   > (change 41)
   (quarter dime nickel penny)
   > (change 14)
   (dime penny penny penny penny)
   > (change 99)
   (quarter quarter quarter dime dime penny penny penny penny)
   > (change 123)
   (quarter
     quarter
     quarter
     quarter
     dime
     dime
     penny
     penny
     penny)
  5. If the sides of a triangle have lengths a, b, and c, the area of the triangle is computed by taking the square root of
        s*(s-a)*(s-b)*(s-c),
    where s is given by
        (a+b+c)/2.
    Define a procedure triangle-area that takes three positive numbers representing the side lengths of a triangle, and returns the area of the triangle. Make use of a let to avoid the recomputation of s.

    However, not all values of a, b, and c represent valid triangles. Your procedure should verify that the given lengths are all positive, and that every combination of two sides is longer than the remaining side. That is, a+b must be greater than c, and a+c must be greater than b, and b+c must be greater than a. If the inputs to triangle-area do not define a valid triangle, then signal an error using the appropriate Scheme error expression, to generate the messages illustrated in the examples. Unfortunately, even though Chez Scheme and DrScheme use the same error syntax, they write the messages to the screen in slightly different ways. This error expression

        (error 'proc-name "expects a number, got ~s" 'monkey)
    prints this message in Chez Scheme:
        Error in proc-name: expects a number, got monkey.
    whereas, DrScheme prints it this way:
        proc-name: expects a number, got monkey

    You should use the Scheme sqrt procedure. Also, remember that you can always define and use helping procedures to make your code more readable.

       > (triangle-area 3 4 5)
   6
   > (triangle-area 1 1 2)
   Error in triangle-area: 2 >= (+ 1 1).

   > (triangle-area 0 2 2)
   Error in triangle-area: side 0 is not positive.

   > (triangle-area -3 -4 -5)
   Error in triangle-area: side -3 is not positive.
  6. Define a procedure all-same? that takes a list, ls, and returns #t if all top-level elements of ls are the same, and #f otherwise. Although the predicate all-same? could be defined in terms of if or cond, you are to use only the logical operators not, or, and and in your solution to this exercise. You may, of course, use help procedures provided they too are defined without the use of if or cond. You can see some additional examples in Exercise 2.2 on Page 57 of Scheme and the Art of Programming.
       > (all-same? '(cat cat cat cat))
   #t
   > (all-same? '(cat cat dog cat cat))
   #f
   > (all-same? '(kitten))
   #t
   > (all-same? '())
   #t

  7. The procedure remove-1st takes a Scheme object item, and a list, ls, and returns a list containing all of the members of ls except the first occurrence of item. The definition of remove-1st is given here: (See also Program 2.4 on Page 52 of Scheme and the Art of Programming)
        (define remove-1st
      (lambda (item ls)
        (cond
          [(null? ls) '()]
          [(equal? (car ls) item) (cdr ls)]
          [else (cons (car ls) (remove-1st item (cdr ls)))])))
    Your problem now is to define a procedure remove-2nd that removes only the second occurrence of a given item from a given list. You may use remove-1st in your solution, but include it as a locally defined procedure within the definition of remove2nd. Note: Look at Exercise 2.17 on Page 56 of Scheme and the Art of Programming for more examples.

       > (remove-2nd 'sea '(she sells sea shells on the sea shore))
   (she sells sea shells on the shore)
   > (remove-2nd 'sea '(she sells shells on the sea shore))
   (she sells shells on the sea shore)
   > (remove-2nd 'hello '(hello 1 hello 2 hello 3))
   (hello 1 2 hello 3)
   > (remove-2nd 'anything '())
   ()

Checklist

Check to make sure you haven't skipped any of the exercises. Be sure you include the hand traces in the first problem.

Your file should contain definitions for: valid?, inventory-pockets, change, triangle-area, all-same?, and remove-2nd.

When you're all done, review the submission instructions.