•/:

00284

Sri Lanka Institute of Information Technology

B.Sc. Honours Degree in Information Technology

Specialized in Information Technology

Final Examination
Year 2, Semester 2 (2022)

IT2070 -Data Structures and Algorithms

Duration: 2 Hours
June 2022

Instructions to Candidates :

• This paper has 4 questions.

• Answer all questions.
• The total marks for the paper is 80.
• Electronic devices capable of storing and retrieving text, including calculators and
mobile phones are not allowed.

Page 1 of 5
 oo284\
Question 1 (20 marks)

1) Taking modulo g = 100, how many spurious hits and valid hits do the Rabin -Karp matcher
encounterin the text T = 900800600300900 when looking forpattemp= 600? (2 marks)

2) Draw the state transition diagram for a string-matching automation for the pattern P = ¢b¢b
and take the input alphabet z: as {o,b}. (6 marks)

3) Following is the Nat.ve-String-Matcher Algorithm, which is used to find the occurrence(s)

of a pattern string within another string or body of text. (4 marks)

Na:ive-String-Matcher (I , P)

1. n+length[T]

2. in+length[P]

3. fors+Oton-in

4. do if prl..ml = Trs+1..s+ml

Given the text and pattern as follows; (2 marks)

Text 7. Pattern P

1 0 0 0 1 0 0 0 1

a) How many comparisons would occur in this algorithm?

b) Show that best-case time complexity of the above algorithm is a((" -in + 1)) where n
is the number of characters in the text and in is the number of characters in the pattern.

4) Given a chain (4'`42' .... '4#-l'4) of # matrices, where for I. = 1,2 ,..., # matrix 4 has
dimension PJ-I X PJ-. Assume that "[z.,/.] is the minimum number of scalar multiplications

neededtocompute thematrix 4 J =4X4+1X ..... X`4J~l x4 anditisdefinedbelow u

J"[Z., /.] -
. <mfr]± ,.{m[z.,fr] "[fr + 1,/.]} + p,_]pkp, otherwise
(0 if ,.-/.
Consider the following set of metrics4 , J42 , 4 and Z{4 with their dimensions of 2 X 5 ,
5X5, 5X10 and l0X20 respectively. (8 marks)
a) Draw the 777 and a table to find the optimal parenthesizing of the matrices for the
above sequence of matrices using the dynamic programming algorithm.
b) Hence find the optimal parenthesizing and optimal number of scalar multiplications
of the above matrices

Page 2 of 5
 00284
Question 2 (20 marks)

1) The power function can be defined as pow(x, rl) = xn. This can be evaluated using the
multiplicationasX"=XXX"-]wherexisanyrealnumberand#isanon-negativeinteger.
[Hint: pow(x,7i -1) = rn-t] (8 marks)

a) Write a recursive relation for pow(x,7i) where x is any real number and # is a non-
negative
b) Write a recursive algorithm in pseudo code for the above recursive relation
c) Write a recurrence equation that describe the ruining time T (#) for the above part b)
recursive algorithm.

2) Analyze the running time of the following program fragment assuming a RAM model of
computation.

-, sum + 0
for Z. + JZ down to 0
(4 marks)

sum = sum + 1
3) Given below is an algorithm for gz/JCKsOR7'(4 p, 7')

Procedrre QUICKSoRT (A, p, r)

1 ifp<r
2 thenq-pARTITloN(A, p, r)
3 QUICKSORT (A, p, q-l)
4 QUICKSORT (A, q+l, r) --

Procedme PARTITION(A, p, r)
1 x-4[r]
2 i-p-1
3 for/.+pto7.-1
4 do if4ly.] Sx
5 thenz.+z.+ 1
6 exchange 4 [J.] ® £4 ly.]
7 exchange4[z.+ 1] <+j4[r]
8 return z. + 1

Illustrate the operations of the gurcKSoRr r24, p, r/ for the array with the given set of
elements. (For the illustration process assign the values only once to the given algorithm
codes and then use diagrammatic way to reach the answer.) (4 marks)

1234 56

4) Is the sequence representing <40, 25,19, 6,13,18, 20, 5, 7,12> a max heap? Justify your
answer. (4 marks)

Page 3 of 5
 00284\
Question 3 (20 marks)

1) Consider the following two link lists. Write the code segment to convert link list A to link
list B. (4 marks)

Link list A

ELE=-nu"
first last

Link list 8

ELE=-nu,,
first last

2) Consider the below link class and implement the method deleteLast() in the link list class
to remove the last link from the linklist. (4 marks)
Link class
int iData;
Link next;
Link(int id)
void displayLink()

3) Following numbers are inserted to a binary search tree.

Dwia:§|4:5£be;i7::*:;S;e£C;i:er;er:;:5§neo:;in:::o::en;;::lot?ee?numbers (::in:a:k:}

AssumeyouhaveNnodesinabinarysearchtreeofthetypegivenini)above.Findthe
rurming time in Big 0 notation when searching a value from this tree. Give reasons for
(3 marks)
your answer.
V. What is the running time in Big 0 notation when searching a value from a link list with N
no of links? Give reasons for your answer. (2 marks)
Vl. Comment on the speed of the two data structures (with large N values) when searching a
value. (Hint: use the answers given in iv) and v) above) (2 marks)

Page 4 of 5
 00284
Question 4 (20 marks)

1) State one similarity and one difference between Stack and Queue data structure.
(2 marks)
2) You are expected to develop a function to delete the middle element of a given stack.
Note that the stack class is already implemented. You may assume that the stack is
implemented to store integers. (9 marks)

Hint: Use two stacks (stack objects are `''s" and "sl")

Sample input and output is given below.

Input: Stack[] = [1, 2, 3, 4, 5]

Output: Stack[] = [1, 2, 4, 5]

Input: Stack[] = [1, 2, 3, 4, 5, 6]

Output: Stack[] = [1, 2, 3, 5, 6]

The function signature is as follows.

public void deleteMiddle()

()

3) (c) Consider the following circular queue which is impleT=iiented to store integers. Draw
the queue frames after executing each of_the statements. (5 marks)

0123456

12 2 8 4

/\
front rear

(i) insert (10)

(ii) peekFront()
(iii) insert (22)
(iv) remove ()
(v) insert (18)
5) Consider a linear queue to store double values. Implement a method to calculate the mean
value of the cuITently available values in the queue and insert it to the same queue. Note
that the queue class is already implemented and assume the queue object is "q". ( 4 marks)

Page 5 of 5