Design and Analysis Algorithm BS/MPhil Computer Science/MS Computer Science 4 Semester/Term University Of Sargodha (UOS) 2018

University of Sargodha

BS 4"" Term Examination 2018

Subject: Computer Science

Paper: Design and Analysis of Algorithms (CS-3143)

Time Allowed: 2:30 Hours

Maximum M ks: 80

Note: Objective part is compulsory. Attempt any four question: frot. snojective part.

Objective Part

(Compulsory)

Q.1.

/i.

vii.

/

ix.

X.

ili.

V

xi.

iv.

xii.

V

V.

/

vi.

Write short answers of the foliowin

What is algorithm optimality?

What are the different complexities

according to which we analyse any

algorithm?

What is Merge sort? And is insertion soit

better than the merge sort?

What is NP hard and NP complex

problems?

Define feasible and optimal solution.

/xili.

Write down three cases of Master Method

xiv.

forsolving recurrences.

vii.* Which sorting algorithm will perfor. t

if array is already sorted?

What are the drawbacks of dy

programming?

ustadni.com

xvi.

3 lines escli on your answer sheet.

Differentiate between dynamic

programming and greedy approach

What is the time complexity of prims

algorithm?

How problems are solved using Divide and

Conquer approach?

What are the constantans of knapsack

problem?

Define all pair shorted path problem.

Write an algorithm using Recursive

function to find sum of n numbers.

What is the major difference between

Dijkstra and Bellman Ford Algorithm?

*11.

Write down the recursive solution for Flos

warshall algorithm.

ustadnl.co

Subjective Part

(4*12)

Write down the algorithm for insertion sort and calculate its worst case time complexity.

Consider the following algorithm

Algorithm Enigma (A[O.. n-1, 0..

n-1))

for i → 0 to n-2 do

for 1 + i+1 to n-1 do

1E Ali, İl - Alİ, 1]

return false

end for

end for

return

true

end algorithm

i.

ii.

ill.

What does this algorithm compute?

iv.

What i:

What is its basic operation?

How many times is the basic operation

V.

Can this algo

executed?

(3 Marks]

Q.4.

Calculate the 'M' and 'S' matrices for matrix chain multiplication prob

matrices. Also find out the optimal parenthesis from 'S' matrix.

Ai: 2 x 3

Az: 3 × 5

A,: 5 x 2

A4: 2x4

As: 4 × 3

Q.5.

For the activity selection problem, suppose that instead of always sel cting t

we select the last activity to start that is compatible with all previously selected activities.

i.

її.

ili.

0.6.

Does this approach works?

[02 Marks]

If this approach works, write down the algorithm that implements this approach. (08 M-

Which technique is used in the solution (D.P or Greedy or D&C)?

[02 Marks]

ustadni.col

Run Floyd-Warshall algorithm on the following graph and calcuate both the matrices.

Jar.

Define a finite automaton to match pattern ababc over alpl.

text caabgabcabababccb.

ustadni.com

Visi

https://tshahab.blogspci.com t

for me

visit website: ustadni.com