Computer Engineering (Semester 4)
TOTAL MARKS: 80
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks.
1 (a) Explain Divide and Conquer strategy. Write control abstraction (general method) for it. List any four examples that can be solved by divide and conquer.(10 marks)
1 (b) Explain asymptotic notations. Explain time complexity and space complexity in detail.(10 marks)
2 (a) Explain Graph Colouring problem using backtracking. Write algorithm for same.(10 marks)
2 (b) Find out single source shortest path for following problem using Dijkstra's Algorithm.
(10 marks)
3 (a) Find the longest common subsequence from the given two sub-sequences:-
P = {100101101101}
Q = {0110}(10 marks)
3 (b) Explain 15 puzzle problem using Branch and Bound.(10 marks)
4 (a) Sort following numbers using Quicksort algorithm.
65, 70, 75, 80, 85, 60, 55, 50, 45.
Show all passes of execution. Also state the time complexity.(10 marks)
4 (b) Explain and write Knuth-Morris Pratt algorithm. Explain with an example.(10 marks)
5 (a) Explain job sequencing with deadlines. Solve the following instance: n=5
(P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1)(d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3)(10 marks)
5 (b) Solve the following sum of subset problem using backtracking:
w= {1, 3, 4, 5}, m=8.
Find the possible subsets of 'w' that sum to 'm'.(10 marks)
6 (a) Solve shortest path from source 1 for following graph using dynamic programming.
(10 marks)
6 (b) Explain travelling Salesperson Problem using branch and bound method.(10 marks)
Write short notes:-
7 (a) Differentiate between greedy approach and dynamic programming.(5 marks)
7 (b) Optimal Storage On Tapes(5 marks)
7 (c) Radix Sort(5 marks)
7 (d) Minimum Spanning Tree using Kruskal's algorithm.(5 marks)
and 3 others joined a min ago.
teamques10
★ 68k
sagarkolekar
★ 11k