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

University of Sargodha

BS 5' Term Examination 2024

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

Subject: 111

Time Allowed: 02:30 Hours

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

Maximum Marks: 60

Objective Part

(Compulsory)

Q.1.

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

What are optimization problems?

(2*12)

What do you mean by an optimal solution?

Fili.

When do we use algorithms?

When do we use the master thorem?

V.

-vi.

vil

vill.

ix.

X.

oRi.

xii.

When do we use heuristics?

What is the relation between algorithms and data structures?

com

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

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

What is the big-O notation

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

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

What is a sparse graph?

VQ.2.

0.3.

7Q.4.

0.5.

10.6.

Subjective Part

(3"12)

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.

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 following character

frequency.

Character

E

A

Frequency

24

12

10

ustadni.com

C

ustadi

bms

- LK-6718/30-05-24-

nstadni.com