Design and Analysis of Algorithms 214 Final Examination 2005

QUESTION ONE [12 Marks]

(i) Find the number of executions of line number 4 for the fragment of [2 marks]
code given below.

1. for i = 1 to n
2. for j = 1 to n2
3. for k = 1 to n3
4. k[i][j] [k] = i* j*k
5. end for
6. end for
7. end for

(ii) Analyze the running time of the following program fragment assuming a [3 marks]
RAM model of computation.
for i ← n -1 down to 0
print i

(iii) Define the Big O value for a given function f ( x ). [1 mark]

(iv) Write an recursive algorithm in psedocode that computes the number [6 marks]
of 1's in the binary representation of a non-negative integer n.
[Hint: For example if n = 15 your program should return 4 since the
binary representation of 15 is 1111.]

QUESTION TWO [21 marks]

PART (a)

(i) Following is an algorithm for INSERTION-SORT which takes an array A [3 marks]

as input.
INSERTION-SORT (A)
1 for j ← 2 to length [A]
2 do key ← A [j]
3 > insert A [j] into the sorted sequence A [1..j-1]
4 i ← j-1
5 while i >0 and A [i] > key
6 do A [i+1] ← A [i]
7 i ← i –1
8 A [i+1] ← key

Illustrate the operation of INSERTION-SORT on the array A given below.

A
6 2 1 5 8

Page 1 of 9
_____________________________________
Sri Lanka Institute of Information Technology
Design and Analysis of Algorithms 214 Final Examination 2005

(ii) What is a recurrence equation? [1 mark]

(iii) The equation below represent the Ackermann’s function. Where i and [5 marks]
j are integers.

 2j i = 1 and j ≥ 1

A(i, j ) =  A(i − 1,2) i ≥ 2 and j = 1
 A(i − 1, A(i, j − 1)) i, j ≥ 2


a) Use the above equations to manually compute A(1,2) and A(2,2) .

b) Identify the base component and recursive components of the
function definition.

PART (b)

(i) What are the advantages of Divide & Conquer method? [1 mark]

(ii) The pseudocode for merge sort is given below [5 marks]

Procedure MERGESORT (A,p,r)

1. if p < r
2. then q ← floor( (p + r)/2 )
3. MERGESORT (A, p, q)
4. MERGESORT (A, p, q)
5. MERGE (A, p, q, r)

Procedure MERGE (A,l,q,r)

1. i ← l
2. j ← q+1
3. k ← 0
4. while (i ≤ q) and ( j ≤ r) do
5. k ← k+1
6. if A[i] ≤ A[j] then
7. TEMP [k] ← A [i]
8. i ← i +1
9. else
10. TEMP [k] ← A [j]
11. j ← j +1
12. if j > r then
13. for t ←0 to q – i do
14. A [r-t] ← A [q-t]
15. for t ← 0 to k-1 do
16. A [l +t] ← TEMP [t +1]

Page 2 of 9
_____________________________________
Sri Lanka Institute of Information Technology
Design and Analysis of Algorithms 214 Final Examination 2005

(a) Illustrate how the partitioning is done with the MERGESORT

procedure for the array given below [Note that you don’t need to
illustrate how the merging is done with MERGE procedure]

A
3 1 8 4 5 4 9

(b) Why is the purpose of line numbers 13 and 14?

(c) Write a recurrence equation, which represent the running time of
merge sort algorithm.

PART(c)

(i) Find the height of a complete binary tree, which contains n number of [1 mark]
nodes.
(ii) The following are the algorithms for Heap sort, Build Heap and Heapify. [5 marks]

Input : Array A[1…n], n = length[A]

Output : Sorted array A[1…n]

Procedure HEAPSORT(A)
1. BUILD_HEAP[A]
2. for i ← length[A] down to 2
3. Exchange A[1] ↔ A[i]
4. heap_size[A] ← heap_size[A]-1;
5. HEAPIFY(A,1)

Input : An array A of size n = length [A], heap_size[A]

Output : A heap of size n

Procedure BUILD_HEAP (A)

1. heap_size[A] ← length[A]
2. for i ← length[A]/2 downto 1
3. HEAPIFY(A,i)

Input: An array A and index i to the array. i =1 if we want to heapify

