Programming Questions: the following questions (3 and 4) are programming questio

Question

Programming Questions: the following questions (3 and 4) are programming questions. 3) (20 pts) Solve the recurrence relation for the ”Tower of Hanoi” problem. The problem statement is as follows Given a stack of n disks arranged from largest on the bottom to smallest on top placed on a rod, together with two empty rods (totally 3 rods), the towers of Hanoi puzzle asks for the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place smaller disks on top of larger disks. Solve the relation and Plot a graph for the various values of n disks. Give appropriate justifications for your relation 4) (20 pts.) Derive a recurrence relation on Binary Search. Solve the relation and Plot a graph for the various values of n. Give appropriate justifications for your relation. Note: The run time should be calculated for Problems 3 and 4. The graph should be plotted with time on the X axis and value of n on the Y axis.

Explanation / Answer

2) Tower of Hanoi

Let T(N) be the total time taken for N disk
Lets say we have N disk and we need to transfer n disk from PEG A To PEG C using Auxilliary PEG B
Steps :
if N is 1 then just transfer that disk from A-->C , base case is 1 i.e O(1)
Otherwise, Transfer N-1 disk from A-->B I.E T(N-1)
Transfer remaining 1 disk from A-->C
Again Transfer N-1 disk back to same place and repeat T(N-1)

Recurrance relation is

T(N) = 2T(N-1) + 1
T(1) = 1

T(1) = 1 , T(2) = 3
T(3) = 7
It goes this way so, T(n) = 2n - 1



(4) Binary Search

This search divide the peoblem into two subproblems and we reduce the search space by half everytime
If there is only one element so, base case is 1 for n=1
Otherwise we reduce the n by n/2 everytime

=> Recurrance relation is

T(N) = T(N/2) + 1
T(1) = 1

T(2) = 1 , T(4) = 2
It goes this way so, T(n) = log 2N

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.