Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 10
Exercise 1:
Suppose we are hashing finite strings over the alphabet {a,b,c}.
(examples of strings are: a, bc, abcab, aaaa).
- Write a function f(S:string):int
which will translate any given string S[1..n] into an integer.
It is up to you to decide how the function should compute the integer.
- Compute the translations of the strings: a, b, ab, aab, cab, c.
- Assume a hash function h(n)= n mod 7.
Show the result after inserting the strings above (in the given
order) into a hash table A[0..6] and use linear probing to resolve
conflicts.
- Assume a hash function h(n)= n mod 3.
Show the result after inserting the strings above into a 5-bucket hash
table A[0..2].
- Assume a hash function h(n)= n mod 3.
Show the result after inserting the strings above into a hash
table A[0..2] and use chaining to resolve conflicts.
Exercise 2 (hand-in):
-
Design a sorting algorithm called bubble_sort which works
as follows: given an array A[1..n] it goes in a loop
through the elements A[1], A[2], ..., A[n-1] and whenever
it discovers a successive pair which is not ordered
(i.e. A[i] > A[i+1]) it will exchange these two elements.
If no exchange has been made the algorithm terminates (the array is sorted),
otherwise the whole procedure repeats.
- For every size n of the array A provide a worst-case instance.
What is the worst-case time complexity of your algorithm
(using big-O notation)?
- In which situations the algorithm performs fast? Can
it have any practical use?
Exercise 3:
Assume that we have two nonempty sets of elements of the same size:
s1={a1, a2, ..., an}
and s2={b1, b2, ..., bn}.
The sets are stored as sequences in arrays A[1..n] and B[1..n]
such that A[i]=ai and B[i]=bi for all
i=1 to n.
- Design an efficient algorithm to test whether the two
sets are equal (the algorithm recieves the arrays A and B as input).
Hint: after the execution of the algorithm the
arrays can be modified.
- Analyze the worst-case time complexity of your algorithm.