#### Iteration and recursion Model Question Paper

11th Standard

Reg.No. :
•
•
•
•
•
•

Computer Science

Time : 01:00:00 Hrs
Total Marks : 50
5 x 1 = 5
1. How many cases are there a recursive solver has

(a)

2

(b)

3

(c)

4

(d)

many

2. Which of the following is a recursive solver case

(a)

Base case

(b)

Recursive case

(c)

loop case

(d)

Both a and b

3. In which year E W Dijkstra was awarded ACM Turing Award?

(a)

1972

(b)

1974

(c)

1970

(d)

1971

4. In a loop, if L is an invariant of the loop body B, then L is known as a __________

(a)

recursion

(b)

variant

(c)

loop invariant

(d)

algorithm

5. The input size to a sub problem is __________ than the input size to the original problem.

(a)

equal

(b)

smaller

(c)

greater

(d)

no criteria

6. 5 x 2 = 10
7. What is an invariant?

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

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

10. Define factorial of a natural number recursively

11. When will the loop variant be true?

12. 5 x 3 = 15
13. 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.)

14. 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?

15. What are the important points in which a loop variant is true?

16. Using a loop variant how will you construct a loop?

17. Write a note on Recursion.

18. 4 x 5 = 20
19. 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?

20. Explain how will you solve a problem recursively.

21. Explain recursive- problem solving.

22. Design a recursive algorithm to compute an, We constructed an iterative algorithm to compute an in Example 8.5. an can be defined recursively as