1. Explain in words why each recurrence relation is represented by the given des
ID: 3594870 • Letter: 1
Question
1. Explain in words why each recurrence relation is represented by the given description For example: P(1) = 2 P(n) = P(n-1)+2 for n22 P(n) slices after cutting a pizza n times along a diameter. you could ay There are two halves of the pizza after one cut so P(1)=2. After n-1 cuts, you have P(n-1) slices, if you slice one more time (the nth time), you will cut two of the slices in half creating two more slices so P(n)P(n-1) +2 H (2) = 1 11(n)-H(n-1) + n-1 for 3 n H(n) is the number of handshakes in a room of n people where everybody shake hands with everybody else exactly once E( 1 ) = 0, C(2)-0, C(3) s),C(9-1 C(n)-C(n-3) + C(n-4) for n 25 C(n) is the number of sequences of 3's and 4's that add up to B(1) = 2, B(2) = 4,B(3) = 7 E(n) = B(n-1) + B(n-2) + B(n-3) for 12 3 B(n) is the number of n-bit binary strings that avoid 000 Fl)Fn) 2F(n/2)+1 or n2 1 F(n) is the number of matches played in a single elimination tournament with n players (you can assume n- 2t for some positive integer k. You can use the bracket below to help explain.) 16 Team Single iminationExplanation / Answer
Hi,
A) Given H(2)=1 and H(n)=H(n-1)+n-1 for n>=3
Now, since a handshake requires 2 people at the min, the base case starts with H(2), where only handshake is possible, Now, imagine we have 3 people, after 2 people are done with the hand shake, the 3rd or the (n+1)th guy is left to shake hands to everyone else, i.e the other 2 people, therefore H(3) = H(2) + 2(shaking hands with other 2)
similarly, for H(n), the nth guy will have shake hands with all n-1 guys, therefore H(n)=H(n-1)+n-1
B)Given C(1)=0,C(2)=0,C(3)=1,C(4)=1 and C(n)=C(n-3)+C(n-4) for n>=5
where C(n) is the number of sequences of 3's and 4's that add up to n
First lets write C(1),C(2) both are zero since they cant add upto n
C(3) will be 1, because 3*1+0*4=3
C(4) will be 1, because 3*0+1*4=4
Now,
to get upto n, with the existing number we have to add (n-3) to so that n-3+3=n
and similarly to get n, we can also do n-4+4=n
this is somewhat similar to a fibonacci relation, but with different combinations,
hence we have C(n)=C(n-3)+C(n-4)
C) given B(1)=2,B(2)=4,B(3)=7 and B(n)=B(n-1)+B(n-2)+B(n-3)
where B(n) is the number of n bit binary strings that avoid 000
lets first see the base cases
B(1) - '1' and '0' avoid 000 hence -2
B(2)- 00 01 10 11 all 4 avoid 000
B(3)- all 8 except 000 are present i.e 7
Now, simlar to the above part,
a sequence ending in a single zero is to take any of the previous sequences and append 00 to it. Similarly the only way to form a sequence ending in 2 '0' is to take any of the previous and append 00 to it. Hence
it becomes B(n)=B(n-1)+B(n-2)+B(n-3)
D)Given F(1)=0 and F(n)=2F(n/2)+1
This is a typical binary search recursion example, where after each step, the set is halfed, like in the case of tournament, the number of matches are halfed after every stage, like round of 64, then round of 32 and so on..
and the both are them are combined with a match between the winner,
the figure given is an excellent representation of the recurrence tree,
for F(n) if there, we split the teams into 2 batches of F(n/2), make the two groups play and then declare the winner as the additonal match that is between winners of each of the F(n/2) groups ( +1 )
therefore F(n)=2F(n/2)+1
Thumbsup if this was helpful, otherwise let me know in comments
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.