[ CIS621 | CIS | UO | News ]

• Let's get a closure on the Fibonacci sequence, defined as

  F(n)=F(n-1)+F(n-2) for n>1
  F(0)=F(1)=1

  Recall that the generating function G(a_n) is defined as the function of a real variable x, g(x), with a_n as the cofficients of the n-the power of x in its power series expansion
  g(x)=sum a_n·x^n for n>-1 (this is an html joke)
  Also, the simple fractional function 1/(1 -c·x) is the generating function of the sequence with general term c^n.

  • Prove that the generating function of F(n) is f(x)=1/(1-x-x²)
  • Represent f(x) as the sum of two simple fractions with denominators 1-(1+sqrt(5))/2·x and 1-(1-sqrt(5))/2·x
  • Represent F(n) as the sum of two exponential functions and give a tight bound on its asymptotic growth rate.

• Analyze the complexity of Order Statistic algorithm when the size of the small groups of elements from which we choose the median is (i) 3 or (ii) 7.

• Provide a linear time solution to the secondary Minimum Record Movement problem where, given the sorted list of file sizes s_1\ge s_2\ge...\ge s_n, you should construct the binary tree reflecting a merging scheme of minimum cost. (Hint: see the comment)