Design and Analysis of Algorithm BS University Of Sargodha (UOS) 2023

University of Sargodha

BS Sill Term Examination 2023

Subject: LT

Paper: Design & Analysis of Algorithms (ITSC-305)

Maximum Marks: 60

Time Allowed: 02:30 Hours

Note:

Objective part is compulsory. Affempt any three questions from subjective part.

usta@ni.com

Objective Part

(Compulsory)

Write short answers of the following in 2-3 lines each on your answer sheet.

(2*12)

Express the function n/1000 - 100n' - 100n+ 3 in terms of e notation.

H.

Define O notation mathematically in term of function.

ili.

What is the smallest value of n such that an algorithm whose running time is 100n? runs faster

than an algorithm whose running time is 2ª on the same machine?

iv.

V.

vi.

vii.

viii.

What is Dynamic Programming?

Define randomized algorithm.

istadni.com

What are the minimum and maximum numbers of elements in a heap of height h?

What is the running time of MAX-HEAPIFY PROCEDURE?

Give the adjacency-matrix representation of the following graph

ix.

X.

xi.

xii.

Q.2.

Q.3.

Q.5.

Q.6.

Mention some of the important problem types.

What are exponential growth functions?

What is worst-case efficiency?

List the strength and weakness of brute force algorithm.

Subjective Part

(3*12)

Solve the following recurrence relation using master method OR substitution method

T (n) =3T (n/4) +n Ig n.

For each function f (n) and time t in the following table, determine the largest size n of a problem

that can be solved in time t, assuming that the algorithm to solve the problem takes f (n

microseconds.

1 second

1 minute

1 hour

1 day

1 month

1 year

1 century

Lg n

Vn

Solve the following recurrence relation using master method or substitution method

T(n)=9 T(n/3)+n

Calculate Huffman code for the following string BCAADDDCCACACAC.

Execute Kruskal's algorithm on the following graph starting from edge B=(h.g),

00)

9

ustadni!

11

10

Scanned with CamScanne

ustadni con