Design and Analysis of Algorithm BS/MPhil Information Technology/MS Information Technology 5 Semester/Term University Of Sargodha (UOS) 2022

19BS IT 29394

University of Sargodha

BS 5th Term Examination 2022

Subject: Information Technology Caper: Design & Analysis of Algorithms (ITSC-305)

Time Allowed: 02:30 Hours

Maximum Marks: 80

Note: Objective part is compulsory. Attempt any three questions from subjective part.

Objective Part (Compulsory)

ustadni.

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

Describe NP-complete problems.

Write two limitation of array data structure

Give a real-world example that requires Sorting.

Define O notation mathematically in term of function.

V.

VI.

vii.

What is the worst case running time of Heap Sort Algorithm?

Is the array with values /23, 17, 14, 6, 13,

10. 1.5,

7. 12) a max-heap?

Give the adjacency-matrix representation of the following graph.

(2*16)

ustadni.com

vili.

ix.

x.

xi.

xii.

xiv.

XV.

xvi.

What is Directed graph? Give an example.

Define aeyelic graph.

Give an example of DAG.

What are the properties of Binary search tree?

What is the time complexity of Algorithm?

What are the fundamental steps involved in algorithmic problem solving?

What is pseudocode?

What are the types of algorithm efficiencies?

What is best-case efficiency?

Subjective Part

(3*16)

Q.2.

Q.3.

What kinds of problems are solved by algorithms? Support your answer with examples.

Suppose we are comparing implementations of insertion sort and merge sort on the same machine.

For inputs of size n. insertion sort runs in 8n? steps, while merge sort runs in 64m Ig n steps. For which

values of n does insertion sort beat merge sort?

Q.4.

Calculate running time in terin of asymptotic notation of following algorithm and mention running

time and cost of each line.

Insertion-sort(A)

i.

ii.

for j = 2 to A.length

key = AU

ili.

I/insert AL] into the sorted sequence A[1 --. j- 1].

iv.

i = j - 1

V.

While i > and and A[> key

vi.

Ali + 1] + A(i

vii.

i= i -1

viii. © 4[i + 1] = key

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

ustao

can he solved in time t, assuming fat the algorithm to solve the problem takes / (r) microseconds.

Second

minute

hour

day

month

year

century

Q.6.

Nign

Write the Bellman Ford Algorithms and give the analysis.

•---- LK-6718 --

ustadn

Scanned with Can

StadriScamer