CS502
BC150401835
Question # 1: 10
Marks
For
the following code snippet, provide line-by-line analysis and construct
function T(n) that give the runtime of this code snippet as a function of
"n". Also determine the big-Oh of Best-case, Worst-case and Average
case for this code snippet. [Marks:
4+2+2+2]
Search(A, Key)
i ← 1
while (A[i] ≠ key) and
(i ≤ length[A])
i ← i + 1
if ( i ≤ length[A])
return true
else
return false
Answer:
Search(A, Key)
i←1
1 access
while (A[i] ≠ key) and (i ≤ length[A])
n times
i←i+1
1 access
if ( i ≤ length[A])
n times
return true
1 access
else
return false
1 access
T(search) = 1+ 2(n+1)+1+1
=5+2n
so Big O notation will be O(n)
Question # 2: 10
Marks
Find
the 19th smallest element from the array given below using Selection
Algorithm (Sieve Technique); you are required to provide complete procedure
along with array indexing and their values at each step.
933,
782, 116, 276, 904, 353, 416, 157, 277, 583, 525, 208, 269, 98, 181, 859, 573,
225, 526, 627, 631, 590, 257, 402, 335
Note: pivot must be the last element of the array in each
iteration (i.e. q = r)
Answer:
933, 782, 116, 276, 904, 353, 416, 157, 277, 583, 525, 208, 269, 98, 181, 859, 573, 225, 526, 627, 631, 590, 257, 402, 335
Pivot is 335. K=19
257, 225, 181, 98, 269, 208, 277, 157, 276, 116, 335, 933, 782, 904, 353, 416, 583, 525, 859, 573, 526, 627, 631, 590, 402,
RankX =11, Recurse K=(19-11)=8, Partition Pivot = 11
Pivot is 402,
353, 402, 933, 782, 904, 416, 583, 525, 859, 573, 526, 627, 631, 590,
Rankx =2, Recurse K= (8-2)=6 , Partition Pivot = 13
Pivot is 590
526,573, 525, 583, 416, 590, 933, 782, 904, 859, 627, 631,
Rankx =6, K=6 , Partition Pivot = 19
So the 19th Smallest from the given array is 590.