Describe class P, NP and NP-Complete problems.
[3 marks]Explain Asymptotic notation.
[4 marks]Explain Multiplying large integers problem and its solution using Divide and Conquer strategy.
[7 marks]Write characteristics of Best case, Average case and Worst case of algorithm.
[3 marks]State and explain Master’s method to solve recurrence equation.
[4 marks]Compare and analyze Insertion sort and Heap sort.
[7 marks]Compare and analyze Bucket sort and Radix sort.
[7 marks]Describe Activity selection problem and find solution for given details. Id A1 A2 A3 A4 A5 A6 A7 Start time 5 1 3 2 5 8 End time 8 2 4 5 7 9
[8 marks]Explain fractional knapsack problem and solution with example.
[4 marks]Write and Explain Krushkal’s algorithm with example. Show algorithmic steps in example.
[7 marks]Describe Job scheduling algorithm and find solution for given details. Number of jobs N = 4. Profits associated with Jobs : (P1, P2, P3, P4) = (80, 20, 13, 32). Deadlines associated with jobs (d1, d2, d3, d4) = (2, 1, 3, 2)
[3 marks]Explain Huffman code with example.
[4 marks]Write and Explain Prim’s algorithm with example. Show algorithmic steps in example.
[7 marks]State and describe principle of optimality.
[3 marks]Describe the naive string matching algorithm.
[4 marks]Explain All points shortest path using dynamic programming with example.
[7 marks]Differentiate Greedy strategy and Dynamic programming.
[3 marks]Describe the Rabin-Karp algorithm.
[4 marks]Explain Longest common subsequence with example.
[7 marks]State limitations of Divide and Conquer strategy.
[3 marks]Describe DFS algorithm with example.
[4 marks]Explain travelling salesman problem using branch and bound strategy with example.
[7 marks]Describe Topological sorting in graphs.
[3 marks]Explain BFS algorithm with example.
[4 marks]Explain Eight queens problem using backtracking strategy with example.
[7 marks]