Define Algorithm. Discuss factors affecting time complexity of an algorithm.
[7 marks]Explain Big Oh (O), Omega (Ω) and Theta (θ) asymptotic notations.
[7 marks]Apply merge sort algorithm on array A = {2,7,3,5,1,9,4,8}. What is time complexity of merge sort in worst case?
[7 marks]Define Minimum Spanning Tree. Use Krushkal’s algorithm to find Minimum Spanning Tree of given graph
[7 marks]Discuss any two methods of amortized analysis in detail
[7 marks]Write greedy algorithm for job scheduling problem. Derive its time complexity.
[7 marks]Write divide and conquer algorithm to solve Exponential problem. Also solve 29 using same algorithm.
[7 marks]Obtain longest common subsequence using dynamic programming. Given A = “acabaca” and B = “bacac”
[7 marks]Explain Depth First Search algorithm for a graph with example. Also explain Tree Edges, Back Edges and Cross Edges
[7 marks]Solve making change problem using dynamic programming Given amount N=8, and denominations d = {1, 3, 5, 6}
[7 marks]What is backtracking? How 4-Queen problem is solved using backtracking?
[7 marks]Sort given array A = {27, 46, 11, 95, 67, 32, 78} using insertion sort algorithm. Also perform best case and worst case analysis of insertion sort algorithm.
[7 marks]How Rabin Karp algorithm performs string matching? Explain with example.
[7 marks]Explain P Problem, NP Problem and NP Complete Problem.
[7 marks]Write Naïve sting matching algorithm. Find its time complexity and perform sting matching for given pattern P = “ACD” Text T = “CACDACAACDAC”1
[7 marks]Explain in brief: Articulation Point, Directed Acyclic Graph, Recurrence Relations
[7 marks]Explain how to solve knapsack problem using greedy algorithms
[7 marks]