CSE 413 Winter 2002

Assignment 1 Sample Solution

Part I.

1.  
   1. I
   2. (III)
   3. error
   4. II
   5. (say how now)
   6. (how now brown cow)
   7. ((how now) brown cow)
   8. #f
   9. #t
   10. #f
   11. #t
2.   
   
   
   

Part II.

1. define (run-length-decode lst)
      (cond ((null? lst) lst)
            ((number? (car lst))
             (cons (cadr lst)
                (run-length-decode (if (= (car lst) 1)
   	     	         (cddr lst)
   			 (cons (- (car lst) 1)
   			       (cdr lst))))))
            (else (cons (car lst) (run-length-decode (cdr lst))))))
   
   ;; an alternate solution
   
   ;; = return a list containing n copies of a item
   (define (repeat item num-times)
       (if (equal? num-times '0) '() (cons item (repeat item (- num-times 1)))))
   	
   (define (run-length-decode lst)
       (cond ((null? lst) lst)
             ((number? (car lst))
              (append (repeat (cadr lst) (car lst)) 
                      (run-length-decode (cddr lst))))
             (else (cons (car lst) (run-length-decode (cdr lst))))))

2. (define (merge-list lst1 lst2)
      (cond ((null? lst1) lst2)
            ((null? lst2) lst1)
            ((> (car lst1) (car lst2))
             (cons (car lst2) (merge-list lst1 (cdr lst2))))
            ((< (car lst1) (car lst2))
             (cons (car lst1) (merge-list (cdr lst1) lst2)))
            (else (cons (car lst1) (merge-list (cdr lst1) (cdr lst2))))))

3. (define (flatten lst)
      (cond ((null? lst) lst)
            ((pair? lst) (if (pair? (car lst)) 
                             (append (flatten (car lst)) (flatten (cdr lst)))
                             (cons (car lst) (flatten (cdr lst)))))))

4. ;;  true if item appears somewhere in lst
   (define (present? item lst)
      (if (pair? lst)
          (or (present? item (car lst)) (present? item (cdr lst)))
          (equal? item lst)))
   
   (define (path item lst)
   	(if (pair? lst)
             (if (present? item (car lst))
                 (cons 'car (path item (car lst)))
                 (if (present? item (cdr lst))
                     (cons 'cdr (path item (cdr lst)))
                     '()))
                 '()))