Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 1
Exercise 1:
Write an equivalent algorithm without the use of goto.
x:=1
1: x:=x*2
if (x<20) then goto 1 else x:=x+1
Exercise 2:
Consider the following problem.
INPUT: A sequence S of natural numbers of length n, such that n>0
(accessed by S[1], S[2], ..., S[n]).
OUTPUT: The smallest and the largest element of S.
- Describe a precise algorithm to solve this problem.
- What is the number of comparisons of your algorithm in the worst case?
- Does this number depend on the input sequence S?
Exercise 3 (hand-in, either individually or in pairs):
Consider the following problem.
INPUT: A sequence S of natural numbers of length n, such that n>0
(accessed by S[1], S[2], ..., S[n]).
OUTPUT: The second smallest element of S.
- Describe a precise algorithm to solve this problem.
- What is the number of comparisons of your algorithm in the worst case?
- Does this number depend on the input sequence S? If not modify (improve)
your algorithm such that it does.
- Try your algorithm on some examples (you do not have to write down
this part) and for all natural numbers n find
a sequence S such that the algorithm performs the largest
number of comparisons on this sequence (write down the sequence
and the number of comparisons).
Exercise 4:
Consider the following problem.
INPUT:
Let x and y be words over an alphabet of capital Roman
letters {A,B,C, ..., Z} of length n and m, respectively
such that n>m>0. Let us call x text and y pattern.
OUTPUT: A number of occurrences of the pattern y in the text x.
- Describe a precise algorithm to solve this problem.
-
What is the number of comparisons of your algorithm in the worst case?
(I.e. given a text x of length n and a pattern y of length m,
what is the maximum number of comparisons among all possible
input words x and y of the length n and m, respectively?)
-
For every n and m describe two words x and y of the given length such that
your algorithm run on these words performs the largest number of comparisons.
To access the i'th letter of the word x and y use the syntax x[i] and y[i].
For example if x=ALGORITHM then n=9, x[1]=A, x[3]=G and x[n]=M.