Design & Analysis of Algorithms BS 4 Semester/Term UOS — University of Sargodha 2021

University of Sargodha

BS 4th Semester/Term Exam 2021

Subject: Computer Science

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

Time Allowed: 02:30 Hours

Maximum Marks: 80

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

Objective Part (Compulsory)

Q.1. Write short answers of the following in 2-3 lines each on your answer sheet. (2*16)

i. What is an Algorithm?

ii. What is a heap?

iii. What is recursion?

iv. What is time complexity?

v. What is a sorting

vi. What is divide-and-conquer approach?

vii. What are the Red-Black trees?

viii. What do you know about growing a minimum spanning tree?

ix. What is Big O notation?

x. Differentiate the Matroids and Greedy methods.

xi. What is Task Scheduling Problem?

xii. What do you know about Topological Sort?

xiii. What do you know about Bellman Ford Algorithm?

xiv. What do you know about Dijkstra's Algorithm?

xv. Shortly describe Floyd-Warshall Algorithm.

xvi. How can you describe the Johnson's Algorithm for Sparse Graphs?

Subjective Part (3*16)

Q.2. Explain the procedure for the algorithm of depth first search.

Q.3. Explain Dijkstra's algorithm. For what purpose it is executed? Describe it with an example run.

Q.4. What is Ford-Fulkerson Method? Explain it pseudocode and run it with an example?

Q.5. What is Dynamic Programming? Explain some of its algorithm with the help of an example.

Q.6. What are binary search trees? Explain some of its algorithm by using the set of keys {11, 4, 15, 10, 6, 2, 26} and draw their respective binary trees.