Description
1. Consider the recurrence R(n) = 4R(n − 1) − 3R(n − 2) with initial conditions
R(0) = 2 and R(1) = 8. (4 Points)
Find its characteristic equation, and use it to create a formula for the recurrence that depends only on n, i.e. is not recursive.
What is the recurrence’s order of growth? Use Θ(n) if you can.
2. The Lucas numbers, named for 19th century French mathematician Edouard ´
Lucas, are defined exactly as the Fibonacci numbers, except that they have
ever-so-slightly different initial conditions. The Lucas numbers are given by:
L(0) = 2
L(1) = 1
L(n) = L(n − 1) + L(n − 2) for n > 1
Write a C++ program that accepts as input a value n and writes as output
the sequence L(0), L(1), . . . , L(n). Your program should compute the values
recursively with a separate function that uses the definition above. You may
hardcode the initial conditions. (7 Points)
What else is Lucas known for?
3. Use the clock() function from < time.h > to investigate the order of growth of
your recursive algorithm that computes the Lucas numbers. (11 Points)
• Extend your program from Part 2 above to determine the time needed to
compute each of the first 30 Lucas numbers. (You are encouraged to go
higher!) Display these results for each n on the standard console output.
• Have your code examine the ratio of successive calculations, i.e. Time(L(n+1))
Time(L(n)) .
Do you recognize this number?
What is the order of growth of your algorithm?
1
4. The Suribachs Magic Square–pictured below–is an interesting construction.
While not technically a magic square, its rows, columns, diagonals, corners,
center, and “postage stamps” do all have the same sum. In fact, there are
many other combinations in the square that also have this sum. (18 Points)
• Write a C++ program that counts all the 4-element combinations that
have the same sum as the rows/columns, etc.
• Add to your program so that you can count all combinations with this sum.
Some will have fewer than 4 elements, some will have exactly 4 elements,
some will have more than 4 elements. Count them all.
• Make yet another addition to your program that counts the number of ways
every possible sum can be formed. Include 0 as a possible sum; the largest
sum will be created by summing every cell of the square.
• What sum can be created with the greatest number of combinations, and
how many combinations is that? Notice anything interesting about that?
Bonus: The Suribachs Magic Square is fascinating. Your investigations might
have piqued your curiosity about it. Write (and document!) a C++ program
investigating some aspect of it not covered here, or write a 1-page report detailing where it can be found, explaining why it is named what it is named, and
discussing its “mystical” significance. (2 Bonus Points)
