Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 4
Exercise 1:
Consider the following algorithm for computing Fibonacci numbers:
fib(n)
=
table[0] := 0
table[1] := 1
for i:=2 to n do table[i]:= table[i-1]+table[i-2] endfor
return table[n]
We have seen that fib(n) has time complexity O(n).
- How would you measure the space requirements of the algorithm?
What is the space complexity of fib(n)?
- Improve the algorithm such that it has O(1) space complexity
while preserving O(n) time complexity.
Exercise 2:
Design "divide and conquer" algorithm for finding the largest element
of a given array A[a..b]. State appropriate pre- and post-conditions.
Exercise 3:
For your algorithm from exercise 2 compute the worst-case complexity
W(n). (Hint: define the worst-case complexity by recurrence equations
and solve them by considering only the points where n=2k for
k = 0,1,2, ...).
Approximate W(n) using the big-O notation.
Exercise 4 (challenging):
Exercise 4.6 from Algorithms and Data Structures: Design, Correctness and Analysis by Jeffrey H. Kingston.
Indeed, it is possible to find an algorithm with O(n) time complexity!
Try to suggest an algorithm s.t. after every question you ask, one
person can be clearly said not to be a celebrity.