CS502 Assignment No.1

[ayesha]

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

Question # 2: 10 Marks

Find the 19thsmallest 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)

[nazia]

assignment ka solve dey do koi

[Esshakanwal]

es ka tora sa idea solution da do koi 

[ayesha]

ksi k pas koi b idea nh ha? big oh of best case ka topic to handouts ma b nh ha

[ayesha]

[Uzair Ahmad]

Please listen the videos of lecture # 3 & 4 for first question and videos of lecture # 10 & 11 for second question;
all these concepts have been discussed in detail there.

[ayesha]

thanks

[+★._.• Cutie Pie•._.★]

es br khair nhiii  subj e bht ajeeb saree 

[Hamza Hameed]

Yr

[Hamza Hameed]

Really bad.

[Rose]

plz tell me.. while or if loop  kitne br access hungy ??

[Dildar Hussain]

Plz listen lec#3 for line by line Analysis and listen lec#7 for Big-oh
Listen Lec#10 for 2nd question

[dastgeer194@]

Answer of Question # 2 

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,

Rank_X =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,  

Rank_x =2, Recurse K= (8-2)=6 , Partition Pivot = 13

Pivot is 590

 526,573, 525, 583, 416, 590, 933, 782, 904, 859, 627, 631,

Rank_x =6, K=6 , Partition Pivot = 19

So the 19^th Smallest from the given array is 590.

Remember in your prayers!