CSci 1901 Spring 2006


Practice Midterm for Midterm #1
Thursday, February 15
50 minutes == 50 points
Open book and notes

  1. (10 points)

    Show the values of the indicated expressions, assuming all the expressions are evaluated in order.

    (define a (cons 3 (cons 2 (list 4))))
    (define (foo x) (cons (car x) '()))
    a $\Longrightarrow$
    (cadr a) $\Longrightarrow$
    (cons 5 '()) $\Longrightarrow$
    (list 5) $\Longrightarrow$
    (foo a) $\Longrightarrow$
    (let ((z (cadr a)))
    (cons 5 z)) $\Longrightarrow$
    ((lambda (x) (cons 6 x)) '(8)) $\Longrightarrow$
    ((lambda (x y) (* x (+ 1 y))) 4 2) $\Longrightarrow$

  2. (4 points)

    Write a predicate (multipleof5? x) that returns #T if x is a multiple of 5 and #F otherwise. It should work like this:

      (multipleof5? 7) should return #F
          since 7 is not a multiple of 5
      (multipleof5? 35) should return #T
          since 35 is a multiple of 5
     

  3. (10 points)

    Write a predicate (list-not-multipleof5 low high), where low and high are respectively the lower and the higher limit of an interval. The predicate should return the elements in the interval low to high that are not multiple of 5. Assume that low and high are positive integers and that ${\tt low} \le {\tt high}$. It should work like this:

      (list-not-multipleof5 2 6) should return (2 3 4 6)
          since these are in the interval and are not multiple of 5
      (list-not-multipleof5 11 11) should return (11)
          since 11 is not a multiple of 5
      (list-not-multipleof5 10 10) should return ()
          since no element in the interval is not a multiple of 5

  4. (10 points)

    Write a procedure that takes a list as an argument and returns the list with each element divided by 2. It should work like this:

      (half '(2 4 8)) should return (1 2 4)
      (half '(1)) should return (0.5)
      (half '(10 20)) should return (5 10)
      (half '()) should return ()

  5. (10 points)

    Write a predicate (some? pred l) that returns #T if any element of the list l satisfies the predicate pred, and #F otherwise. It should work like this:

      (some? odd? (list 2 6 3 8)) should return #T
          since 3 is an odd number
      (some? divisibleby5? (list 1 17 32)) should return #F
          since no element in the list is exactly divisible by 5

  6. (6 points)

    What is the difference in the cost between the following two definitions of the modular exponentiation function expmod? Which version below has fewer operations? Which version has smaller intermediate numbers? Explain. [Hint: consider the computation of (expmod 10000 7777 3)]

    (a)  (b)
    (define (expmod base exp m)
      (modulo (expt base exp) m))
    
    (define (expt base exp)
      (if (= exp 0)
          1
          (* base
             (expt base (- exp 1)))))
    
     
    (define (expmod base exp m)
      (if (= exp 0)
          1
          (modulo
            (* base (expmod base (- exp 1) m))
            m)))