Problem Set 2 Key, CS 257

  1. Do the following problems from the book:

    4.4
    4.8

    ;;; easy way
    (define (scientific a b) (* a (expt 10 b)))
    
    ;;; scheme-in-your-blood way
    (define (scientific a b)
       (cond ((= b 0) a)
             ((< b 0) (/ (scientific a (+ b 1)) 10))
             ((> b 0) (* (scientific a (+ b 1)) 10))))
    
    4.10
    (define (tip x)
       (- (ceiling (* x 1.15)) x))
    
    5.12

    All of them! Each of these returns an empty word:

    (first '("" two three))
    (last '(one two ""))
    (butfirst 'a)
    (butlast 'a)

    5.13

    ''banana stands for (quote (quote banana))

    (first ''banana) is the same as (first '(quote banana)), so it returns the first word of the sentence (quote banana), ie quote.

    5.14

    (define (third x) (first (butfirst (butfirst x))))
    
    5.20
    (define (middle-names x) (butfirst (butlast x)))
    
    6.1
    6.3
    ;;; two equivalent definitions:
    
    (define (sign number)
      (if (< number 0)
          'negative
          (if (= number 0)
              'zero
              'positive))))
    
    (define (sign number)
      (cond ((< number 0) 'negative)
            ((= number 0) 'zero)
            (else 'positive)))
    
    6.5
    (define (european-time x)
      (cond ((equal? x '(12 am)) 24)
            ((equal? x '(12 pm)) 12)
            (else (+ (first x)
                     (if (equal? (last x) 'am) 0 12)))))
    
    (define (american-time x)
      (cond ((= x 0) '(12 am))
            ((= x 24) '(12 am))
            ((= x 12) '(12 pm))
            ((< x 12) (sentence x 'am))
            (else (sentence (- x 12) 'pm))))
    
    6.11
    ;;; The most interesting problem here was testing to see if a date is valid.
    
    ;;; Here are two solutions: with vs without helper functions.
    
    ;;; MONOLITHIC SOLUTION:
    
    (define (divisible? big small)
      (= (remainder big small) 0))
    
    (define (valid-date? month day year)
      (and (>= day 1)
           (or
    	(and (= month 1) (<= day 31))
    	(and (= month 2) (or (<= day 28)
    			     (and (= day 29)
    				  (divisible? year 4)
    				  (or (not (divisible? year 100))
    				      (divisible? year 400)))))
    	(and (= month 3)  (<= day 31))
    	(and (= month 4)  (<= day 30))
    	(and (= month 5)  (<= day 31))
    	(and (= month 6)  (<= day 30))
    	(and (= month 7)  (<= day 31))
    	(and (= month 8)  (<= day 31))
    	(and (= month 9)  (<= day 30))
    	(and (= month 10) (<= day 31))
    	(and (= month 11) (<= day 30))
    	(and (= month 12) (<= day 31)))))
    
    
    ;;; MODULAR SOLUTION:
    
    (define (valid-date? month day year)
      (and (<= 1 month 12)
           (<= 1 day (days-in-month month year))))
    
    (define (days-in-month month year)
    
      (cond ((or (= month 9)		; 30 days hath September,
    	     (= month 4)		; April,
    	     (= month 6)		; June,
    	     (= month 11)) 30)		; and November
    
    	((= month 2)			; except for february,
    	 (if (leap-year? year) 29 28))	; which has 28, 29 on leap years
    
    	(else 31)))			; all the rest have 31
    
    (define (leap-year? year)
      (and (divisible? year 4)
           (or (not (divisible? year 100))
    	   (divisible? year 400))))
    
    ;;; Note that the LEAP-YEAR? predicate might come in handy elsewere,
    ;;; eg an astronomy package that needs to know whether some year has 365
    ;;; or 366 days.  Similarly the DAYS-IN-MONTH function might be useful
    ;;; for say an accounting package, or a program that prints calendars.
    ;;;
    ;;; This is one criterion for good helper functions: do they make
    ;;; sense independently!
    

  2. Define a function harmonic which computes the sum of the first n elements of the harmonic series:

    (harmonic 0) = 0
    (harmonic 1) = 1/1 = 1
    (harmonic 2) = 1/1 + 1/2 = 1.5
    (harmonic 5) = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 = 2.2833333


    (define (harmonic n)
      (if (= n 0) 0
          (+ (/ 1 n) (harmonic (- n 1)))))
    

  3. Define a procedure (bopper side) which uses the turtle to draw a picture like that below, with the argument to the function being the length of the first upstroke.

    (define (bopper side)
      (cond ((> side 1)
    	 (move side)
    	 (turn 120)
    	 (move side)
    	 (turn -120)
    	 (bopper (* side 0.7)))))
    

  4. Define a procedure circle-sentence which takes a sentence and draws its words on the edge of a circle (or really an n-gon for some large n). For instance, doing
    (circle-sentence '(we can meet at your convenience my sweet little sugar plum))
    should result in something like this:

    (define (circle-sentence s)
      (cond ((not (empty? s))
    	 (write (first s))
    	 (move 50)
    	 (turn 10)
    	 (circle-sentence (butfirst s)))))
    

Barak Pearlmutter <bap@cs.unm.edu>