the whole tree. Subtrees rooted at LEFT_CHILD(i) and
RIGHT_CHILD(i) are heaps
Output: The elements of array A forming subtree rooted at i satisfy
the heap property.

Page 3 of 9
_____________________________________
Sri Lanka Institute of Information Technology
Design and Analysis of Algorithms 214 Final Examination 2005

Procedure HEAPIFY (A,i)

1. l ← LEFT_CHILD (i);
2. r ← RIGHT_CHILD (i);
3. if l ≤ heap_size[A] and A[ l ] > A[ i ]
4. then largest ← l;
5. else largest ← i;
6. if r ≤ heap_size[A] and A[r] > A[largest]
7. then largest ← r;
8. if largest ≠ i
9. then exchange A[i] ↔ A[largest]
10. HEAPIFY (A,largest)

Illustrate the operations of the Heap sort for the heap given below.

9 8

5 4 6 7

QUESTION THREE [18 marks]

PART (a)

(i) Draw the graph that is represented by Adjacency matrix given below. [1 mark]

0 1 0 1
0 0 1 1

1 1 0 0
 
1 1 1 0

(ii) Draw the Directed graph if V={1,2,3,4,5} and [1 mark]

E={(4,2),(2,3),(2,4),(3,5),(5,1),(1,2),(1,3)}

(iii) What is a Hamiltonian cycle in a graph? [1 mark]

Page 4 of 9
_____________________________________
Sri Lanka Institute of Information Technology
Design and Analysis of Algorithms 214 Final Examination 2005

(iv) Briefly explain with an example how the traversing is done in a graph [3 marks]
with Depth First Searching (DFS) and Breadth First Searching (BFS)
methods and what data structure should be used for each searching
methods?

PART (b)

(i) What is a Minimum Cost Spanning Tree (MCST) of a graph? [1 mark]

(ii)
12
B E
15
22

10 D 40
A

30
25 C F
8

(iii) The algorithm for the Kruskal’s algorithm is given below. [5 marks]

Input: An undirected graph G(V,E) with a cost function c on

edges
Output: T the minimum cost spanning tree for G

1 T ← {};
2 Sort the edges of E in non decreasing order of weight c
3. for each edge in E do
4. choose first edge in E, say (v,w) // has lowest cost
5. delete (v,w) from E
6. if v and w are in disjoint sets W1 and W2 do
7. W1 = W1 ∪ W2;
8. T ← T ∪ (v,w);
9. return T

Find the MCST of the graph in (ii) using Kruskal’s algorithm.

(iv) The algorithm for the Dijkstra’s single-source shortest path is given [6 marks]
below.
Input: G =(V,E), the weighted directed graph and u the source vertex
Output : for each vertex, v, d[v] is the length of the shortest path
from u to v.

Page 5 of 9
_____________________________________
Sri Lanka Institute of Information Technology
Design and Analysis of Algorithms 214 Final Examination 2005

Procedure Dijkstra's Single-source shortest path_G(V,E,u)

1. mark vertex u;
2. d[u] ← 0;
3. for each unmarked vertex v ∈ V do
4. if edge (u,v) exists d [v] ← weight (u,v);
5. else d[v] ← ∞ ;
6. while there exists an unmarked vertex do
7. let v be an unmarked vertex such that d[v] is
minimal;
8. mark vertex v;
9. for all edges (v,x) such that x is unmarked do
10. if d[x] > d[v] + weight[v,x] then
11. d[x] ← d[v] + weight[v,x]

Using the above Dijkstra’s Single-source shortest path algorithm, find

the length of the shortest path from the node A to all other nodes on the
graph shown below.
20
F
B
75
80 30 45
60
A D 50
E
40 15

C 55

QUESTION FOUR [15 marks]

(i) a) Taking modulo q = 12, how many spurious hits and valid hits do [5 marks]
the Rabin-Karp matcher encounter in the text T = 22531491349
when looking for pattern P = 49?

b) What can you do to reduce the number of spurious hits in (a)?

c) What should be the number of spurious hits and valid hits if best-
case scenario occurs in Rabin-Karp algorithm?

Page 6 of 9
_____________________________________
Sri Lanka Institute of Information Technology
Design and Analysis of Algorithms 214 Final Examination 2005

