CS212 Exams
Spring 1997 - Prelim 1

Analysis of Algorithms

Consider again the code for computing all the unordered pairs of the elements in a list. 
(define (all-pairs lst)
  (cond
    ((empty? (tail lst)) empty)
    ((empty? (tail (tail lst))) (list lst))
    (else (append (pair-with-list (head lst) (tail lst))
                  (all-pairs (tail lst))))))

making use of the helper procedure 

(define (pair-with-list elt lst)
  (if (empty? lst)
    empty
    (cons (list elt (head lst))
          (pair-with-list elt (tail lst)))))
  1. How many unordered pairs are there for a list of length n? Briefly justify your answer.





  2. Is the process generated by the all-pairs procedure iterative or recursive?




  3. What is the order of growth of the running time of the all-pairs procedure as a function of the length n of lst? Recall that the append procedure requires time proportional to the length of its first argument; that is, (append l1 l2) takes O(n) time where n is then length of l1. Briefly justify your answer.







Solution

Return to CS 212 Prelim 1 - Spring 1997