Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 5
Exercise 1:
In this exercise you are asked to implement the operation merge from the
D&C sorting algorithm explained at the lecture.
Let A[1..n], B[1..m] and C[1..(n+m)] be arrays such that n,m>0.
-
Write an algorithm merge(A,B) which will return an array of
size n+m and satisfy the following conditions.
Try to achieve an optimal time complexity.
--pre: A and B are non-decreasing arrays
C:=merge(A,B);
--post: C is a non-decreasing array and it is a permutation of
the elements from A and B
- Run your algorithm on the following instance of the problem:
A = [3,4,7] and B =[1,4,8] (i.e. A[1]=3, A[2]=4, A[3]=7, B[1]=1, B[2]=4,
B[3]=8).
- What is the worst-case time complexity of your algorithm (use the
big-O notation and justify your answer)?
Exercise 2 (hand in):
Recall the ADT called SET from the lecture. For a set s:SET
we have the following basic operations
- s.make
- s.empty:boolean
- s.insert(x:int)
- s.delete_any:int
and we also defined a non-destructive version of member(x:int,s:SET):boolean.
Define a new set operation sum(s:SET):int satisfying
--pre: s is a SET
x:=sum(s)
--post: x=Σa ∈ S a
and
s'=s
Assume now that somebody gave you a better implementation of
SET than what we did at the lecture. However, the only info you know
about the new implementation is that
-
all the basic set operations (make, empty, insert, and delete)
and the operation member satisfy exactly the same pre- and post-
conditions as before
-
if we assume that the number of elements in the set s is n
then (in the worst-case)
- s.make takes O(1) time
- s.empty takes O(1) time
- s.insert takes O(1) time
- s.delete_any takes O(1) time
- member(x,s) takes O(n) time.
Is this piece of information
enough to analyze the worst-case time complexity of your sum operation?
- If yes, provide the worst-case time complexity of sum(s) where the size
of your input is the number of elements in s (let's call this number n).
Exercise 3:
Assume the same "better" implementation of SET as in Example 2.
Define a new operation intersection(s1:SET,
s2:SET):SET
satisfying
--pre: s1 and s2 are SETs
s:=intersection(s1, s2)
--post: s = s1 ∩ s2 and
s'1 = s1 and
s'2 = s2
Provide the worst-case time complexity analysis of
intersection(s1, s2) (use
|s1| for the number of elements in the set
s1 and |s2| for the number of elements
in s2).