CSPP 55001 Algorithms - Spring 2008
Homework 4 (assigned April 23, due May 6)
Reading: Read CLRS chapters 8 and 9.
Written assignment: Solve the following "Do" exercises and assigned
problems. Turn in only the problem solutions. Please note: You are
responsible for the material covered in both "Do" exercises and
problems.
"Do" Exercise (not to be handed in):
-
A tournament tree is a complete binary tree reflecting results
of a single-elimination tournament: its leaves represent n players
entering the tournament, and each internal node represents a winner of a
match played by the players represented by the children of this node. The
winner of the tournament is represented by the root of the tree.
-
What is the total number of games played in such a tournament?
-
How many rounds are there in such a tournament?
-
Design an efficient algorithm to determine the second best player using
the information produced by the tournament. How many extra games
does your algorithm require?
Problems (to be handed in):
-
Simultaneous max and min
Describe an algorithm that uses at most 3 × floor[n/2]
comparisons to simultaneously find the largest and smallest elements in an
array of n numbers. Write pseudocode for your algorithm and justify
its running time. (20 points)
-
Simultaneous smallest two
Show that the two smallest numbers in a list of n numbers can be
found with n + ceiling[lg n] - 2 comparisons in the worst
case. (20 points)
-
Algorithm design
-
Design a recursive algorithm for computing 2n for any
nonnegative integer n that is based on the formula
2n = 2n-1 + 2n-1.
Write pseudocode for your algorithm. (10 points)
-
Write a recurrence for the number of additions made by your algorithm
from part (1) and solve this recurrence.
(5 points)
-
Is your algorithm from part (1) an efficient algorithm for solving the problem
of computing 2n? Present a second algorithm
for solving this problem that is more efficient than the first. Clearly and
concisely describe the steps that your second algorithm makes. (10 points)
-
Computing Fibonacci numbers
Revision (5/1/08): Turn this problem in with Homework *6*, on May 13,
as a bonus point problem.
Note:
The nth Fibonacci number satisfies the equality
Fn = (φn -
φ'n)/√5,
where φ = (1 + √5)/2 and φ' = (1 - √5)/2. See the above
"Do" exercise.
The Fibonacci numbers are defined by the following recurrence:
F0 = 0,
F1 = 1,
Fn = Fn-1 +
Fn-2 for n ≥ 2.
We can use this recurrence to obtain the following recursive algorithm for
computing the nth Fibonacci number F(n):
F(n)
01 if n = 0
02 then return 0
03 else if n = 1
04 then return 1
05 return F(n - 1) + F(n - 2)
This algorithm is correct, since it directly implements the definition of the
Fibonacci numbers. To analyze its cost, let A(n) be the
number of additions peformed by the algorithm in computing F(n).
Assume that all operations take unit time.
-
Give a recurrence for A(n), and use the substitution method to
show that
A(n) = O(Fn). (10 points)
-
Show that A(n) = Ω(Fn), and
hence, that
A(n) = Θ(Fn). (5 points)
The following is an alternative algorithm for computing the nth
Fibonacci number which computes the successive elements of the Fibonacci
sequence iteratively:
Fib(n)
01 Fib(0) <- 0
02 Fib(1) <- 1
03 for i ← 2 to n do
04 Fib(i) <- Fib(i - 1) + Fib(i - 2)
05 return Fib(n)
-
How many additions does this algorithm make on input n? (5 points)
-
Which of these two algorithms for computing the nth Fibonacci number
is faster? Justify your answer. (5 points)
Gerry Brady
Wednesday April 23 18:21:23 CDT 2008