DS1 (L1 Recurrent Problems )

Which of the following characteristics define recurrent problems?

• They are investigated once and solved immediately

• They are investigated repeatedly and depend on smaller instances of the problem

• They do not require recurrence relations for their solutions

• They always have a non-recursive solution

What is the role of recurrence in problem-solving?

• It makes problems harder to solve

• It allows solving large problems by referring to solutions of smaller subproblems

• It eliminates the need for mathematical proofs

• It is only useful for iterative approaches

What is a closed-form expression?

• A formula that cannot be simplified further

• A formula that can be expressed in terms of elementary functions

• A formula that only uses summations and iterations

• A recursive equation that does not require a base case

In solving recurrent problems, what is the first step?

• Solve for the largest possible case

• Find a recurrence relation immediately

• Look at small cases and analyze the pattern

• Assume a solution without proof

Who invented the Tower of Hanoi problem?

• Blaise Pascal

• Euclid

• Edouard Lucas

• Pierre de Fermat

What is the goal of the Tower of Hanoi problem?

• Sort the disks from largest to smallest

• Move all disks from one rod to another, following specific rules

• Swap the positions of the largest and smallest disks

• Count the number of moves required to complete the game

Which of the following is NOT a rule in the Tower of Hanoi?

• Move only one disk at a time

• A larger disk cannot be placed on a smaller disk

• Disks can be moved freely between any two pegs

• All disks must be transferred to another peg

What is the recurrence relation for the number of moves required to solve the Tower of Hanoi with n disks?

• T(n)=T(n−1)+1

• T(n)=2T(n−1)+1

• T(n)=T(n−1)+2T(n−2)

• T(n)=3T(n−1)−1

The base case for the Tower of Hanoi recurrence relation is:

• T(0)=0

• T(1)=1

• T(1)=2

• T(2)=1

If the Tower of Hanoi problem takes 3 moves for 2 disks, how many moves will it take for 3 disks?

• 4

• 5

• 6

• 7