(ii) Draw the state transition diagram for a string-matching automaton for [5 marks]
the pattern P = bbaba and illustrate its operation on the text string T =
aabbabaababba. Take the input alphabet ∑ as {a,b}

(iii) Following is the Naïve-String-Matcher Algorithm, which is used [5 marks]

to find the occurrence(s) of a pattern string within another string
or body of text.

Naïve-String-Matcher (T, P)
1. n ← length[T]
2. m ← length[P]
3. for s ← 0 to n-m
4. do if P[1..m] = T[s+1..s+m]
5. then print "Pattern occurs with shift" s

Given the text and pattern as follows

Text T Pattern P
b b a b c c a b c b a b

a) What will be the output from this algorithm?

b) How many comparisons would occur in this algorithm?
c) Show that worst-case time complexity of the above algorithm is
O(m(n − m + 1)) where n is the number of characters in the text
and m is the number of characters in the pattern.

QUESTION FIVE [15 marks]

(i) What do you mean by data compression? [1 mark]

(ii) What is “Entropy”? Write an equation to find the entropy for a given [2 marks]
message?
(iii) Construct the codeword for the following message using Huffman [4 mark]
Algorithm.
[Hint: You may use either probabilities or frequencies for calculations]

beabebaeccdcece

Page 7 of 9
_____________________________________
Sri Lanka Institute of Information Technology
Design and Analysis of Algorithms 214 Final Examination 2005

(iv) a) Develop a codeword for following data using Shannon Fano [8 marks]
Algorithm.

Symbol A B C D E F
Frequencies 8 5 1 3 6 2

b) Develop a codeword for above data using Hu Tucker

Algorithm.
c) If you have used the Unicode for coding the above symbols how
many bits are need to represent these data?
d) Hence find the percentages of compression achieved using
Shannon Fano Algorithm and Hu Tucker Algorithm.

QUESTION SIX [19 marks]

PART (a)

(i) What do you mean by Optimal substructure. [1 mark]

(ii) In the 0/1 knapsack problem we define P(i,k) to be the maximum

profit possible using items i…n and remaining capacity k. We denote
the weight and profit of the ith item by wi and pi .

0 i = n & wn > k
p
P (i , k ) =  n
i = n & wn ≤ k
 P (i + 1, k ) i < n & wi > k
max( P (i +1, k ), pi + P (i + 1, k − wi )) i < n & wi ≤ k

a. Draw a table for the following 0/1 knapsack problem-using [9 marks]

Dynamic Programming.

n = 4, c = 5, w = [ 1, 3, 4 , 2 ] and p = [ 4, 5, 6, 3 ]

b. Find p (3,2) , p (3,5) , p (2,5) and p (1,4) .

c. Fill all the entries of the table using above equations.

d. Briefly explain how you achieve the final solution.

Page 8 of 9
_____________________________________
Sri Lanka Institute of Information Technology
Design and Analysis of Algorithms 214 Final Examination 2005

(iii) Given a chain ( A1 , A2 ,...., An−1 , An ) of n matrices, [4 marks]

where for i = 1,2, …, n matrix Ai has dimension pi −1 × pi .
Assume that m[i,j] is the minimum number of scalar multiplications
needed to compute the matrix Ai... j = Ai × Ai +1 × ..... × A j −1 × A j and it is
defined below

0 if i = j
m[i, j ] =  min
i ≤ k < j {m[i, k ] + m[k + 1, j ]} + pi −1 pk p j otherwise

Consider the following set of metrics with their dimensions.

Matrix Dimensions
A1 20 × 10
A2 10 × 5
A3 5× 4
A4 4×8

Using the above equations find m[1,3] and m[2,4].

PART (b)

(i) What are the steps in the backtracking method? [1 mark]

(ii) What is the difference between backtracking and branch and bound [1 mark]
method?
(iii) The following is a 0/1 Knapsack problem. [3 marks]

n = 4, c = 5, w = [ 1, 3, 4 , 2 ] and p = [ 4, 5, 6, 3 ]

a) Define the solution space and organize it on a tree to find the

solution with backtracking method.
b) Find the solution and verify with the dynamic programming
solution in the above part (ii) in Part(a).

Page 9 of 9
_____________________________________
Sri Lanka Institute of Information Technology