CS702 Advanced Algorithms Analysis and Design Assignment No. 2 Fall 2014

[Entboy]

CS702 Advanced Algorithms Analysis and Design Assignment No. 2 Solutions and Discussions Fall 2014 Due Date: December 6, 2014


Question No. 1 (20 Points)


Consider the recurrence



tn = n if n = 0, 1, 2



tn = 6.tn-1 -11n-2 + 6.tn-3



Find the general solution of the recurrence above.


Question No. 2 (20 Points)


Solve the recurrence relation given below using substitution method.



Question No. 3 (10 Points)


Read the attached research paper entitled “Generalized Fibonacci Sequences” with this assignment very carefully. Explain in your own words, how they have Generalized Fibonacci Sequence?



While evaluating your answer, following rules will apply.

1) Copied answer will result in 0 marks

2) Any student found cheating in any of the two research papers summary submitted will be awarded "F" grade in the course.
3) Avoid using same wording from the research paper.



There is an update in question No. 1 of Assignment No. 1. Use following recurrence

tn = 6.tn-1 -11.tn-2 + 6.tn-3



Instead of tn = 6.tn-1 -11n-2 + 6.tn-3

and those who have submitted the assignments kindly check this again.