Samacheer Kalvi solutions for Computer Science [English] Class 11 TN Board chapter 8 - Iteration and recursion [Latest edition]

A loop invariant need not be true ______

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

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 ______

Which of the following is not an invariant of the assignment?

m, n := m + 2, n + 3

If the Fibonacci number is defined recursively as F(n) = `{(0, "n" = 0), (1, "n" = 1), ("F"("n" - 1),+  "F"("n" - 2) "otherwise"):}` 
to evaluate F(4), how many times F() is applied?

Using this recursive definition

`"a"^"n" = {(1, "if"  "n" = 0), ("a" × "a"^("n" - 1), "otherwise"):}`

how many multiplications are needed to calculate a¹⁰?

What is an invariant?

Define a loop invariant.

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

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

What is recursive problem-solving?

Define factorial of a natural number recursively.

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?

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?

King Vikramaditya has two magic swords. With one, he can cut off 19 heads of a dragon, but after that, the dragon grows 13 heads. With the other sword, he can cut off 7 heads, but 22 new heads grow. If all heads are cut off, the dragon dies. If the dragon has originally 1000 heads, can it ever die?

Assume an 8 × 8 chessboard with the usual coloring. "Recoloring" operation changes the color of all squares of a row or a column. You can recolor repeatedly. The goal is to attain just one black square. Show that you cannot achieve the goal.

Power can also be defined recursively as

`"a"^"n" = {(1, "if"  "n" = 0), ("a" × "a"^("n" - 1), "if n is odd"), ("a"^("n""/"2) × "a"^("n""/"2), "if n is even"):}`

Construct a recursive algorithm using this definition. How many multiplications are needed to calculate a¹⁰?

A single-square-covered board is a board of 2n x 2n squares in which one square is covered with a single square tile. Show that it is possible to cover this board with triominoes without overlap.