Design & Analysis of Algorithms/Design and Analysis of Algorithm/Advance Analysis of Algorithms BS/MPhil Computer Science/MS Computer Science 4 Semester/Term University Of Sargodha (UOS) 2024

Subject: Computer Science

Time Allowed: 02:30 Hours

30226

University of Sargodha

BS 4th Term Examination 2024

Paper: Design & Analysis of Algorithms (CS-3143/CSCC-202)

Maximum Marks: 60

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

ustadni.

Objective Part

(Compulsory)

Q.1.

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

2*12)

i.

What is correctness of an algorithm?

il.

Define best case complexity.

ili.

stadni.

Give a real-world example that requires sorting or a real-world example that requires computing a

convex hull.

iv.

What is a stable algorithm?

V.

Give worst-case running time using big theta notation for insertion sort.

vi.

Given worst case complexity of Strassen's algorithm.

vii.

Is 22" is O(2")? Why?

viii.

When Johnson's algorithm is used?

ix.

Why Huffman codes are optimal?

X.

What is a knapsack 0-1 problem?

xi.

What is an advantage of using adjacency matrix representation over adjacency list representation?

xii.

When Rabin-Karp algorithm is used?

Q.2.

Q.3.

Q.4.

Q.5.

Q.6.

Subjective Part

(3*12)

Give an algorithm for locating the last occurrence of the smallest number in a list of integers.

Estimate the number of comparisons used.

Let Fn denote the nth Fibonacci number. Write an algorithm to find n?-th Fibonacci number in

O(log n) time.

Derive how many edges are required for a graph Qn.

Given a directed acyclic graph, design an efficient algorithm to determine whether there is a

positive weight cycle in the graph? Derive complexity of the algorithm.

Why Dijkstra's algorithm may fail on negative weights (not necessarily cycle)? Give an example

graph where it fails and Bellman-Ford's algorithm does not fail?

ustad

ustadni.com

LK-5460, 5493/15-01-24

ustadni.com