Sample Questions: SICP Section 1.2

Procedures and Processes

Concept: linear recursion and iteration

  1. One hallmark of an iterative process is that it:
    1. does not exhibit recursion
    2. executes in constant space
    3. uses a while loop or a for loop
    4. cannot be implemented in functional languages
  1. What kind of process does the following function implement?
        (define (f x)
            (if (< x 1)
                1
                (* (+ x 1) (f (- x 1)))
                )
            )
    
    1. syntactically non-tail recursive, so recursive
    2. syntactically tail recursive, so iterative
    3. syntactically tail and non-tail recursive, overall recursive
    4. syntactically tail and non-tail recursive, overall iterative
  1. What kind of process does the following function implement?
        (define (f x y z)
            (cond
                ((= x 1) (* y z))
                ((= (% x 2) 0) (f (/ x 2) (* y 2) z))
                (else (f (- x 1) y (+ z x)))
                )
            )
    
    1. syntactically non-tail recursive, so recursive
    2. syntactically tail and non-tail recursive, overall recursive
    3. syntactically tail and non-tail recursive, overall iterative
    4. syntactically tail recursive, so iterative
  1. TQ: What kind of process does the following function implement?
        (define (f x y z)
            (cond
                ((= x 0) (* y z))
                ((< x 5) (f y z (+ x 7))
                ((< x 10) (+ y (* 2 z) (f (- x 1) y z)))
                (else x)
                )
            )
    
    1. syntactically tail recursive, so iterative
    2. syntactically non-tail recursive, so recursive
    3. syntactically tail and non-tail recursive, overall iterative
    4. syntactically tail and non-tail recursive, overall recursive
  1. What kind of process does the following function implement?
        (define (f n a b)
            (cond
                ((= b (+ a 1)) 'ok)
                ((= b (+ a 2)) (swap n a (+ a 1)))
                (else
                    (f n a (integer (* (+ a b) 0.666)))
                    (f n (integer (* (+ a b) 0.333) b))
                    (f n a (integer (* (+ a b) 0.666)))
                    )
                )
            )
    
    1. syntactically tail and non-tail recursive, overall recursive
    2. syntactically non-tail recursive, so recursive
    3. syntactically tail recursive, so iterative
    4. syntactically tail and non-tail recursive, overall iterative
  1. What kind of process does the following function implement?
        (define (f n z)
            (cond
                ((= n 0) z)
                ((< n 3) (* z (f (- n 1) (+ z 1))))
                (else (f (- n 1) (* n z)))
                )
            )
    
    1. syntactically non-tail recursive, so recursive
    2. syntactically tail and non-tail recursive, overall iterative
    3. syntactically tail and non-tail recursive, overall recursive
    4. syntactically tail recursive, so iterative
  1. What kind of process does the following function implement?
        (define (f n z)
            (cond
                ((= n 0) z)
                ((< n 3) (f (- n 1) (* z n)))
                (else (* z (f (- n 1) (+ z 1))))
                )
            )
    
    1. syntactically tail recursive, so iterative
    2. syntactically tail and non-tail recursive, overall iterative
    3. syntactically non-tail recursive, so recursive
    4. syntactically tail and non-tail recursive, overall recursive

Concept: tree recursion

  1. T or F: Does the following function exhibit tree recursion?
        (define (f z)
            (if (< z 2)
                z
                (+ (f (- z 2)) (- z 1))
                )
            )
    
  1. T or F: Does the following function exhibit tree recursion?
        (define (f z)
            (define (iter a b count)
                (if (= count 0)
                    b
                    (iter (f (- count 1)) (f (- count 2)) (- count 1))
                    )
                )
            (iter 0 0 z)
            )
    
  1. T or F: Does the following function exhibit tree recursion?
        (define (f z)
            (define (iter a b count)
                (if (= count 0)
                    a
                    (iter b (+ a b) (- count 1))
                    )
                )
            (iter 0 1 z)
            )
    
  1. T or F: TQ: Does the following function exhibit tree recursion?
        (define (f z)
            (cond
                ((< z 2) 1)
                (else (* z (f (- z 1))) (f 1))
                )
            )
    
  1. The space complexity of the following function is:
        (define (f x)
           (if (< x 2)
               x
               (+ (f (- x 1)) (f (- x 2)))
               )
            )
    
    1. linear
    2. constant
    3. exponential
    4. log linear
    5. logorithmic
  1. The time complexity of the following function is:
        (define (f x)
           (if (< x 2)
               x
               (+ (f (- x 1)) (f (- x 2)))
               )
            )
    
    1. logorithmic
    2. linear
    3. exponential

    4. log linear
    5. constant
  1. T or F: One way to reduce redundant computations, if any, in tree recursion is to memoize intermediate results.
  1. T or F: A recursive function cannot implement an iterative process.
  1. A completely tail recursive function is one that:
    1. recurs an infinite number of times
    2. recurs a constant number of times
    3. if a recursive call is made, it is the last expression evaluated
    4. the last expression evaluated is a recursive call
  1. Among recursive functions, a completely tail recursive function is uniquely characterized by:
    1. execution in ω ( 1 ) space
    2. execution in θ ( 1 ) space
    3. execution in θ ( 1 ) time
    4. execution in Ω ( 1 ) time

Concept: orders of growth

  1. T or F: If f = Θ ( g ) , then c 1 g ( n ) f ( n ) c 2 g ( n ) .
  1. Tree-recursive fibonacci takes time on the order of:
    1. φ n
    2. n 2
    3. φ 2
    4. n
  1. Non-tail recursive factorial takes space on the order of:
    1. φ 2
    2. n
    3. n 2
    4. φ n
  1. Non-tail recursive factorial takes time on the order of:
    1. n
    2. n 2
    3. φ 2
    4. φ n
  1. Tree-recursive fibonacci takes space on the order of:
    1. a constant
    2. φ 2
    3. φ n
    4. n
  1. Iterative factorial takes space on the order of:
    1. n
    2. φ n
    3. φ 2
    4. a constant
  1. Iterative factorial takes time on the order of:
    1. φ n
    2. n
    3. a constant
    4. n !
  1. Iterative fibonacci takes space on the order of:
    1. a constant
    2. φ n
    3. φ 2
    4. n
  1. Iterative fibonacci takes time on the order of:
    1. a constant
    2. n
    3. φ n
    4. n !

Concept: exponentiation

  1. This recurrence:
        e(b,n) = b * e(b,n-1) if n > 0
        e(b,n) = 1 otherwise
    
    if implemented directly, takes:
    1. quadratic time
    2. linear time
    3. log time
    4. exponential time
    5. constant time
    6. log linear time
  1. This recurrence:
        e(b,n) = b * e(b,n-1) if n > 0
        e(b,n) = 1 otherwise
    
    if implemented directly, takes:
    1. log space
    2. linear space
    3. constant space
    4. quadratic space
    5. log linear space
    6. quadratic space
  1. This recurrence:
        e(b,n) = e(b*b,n/2) if
            n is positive,even
        e(b,n) = b * e(b,n-1) if
            n is positive,odd
        e(b,n) = 1 otherwise
    
    if implemented directly, takes:
    1. log linear space
    2. log time
    3. quadratic time
    4. constant time
    5. linear time
    6. exponential time
  1. This recurrence:
        e(b,n) = e(b*b,n/2) if
            n is positive,even
        e(b,n) = b * e(b,n-1) if
            n is positive,odd
        e(b,n) = 1 otherwise
    
    if implemented directly, takes:
    1. quadratic space
    2. exponential space
    3. log space
    4. log linear space
    5. linear space
    6. constant space
  1. This recurrence:
        e(b,n) = e(b*b,n/2) if
            n is positive,even
        e(b,n) = b * e(b,n-1) if
            n is positive,odd
        e(b,n) = 1 otherwise
    
    if implemented directly, takes:
    1. quadratic space
    2. log space
    3. linear space
    4. log linear space
    5. constant space
  1. This recurrence:
        e(b,n) = e(b,n/2)^2 if
            n is positive,even
        e(b,n) = b * e(b,n-1) if
            n is positive,odd
        e(b,n) = 1 otherwise
    
    if implemented directly, takes:
    1. exponential time
    2. log linear time
    3. log time
    4. linear time
    5. quadratic time
  1. This recurrence:
        e(b,n) = e(b,n/2)^2 if
            n is positive,even
        e(b,n) = b * e(b,n-1) if
            n is positive,odd
        e(b,n) = 1 otherwise
    
    if implemented directly, takes:
    1. quadratic space
    2. exponential space
    3. log space
    4. linear space
    5. constant space
    6. log linear space
  1. This recurrence:
        e(b,n) = e(b,n/2) * e(b,n/2) if
            n is positive,even
        e(b,n) = b * e(b,n-1) if
            n is positive,odd
        e(b,n) = 1 otherwise
    
    if implemented directly, takes:
    1. log linear space
    2. exponential space
    3. constant space
    4. log space
    5. quadratic space
    6. linear space
  1. This recurrence:
        e(b,n) = e(b,n/2) * e(b,n/2) if
            n is positive,even
        e(b,n) = b * e(b,n-1) if
            n is positive,odd
        e(b,n) = 1 otherwise
    
    if implemented directly, takes:
    1. constant time
    2. log time
    3. exponential time
    4. quadratic time
    5. log linear time
    6. linear time
  1. This recurrence:
        e(b,n) = f(b,n,1)
        f(b,n,t) = f(b*b,n/2,t) if
            n is positive,even
        f(b,n,t) = f(b,n-1,t*b) if
            n is positive,odd
        f(b,n,t) = t otherwise
    
    if implemented directly, takes:
    1. linear time
    2. exponential time
    3. constant time
    4. quadratic time
    5. log linear time
    6. log time
  1. This recurrence:
        e(b,n) = f(b,n,1)
        f(b,n,t) = f(b*b,n/2,t) if
            n is positive,even
        f(b,n,t) = f(b,n-1,t*b) if
            n is positive,odd
        f(b,n,t) = t otherwise
    
    if implemented directly, takes:
    1. quadratic space
    2. linear space
    3. constant space
    4. log linear space
    5. log space
    6. exponential space

Concept: greatest common divisors

  1. This recurrence:
        gcd(a,b) = a if b is zero
        gcd(a,b) = gcd(b,a%b) otherwise
    
    was first attributed to:
    1. Caesar Augustus
    2. Euclid
    3. Ptolmey
    4. Aristotle
  1. How is Lamé's Theorem used to generate an upper bound on gcd(m,n)? Assume m is larger than n and that gcd(m,n) takes k steps.
    1. n F i b ( k ) n k Φ 5 l o g ( n ) Φ l o g ( k ) - l o g ( 5 )
    2. n F i b ( k ) n Φ k 5 l o g ( n ) k l o g ( Φ ) - l o g ( 5 )
    3. n F i b ( k ) n k Φ 5 l o g ( n ) Φ l o g ( k ) - l o g ( 5 )
    4. n F i b ( k ) n Φ k 5 l o g ( n ) k l o g ( Φ ) - l o g ( 5 )
  1. This recurrence:
        gcd(a,b) = a if b is zero
        gcd(a,b) = gcd(b,a%b) otherwise
    
    if implemented directly, takes:
    1. exponential space
    2. linear space
    3. log linear space
    4. log space
    5. constant space
    6. quadratic space
  1. Consider this recurrence:
        gcd(a,b) = a if b is zero
        gcd(a,b) = gcd(b,a%b) otherwise
    
    The number of remainder operations performed by gcd(412,60) using applicative order evaluation is:
    1. 2
    2. 3
    3. 5
    4. 4
  1. Consider this recurrence:
        gcd(a,b) = a if b is zero
        gcd(a,b) = gcd(b,a%b) otherwise
    
    Assuming a knowledge of when to stop, what is the number of remainder operations performed by gcd(412,60) using normal order evaluation? There are four recursive calls which involve remainder operations. gcd(a,b) is gcd(b,a%b) is the first of these.
    1. 19
    2. 6
    3. 11
    4. 3

Concept: testing for primality

  1. What is the distinguishing characteristic of probabilistic algorithms?
    1. the chance of success drops the more times the algorithm is run
    2. the chance of failure cannot be made arbitrarily small
    3. they use random numbers
    4. the chance of failure can be made arbitrarily small
  1. What is Fermat's little theorem? Assume n is prime and a positive.
    1. a n % n = a % n
    2. a n % a = a % n
    3. a n % a = n % a

    4. a n % n = a
  1. What is a Charmichael number?
    1. prime numbers undetected by straight Fermat-based primality predicates
    2. numbers that fool straight Fermat-based primality predicates
    3. prime numbers undetected by Miller-Rabin-based primality predicates
    4. numbers that fool Miller-Rabin-based primality predicates
  1. What is the drawback of the following implementation with respect to primality testing:
        (define (expmod base exp m)
            (% (fast-expt base exp) m))
    
    1. fast-expt may overflow in systems with fixed-sized integers
    2. fast-expt is slow for systems with fixed-sized integers
    3. the mod operation should happen before the call to fast-expt
    4. fast-expt already performs the mod operation
  1. Consider the following implementation:
    (define (expmod base exp m)
        (cond ((= exp 0) 1)
            ((even? exp)
                (% (square
                      (expmod base
                          (/ exp 2) m)) m))
            (else
                (% (* base
                      (expmod base
                          (- exp 1) m)) m))))
    
    What is the recurrence that describes the even case?
    1. T(n) = T(n/2) + O(1)
    2. T(n) = T(n-1) + O(log n)
    3. T(n) = T(n-1) + O(1)
    4. T(n) = T(n/2) + O(log n)
  1. Consider the following implementation:
    (define (expmod base exp m)
        (cond ((= exp 0) 1)
            ((even? exp)
                (% (square
                    (expmod base (/ exp 2) m)) m))
            (else
                (% (* base
                    (expmod base (- exp 1) m)) m))))
    
    What is the recurrence that describes the default case?
    1. T(n) = T(n/2) + O(1)
    2. T(n) = T(n/2) + O(log n)
    3. T(n) = T(n-1) + O(log n)
    4. T(n) = T(n-1) + O(1)
  1. Consider the following implementation:
    (define (expmod base exp m)
        (cond ((= exp 0) 1)
            ((even? exp)
                (% (* (expmod base (/ exp 2) m)
                      (expmod base (/ exp 2) m))
                      m))
            (else
                (% (* base (expmod base (- exp 1) m))
                   m))))
    
    What is the recurrence that describes the even case?
    1. T(n) = T(n/2) + O(1)
    2. T(n) = 2T(n/2) + O(log n)
    3. T(n) = 2T(n/2) + O(1)
    4. T(n) = T(n/2) + O(log n)
  1. The recurrence: T(n) = T(n/2) + O(1) reduces to:
    1. O(log n)
    2. O(n)
    3. O(1)
    4. O(n log n)
  1. The recurrence: T(n) = T(n/2) + O(log n) reduces to:
    1. O(log n)
    2. O(n log n)
    3. O(n)
    4. O((log n)*(log n))
  1. The recurrence: T(n) = 2T(n/2) + O(log n) reduces to:
    1. O(n)
    2. O((log n)*(log n))
    3. O(log n)
    4. O(n log n)
  1. The recurrence: T(n) = 2T(n/2) + O(1) reduces to:
    1. O(n)
    2. O(n log n)
    3. O(log n)
    4. O((log n)*(log n))
  1. The recurrence: T(n) = T(n-1) + O(1) reduces to:
    1. O((log n)*(log n))
    2. O(n)
    3. O(log n)
    4. O(n log n)
  1. The recurrence: T(n) = T(n-1) + O(log n) reduces to:
    1. O(n log n)
    2. O(n)
    3. O(log n)
    4. O((log n)*(log n))