## 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