#### Iteration and Recursion Book Back Questions

11th Standard

Reg.No. :
•
•
•
•
•
•

Computer Science

Time : 00:45:00 Hrs
Total Marks : 30
6 x 1 = 6
1. A loop invariant need not be true

(a)

at the start of the loop

(b)

at the start of each iteration

(c)

at the end of each iteration

(d)

at the start of the algorithm

2. We wish to cover a chessboard with dominoes, the number of black squares and the number of white squares covered by dominoes, respectively, placing a domino can be modeled by

(a)

b:= b + 2

(b)

w:= w + 2

(c)

b, w := b1+, w1+

(d)

b:= w

3. If m x a + n x b is an invariant for the assignment a, b : = a + 8, b + 7, the values of m and n are

(a)

m=8,n=7

(b)

m=7,n=-8

(c)

m=7,n=8

(d)

m =8,n=-7

4. Which of the following is not an invariant of the assignment? m, n := m2+, n3+

(a)

m mod2

(b)

n mod3

(c)

3 X m - 2 X n

(d)

2 X m - 3 X n

5. If Fibonacci number is defined recursively as$f(n)=\begin{cases} 0n=0 \\ 1n=1 \\ f(n-1)+f(n-2)otherwise \end{cases}$to evaluate F(4), how many times F() is applied?

(a)

3

(b)

4

(c)

8

(d)

9

6. Using this recursive definition${ a }^{ n }=\begin{cases} 1\quad \quad \quad \quad \quad \quad ifn=0 \\ a\times { a }^{ n }-1\quad otherwise \end{cases}$how many multiplications are needed to calculate a10?

(a)

11

(b)

10

(c)

9

(d)

8

7. 6 x 2 = 12
8. What is an invariant?

9. Define a loop invariant.

10. Does testing the loop condition affect the loop invariant? Why?

11. What is the relationship between loop invariant, loop condition and the input-output recursively?

12. What is recursive problem solving

13. Define factorial of a natural number recursively

14. 2 x 3 = 6
15. There are 7 tumblers on a table, all standing upside down. You are allowed to turn any 2 tumblers simultaneously in one move. Is it possible to reach a situation when all the tumblers are right side up? (Hint: The parity of the number of upside-down tumblers is invariant.)

16. A knockout tournament is a series of games. Two players compete in each game; the loser is knocked out (i.e. does not play anymore), the winner carries on. The winner of the tournament is the player that is left after all other players have been knocked out. Suppose there are 1234 players in a tournament. How many games are played before the tournament winner is decided?

17. 1 x 5 = 5
18. Power can also be defined recursively as ${ a }^{ n }=\begin{cases} 1\quad \quad \quad \quad \quad \quad ifn=0 \\ a\times { a }^{ n }-1\quad \quad ifn\quad is\quad odd \\ { a }^{ n/2 }\times an/2\quad ifn\quad is\quad even \end{cases}$ Construct a recursive algorithm using this definition. How many multiplications are needed to calculate a10?