and 5 others joined a min ago.
0
1.3kviews
Analysis Of Algorithms Question Paper - May 18 - Computer Engineering (Semester 4) - Mumbai University (MU)
1 Answer
0
4views
written 5.4 years ago by
teamques10
★ 64k
|
Analysis Of Algorithms - May 18
Computer Engineering (Semester 4)
Total marks: 80
Total time: 3 Hours
INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Make Suitable assumptions wherever necessary and justify it.
(4) Figuers to right indicate full marks.
Q1 Answer the following
a)
Write the difference between greedy method and dynamic programming.
(5 marks)
00
b)
Explain the general procedure of divide and conquer method.
(5 marks)
00
c)
Determine the frequency counts for all statements in the following algorithm segment.
(5 marks)
00
I=1;
While(I<=n)
{
X=X+1;
I=I+1;
}
d)
What is backtracking Approach? Explain how it is used in Graph coloring
(5 marks)
00
Q2
a)
Explain with example how divide and conquer strategy is used in binary search?
(10 marks)
00
b)
Solve sum of subsets problem for following
(10 marks)
00
N=6 W={3,5,7,8,9,15} & M=20 Also write the algortihm for it.
Q3
a)
Obtain the solution to knapscak problem by Greedy method n=7,m=15 (p1,p2.....p7) = (10,5,15,7,6,18,3), (w1,w2,.....,w7)=(2,3,5,7,1,4,1).
(10 marks)
00
b)
Sort the list of the elements 10,5,7,6,1,4,8,3,2,9 using merge sort algorithm and show its computing time is O(n logn).
(10 marks)
00
Q4
a)
Explain different string matching algorithms
(10 marks)
00
b)
What do you understand by NP complete? Explain Is subset sum problem NP complete? If so explain.
(10 marks)
00
Q5
a)
Write a detailednote on Hamiltonian cycles.
(10 marks)
00
b)
Explain how backtracking is used for solving n-queens problem. Show the state space tree.
(10 marks)
00
Q6 Write Short Note on (Any 2):
a)
Job sequencing with deadlines
(5 marks)
00
b)
8 queens problem.
(5 marks)
00
c)
Longest common subsequence.
(5 marks)
00
ADD COMMENT
EDIT
Please log in to add an answer.