M.C.A. S.Y. (Part II) Examination Nov/Dec-2018
Engg
DESIGN AND ANALYSIS OF ALGORITHM
iI
Time 2½ Hours Max. Marks: 70
Instructions: All questions are compulsory.
Figures to the right indicate full marks.
Q.1 Multiple choice questions: 14
GCD is
1 2
3 4D
8 queen's problem is solved by
Backtracking Branch and Bound
Greedy method None of these
If tree is having m levels then the total node in the tree is
− 1
∗ −1
There are steps to solve the problem.
Seven Four
Six Two
is the first step in solving the problem.
Understanding the Problem Identify the Problem
Evaluate the Solution None of these
is the last step in solving the problem.
Understanding the Problem Identify the Problem
Evaluate the Solution None of these
Following is true for understanding of a problem.
Knowing the knowledgebase
Understanding the subject on which the problem is based
Communication with the client
All of the above
The six-step solution for the problem can be applied to
Problems with Algorithmic Solution
ii) Problems with Heuristic Solution
Only I Only II
Both I and II Neither I nor II
solution requires reasoning built on knowledge and experience.
Algorithmic Solution Heuristic Solution
Random Solution None of these
10) While solving the problem with computer the most difficult step is
Describing the problem
Finding out the cost of the software
Writing the computer instructions
Testing the solution
11) The correctness and appropriateness of solution can be checked
very easily.
Algorithmic solution Heuristic solution
Random solution None of these
12) The branch of computer that deals with heuristic types of problem is called

System software Real time software
Artificial intelligence None of these
13) Artificial Intelligence makes use of following prominently
Database Data Warehouse
Knowledge base None of these
14) The true and false values represent
Logical data Numeric data
Character data Alphanumeric data
15) Following operator distinguishes equation from expression.
or
Logical operator Assignment Operator
16) Following are called logical operators

AND, OR, NOT MOD
17) Evaluate where b=8
False True
6 7
18) Evaluate for 12 for the equation
40 24
10 10.66
19) The PAC stands for
Program Analysis Chart Problem Algorithm Code
Problem Access Code Problem Analysis Chart
20) In interactivity chart the darkened circle indicates
Duplicate module Loop
Decision No special meaning
SECTION I
Q.2 Write short note on following: (Any Four) 20
Time complexity
Asymptotic notation
Optimal merge pattern
Heap
Algorithm characteristics
Q.3 Explain rules for step count method to calculate time complexity? Write
algorithm and calculate step count using table method for algorithm to
display Fibonacci series up to N nos.
10
List out different asymptotic notation with their key characteristic and
explain big O notation in detail.
10
OR
Explain algorithm characteristics and algorithm specifications. 10
SECTION II
Q.4 Write short note on following. (Any Four) 20
Greedy method
Divide and conquer method
Branch and Bound techniques
Radix sort
Bi-connected components
Q.5 Write algorithm for merge sort using Divide and Conquer method?
Sort the list 20, 30, 40, 10, 50, 60}.
10
Describe the terms heap, max heap and min heap. Explain sort operations
of heap with suitable example.
10
OR
Explain selection sort method? Write algorithm and sort the array
11, using selection sort method.