i. Worst case running time for Radix Sort is _________. ii. Average case running time for Bubble Sort is ______. iii. To denote two string ab and ac RE will be _________. iv. Prims and Kruskal Algorithms are used for ____________ tree. v. ___________ Algorithm is used to find the shortest path. vi. NPT stands for _______. vii. ET stands for ___________.
[7 marks]Explain Big O, Omega and Theta Notation.
[7 marks]Solve the Traveling salesman problem using dynamic programming for given connection matrix for 4-nodes graph.
[7 marks]What is Top Down design method? Explain with example of gcd.
[7 marks]i. Discuss some of ways to improve the efficiency of algorithm. ii. Explain where D&Cfails.
[2 marks]Explain Multiplication of N-Digit integers using Divide and Conquer. Consider 2345 and 6789 as two numbers for example.
[7 marks]Explain Binary Search? Write an iterative algorithm for binary search and explain the best, average and worst case in Onotation.
[7 marks]Discuss Strassen Matrix Multiplication with example.
[7 marks]What is Merge Sort? Write a recursive algorithm for merge sort and discuss time complexity of merge sort.
[7 marks]Explain Greedy Strategy. Discuss Knapsack problem for n=3, M=20, P = {25,24,15} and W={18,15,10}
[7 marks]Explain Dynamic programming. Explain how it is used for coin exchange problem if we have coin with denomination 1, 4 and 6 units and we want to make change of 8 units.
[7 marks]List and explain four steps in dynamic programming solution.
[7 marks]Discuss union and find data structure with example.
[7 marks]Give simplified definition of ‘O’. Explain Transitivity Rule, Sum Rule, Polynomial Rule, Constant absorption rule and Multiplication Rule of ‘O’ Notation.1
[7 marks]Explain execution time of straight line programs, programs loops and recursive programs.
[7 marks]Discuss Backtracking Strategy. Explain how it can be used to solve the 4-queen problem
[7 marks]Explain DFS and BFS. Write an algorithm for BFS and discuss the total running time of BFS.
[7 marks]