UNIVERSITY OF VENDA
Department of Computer Science and Information Systems
Solved Exercises
QUESTION 1
a) Describe the algorithm used by your favorite ATM machine in dispensing cash. Give
your description in a pseudocode.
Suggested Ans:
Answers will vary from student to student depending on the algorithm chosen
b) Make an analysis of the algorithm you described in a) above and say what is its Time
efficiency class.
Suggested Ans:
Depending on the algorithm the answers may also vary but evident in every answer
must be the following
The input size
The Basic Operation
Expression for the number of times the basic operation occurs
Where necessary, best case, average case and worst case.
QUESTION 2
a) Give an example of a problem other than computing the greatest common divisor for
which you know more than one algorithm. Compare the two identified algorithms for
simplicity and efficiency
Suggested Ans:
Open ended question allowing students to give different answer
b) Define the term Order of Growth as used in algorithm design and analysis
State whether the first function of each of the following pairs has a smaller, same, or larger
order of growth (to within a constant multiple) than the second function.
i) 𝑛(𝑛 + 2) and 2000𝑛3
ii) 100𝑛2 and 0.001𝑛4
iii) log 2 𝑛 and ln 𝑛
1
Suggested Ans:
i) n (n + 1) ≈ 𝑛2 has the smaller order of growth (quadratic) than 2000𝑛3 to within a
constant multiple.
ii) 100 𝑛2 (quadratic) has a lower order of growth than 0.01𝑛4 (cubic).
iii) Since changing a logarithm’s base can be done by the formula
loga n = loga b logb n, all logarithmic functions have the same order of growth to within a
constant multiple.
QUESTION 3
a) Consider the algorithm for the sorting problem that sorts an array by counting, for each
of its elements, the number of smaller elements and then uses this information to put
the element in its appropriate position in the sorted array:
Apply this algorithm in sorting the list 60, 35, 81, 98, 14, 47, Is the algorithm stable?
Suggested Ans:
2
The algorithm is not stable. Consider, as a counterexample, the result of its
application to 1, 1”.
b) Consider the following algorithm for finding the distance between the two
closest elements in an array of numbers.
Make as many improvements as you can in this algorithmic solution to the problem. (If
you need to, you may change the algorithm altogether; if not, improve the
implementation given.)
QUESTION 4
a) Given the sequential search algorithm, use the most appropriate notation among O, Θ,
and Ω to indicate its time efficiency class.
Int SeqSearch (int [ ] E, int n, int K
1. int ans , index
2. ans = -1; //assume failure
3. for(index = 0; index < n; index ++)
4. if (K = = E[index])
5. ans = index; //success
6. break; //done
3
7. return ans;
i) In the worst case.
ii) In the best case.
iii) In the average case.
Suggested Ans:
i). Since 𝐶𝑊𝑜𝑟𝑠𝑡 (𝑛) = n, 𝐶𝑊𝑜𝑟𝑠𝑡 (𝑛) ∈ Θ (n).
ii). Since 𝐶𝐵𝑒𝑠𝑡 (𝑛) = 1, 𝐶𝐵𝑒𝑠𝑡 (1) ∈ Θ (1).
𝑝(𝑛+1) 𝑝 𝑝
iii). Since 𝐶𝐴𝑣𝑔 (𝑛) = 2 ) + n(1 − p) = (1 − 2)𝑛 + where 0 ≤ p ≤ 1,
2
a. 𝐶𝐴𝑣𝑔 (𝑛) ∈ Θ (n).
b) Write a pseudocode for an algorithm for finding real roots of equation
𝑎𝑥 2 + 𝑏𝑥 + 𝑐 = 0 for arbitrary real coefficients a, b, and c. (You may assume
the availability of the square root function sqrt(x).)
Suggested Ans:
Algorithm Quadratic (a, b, c)
//The algorithm finds real roots of equation ax2 + bx + c = 0
//Input: Real coefficients a, b, c
//Output: The real roots of the equation or a message about their absence
if a _= 0
D←b∗b−4∗a∗c
if D >0
temp ← 2 ∗ a
x1 ← (−b + sqrt(D))/temp
x2 ← (−b − sqrt(D))/temp
return x1, x2
else if D = 0 return −b/(2 ∗ a)
else return ‘no real roots’
else //a = 0
if b _= 0 return −c/b
else //a = b = 0
if c = 0 return ‘all real numbe
QUESTION 5
4
a) Design a simple algorithm for the string-matching problem.
Suggested Ans:
Align the pattern with the beginning of the text. Compare the corresponding
characters of the pattern and the text left-to right until either all the pattern
characters are matched (then stop–the search is successful) or the algorithm runs
out of the text’s characters (then stop–the search is unsuccessful) or a mismatching
pair of characters is encountered. In the latter case, shift the pattern one position to
the right and resume the comparisons.
b) Find the order of growth for solutions of the following recurrences.
i) T(n) = 4T(n/2) + n, T(1) = 1
ii) T(n) = 4T(n/2) + 𝑛2 , T(1) = 1
iii) T(n) = 4T(n/2) + 𝑛3 , T(1) = 1
Suggested Ans:
The applications of the Master Theorem yield the following.
i) T(n) = 4T(n/2) + n. Here, a = 4, b = 2, and d = 1. Since a > 𝑏 𝑑
T(n) ∈ Θ(𝑛log2 4 ) = Θ(𝑛2 ).
i) T(n) = 4T(n/2) + 𝑛2 . Here, a = 4, b = 2, and d = 2. Since a = 𝑏 𝑑 ,
T(n) ∈ Θ(𝑛2 log n).
ii) T(n) = 4T(n/2) + 𝑛3 . Here, a = 4, b = 2, and d = 3. Since a < 𝑏 𝑑 ,
T(n) ∈ Θ(𝑛3 ).
