# Design and Analysis of Algorithms Past Papers Exam Questions

By Prof. Fazal Rehman Shamil

## Guess Paper 1:Design and Analysis of Algorithms Fall – 2020 Past Papers

Time Allowed: 3 hours

Total Marks:    70, Passing Marks (35)

Q.1 Attempt all parts of this question. (30 marks)

A. Write down True or False for the following (10 marks)

I. Data Structure refers to the permanent storage and manipulation of data
II. Array is a linear Data structure
III. Algorithms are platform independent but they can be implemented only in one procedural language
IV. Asymptotic notation  represents greater than between two functions f(n) and g(n)
V.
B. Choose the correct option. (10 marks)

I. An algorithm is defined as
i. a mathematical formula that solves a problem.
ii. a tempo for classical music played in a coda.
iii. a logical sequence of a steps that solve a problem.
iv. a tool that designs computer programs and draws the user interface
II. Two main measures for the efficiency of an algorithm are
i. Processor and memory
ii. Complexity and capacity
iii. Time and space
iv. Data and space
III. Which of the following case does not exist in complexity theory
i. Best case
ii. Worst case
iii. Average case
iv. Null case
IV. The complexity of the average case of an algorithm is
i. Much more complicated to analyze than that of worst case
ii. Much more simpler to analyze than that of worst case
iii. Sometimes more complicated and some other times simpler than that of worst case
iv. None or above
V. The complexity of linear search algorithm is
i. O(n)
ii. O(log n)
iii. O(n2)
iv. O(n log n)

C. Fill in the blanks. (10 marks)
a. The operation of processing each element in the is known as ______________
b. Array are best data structure for relatively _____________ collections of data
c. The average case occur in linear search algorithm when an item is somewhere in the ________ of the array
d. Algorithm efficiency in terms of time is measured by counting the number of _________
e. Algorithms can be measured in machine independent way using the _________________ model.

Q.2 What do you mean by analysis of algorithms and why analysis of algorithms is important to computer science (10 marks)

Q.3 Write a pseudo code for the binary search algorithm. Argue that worst case running time of binary search is O (lg n) (10 marks)

Q.4 Write a pseudo code for the merge sort algorithm (10 marks)

Q.5 Traverse the following tree using PreOrder, InOrder and PostOrder methods. (10 marks)

Q.6 Write in detail at least two general approaches i.e. algorithm design techniques to the construction of efficient solution to problems? (10 marks)

Q.7 Write short note on any two of the following: (10 marks)
a) Heap Sort
b) Minimum Spanning Tree
c) Greedy Algorithm
d) Quick Sort Prof.Fazal Rehman Shamil (Available for Professional Discussions)
1. Message on Facebook page for discussions,