Design and Analysis of Algorithm BS 5 Semester/Term University Of Sargodha (UOS) 2024

30347

Subject: IT

University of Sargodha

BS 5th Term Examination 2024

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

Maximum Marks: 60

(Compulsory)

Q.1.

(2*12)

i.

-ii.

What are optimization problems?

What do you mean by an optimal solution?

iii.

Whetdo we use algorithms?

iv.

When do we use the master theorem?

V.

vi

When de we use heuristics?

What is the relation between algorithms and data structures?

vil

A program is faster than another right now, means it will always be faster?

vili.

Name an algorithm that has time complexity of O(N Log(N)):

ix.

What is the big-O notation?

x.

Is the time complexity of a program dependent on the hardware platform? Justify.

xiE

Is the time complexity of a program dependent on the compiler? Justify.

xii. 8. What is a sparse graph?

upe.

Subjective Part

(3*12)

Q.2.

Q.3.

Explain Dijkstra's algorithm with the help of an example.

What are the advantages and disadvantages of using dynamic Programming? Also, solve

the factorial (6) problem using dynamic programming.

Q.4.

Q.5.

Q.6.

Differentiate between heapsort algorithm and quick sort algorithm.

Differentiate between breadth-first search and depth-first search techniques.

Show Huffman coding (greedy approach) for a data string that has the tollowing character

Requency.

usta@hi.com

Character

visit website: ustadni.com

E

A

D

C

24

12

10

ustadni.com

.. visit website: ustadni.com