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 $\omega \left(1\right)$ space
2. execution in $\theta \left(1\right)$ space
3. execution in $\theta \left(1\right)$ time
4. execution in $\Omega \left(1\right)$ time

## Concept:orders of growth

1. T or F: If $f=\Theta \left(g\right)$, then ${c}_{1}g\left(n\right)\le f\left(n\right)\le {c}_{2}g\left(n\right)$.
1. Tree-recursive fibonacci takes time on the order of:
1. ${\phi }^{n}$
2. ${n}^{2}$
3. ${\phi }^{2}$
4. $n$
1. Non-tail recursive factorial takes space on the order of:
1. ${\phi }^{2}$
2. $n$
3. ${n}^{2}$
4. ${\phi }^{n}$
1. Non-tail recursive factorial takes time on the order of:
1. $n$
2. ${n}^{2}$
3. ${\phi }^{2}$
4. ${\phi }^{n}$
1. Tree-recursive fibonacci takes space on the order of:
1. a constant
2. ${\phi }^{2}$
3. ${\phi }^{n}$
4. $n$
1. Iterative factorial takes space on the order of:
1. $n$
2. ${\phi }^{n}$
3. ${\phi }^{2}$
4. a constant
1. Iterative factorial takes time on the order of:
1. ${\phi }^{n}$
2. $n$
3. a constant
4. $n!$
1. Iterative fibonacci takes space on the order of:
1. a constant
2. ${\phi }^{n}$
3. ${\phi }^{2}$
4. $n$
1. Iterative fibonacci takes time on the order of:
1. a constant
2. $n$
3. ${\phi }^{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:
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
5. log linear 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
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:
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:
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
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:
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
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
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
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:
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\ge Fib\left(k\right)\to n\ge \genfrac{}{}{0.1ex}{}{{k}^{\Phi }}{\sqrt{5}}\to log\left(n\right)\ge \Phi \phantom{\rule{0.278em}{0ex}}log\left(k\right)-log\left(\sqrt{5}\right)$
2. $n\le Fib\left(k\right)\to n\le \genfrac{}{}{0.1ex}{}{{\Phi }^{k}}{\sqrt{5}}\to log\left(n\right)\ge k\phantom{\rule{0.278em}{0ex}}log\left(\Phi \right)-log\left(\sqrt{5}\right)$
3. $n\le Fib\left(k\right)\to n\le \genfrac{}{}{0.1ex}{}{{k}^{\Phi }}{\sqrt{5}}\to log\left(n\right)\le \Phi \phantom{\rule{0.278em}{0ex}}log\left(k\right)-log\left(\sqrt{5}\right)$
4. $n\ge Fib\left(k\right)\to n\ge \genfrac{}{}{0.1ex}{}{{\Phi }^{k}}{\sqrt{5}}\to log\left(n\right)\ge k\phantom{\rule{0.278em}{0ex}}log\left(\Phi \right)-log\left(\sqrt{5}\right)$
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
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))