Analysis and Design of Algorithms (3150703) Chapterwise IMP Questions || GTU || Computer Engineering

Chapter - 1 : BASICS OF ALGORITHMS AND MATHEMATICS

1. What is an algorithm? Explain various properties of algorithm
2. What is an algorithm? Why analysis of algorithm is required?
3. Explain the term quantifiers, function and Relation.
4. Difference between Algorithm and Flowchart.
5. What is relation? Explain equivalence relation

Chapter - 2 : ANALYSIS OF ALGORITHM

1. Why do we use asymptotic notations in the study of algorithms? Briefly describe the commonly used asymptotic notations. OR Explain all asymptotic notations used in algorithm analysis.
2. Why Analysis of Algorithm is important? Explain worst case, best case, and average case Complexity
3. What is an amortized analysis? Explain aggregate method of amortized analysis using suitable example.
4. Explain following sorting algorithm with best , average and worst case analysis (any one sorting algorithm may be ask) Bubble Sort, Selection Sort, Insertion Sort, Quick sort, Merge Sort, Heap Sort, Shell Sort, Radix Sort. OR any example may be given to solve using above algorithm. Such, as Sort the letters of word “EDUCATION” in alphabetical order using insertion sort Sort the given elements with Heap Sort Method: 20, 50, 30, 75, 90, 60, 25, 10, 40. Give the properties of Heap Tree. Sort the following data using Heap Sort Method: 20, 50, 30, 75, 90, 60, 80, 25, 10, 40. Sort the letters of word “EXAMPLE” in alphabetical order using insertion sort.
5. Which are the basic steps of counting sort? Write a counting sort algorithm. Derive its time complexity in worst case.
6. Explain Master and Substitution Method to solve recurrence. OR Solve any recurrence using Master Method or Substitution Method (Any recurrence will be given) OR Write the Master theorem. Solve following recurrence using it (i) T(n)=9T(n/3) + n (ii) T(n)=3T(n/4) + nlgn
7. Prove or Disprove that f(n) = 1 + 2 + 3 + . . . . +n = Ѳ(n^2)
8. What is the difference between selection sort and bubble sort?
9. Write iterative and recursive algorithm for finding the factorial of N. Derive the time complexity of both the algorithms

Chapter - 3 : DIVIDE AND CONQUER ALGORITHM

1. How divide and conquer approach work?
2. Explain the use of Divide and Conquer Technique for Binary Search Method. What is the complexity of Binary Search Method? Explain it with example. OR Explain Binary search algorithm with divide and conquer strategy and use the recurrence tree to show that the solution to the binary search recurrence T(n) = T(n/2) + Ѳ(1) is T(n) = Ѳ(lgn)
3. Write a program/algorithm of Quick Sort Method and analyze it with example. Also explain best case, worst case and average case time complexity of it.
4. Explain how multiplication of large integers can be done efficiently by using divide and conquer technique?
5. Discuss matrix multiplication problem using divide and conquer technique. OR Explain Strasson’s algorithm for matrix multiplication with suitable example.
6. What is recurrence? Solve recurrence equation T (n) =T (n-1) + n using forward substitution and backward substitution method.
7. Write an algorithm for quick sort and derive best case, worst case using divide and conquer technique also trace given data (3,1,4,5,9,2,6,5) OR Write the quick sort algorithm. Trace the same on data set - 4, 3, 1, 9, 8, 2, 4, 7.
8. Write a program/algorithm of Merge Sort Method. What is Complexity of it?

Chapter - 4 : DYNAMIC PROGRAMMING

1. Define principle of optimality
2. Discuss Assembly Line Scheduling problem using dynamic programming with example.
3. Give difference of dynamic programming and divide-and-conquer method
4. Write equation for Chained matrix multiplication using Dynamic programming. Find out optimal sequence for multiplication: A1 [5 × 4], A2 [4 × 6], A3 [6 × 2], and A4 [2 × 7]. Also give the optimal parenthesization of matrices. OR Explain Chained Matrix Multiplication with example. Note : This kind of any example may be in examination such as : For the following chain of matrices find the order of parenthesization for the optimal chain multiplication (15,5,10,20,25)
5. Explain how to find out Longest Common Subsequence of two strings using Dynamic Programming method. Find any one Longest Common Subsequence of given two strings using Dynamic Programming. X=abbacdcba Y=bcdbbcaac
6. Solve Making Change problem using Dynamic Programming. (Denominations: d1=1, d2=4, d3=6). Give your answer for making change of Rs. 9.
7. Given two sequence of characters, X={G,U,J,A,R,A,T}, Y = {J,R,A,T} obtain the longest common subsequence.
8. Solve all pair shortest path problem for the following graph using Floyd’s algorithm
9. Find out the NCR (5 , 3) Using Dynamic Method.

Chapter - 5 : GREEDY ALGORITHM

1. Explain in brief characteristics of greedy algorithms. Compare Greedy Method with Dynamic Programming Method
2. Using greedy algorithm find an optimal schedule for following jobs with n=6. Profits: (P1,P2,P3,P4,P5,P6) = (20, 15, 10, 7, 5, 3) Deadline: (d1,d2,d3,d4,d5,d6) =(3, 1, 1, 3, 1, 3)
3. Write the Prim’s Algorithm to find out Minimum Spanning Tree.
4. Write Huffman code algorithm and Generate Huffman code for following
5. Explain the characteristics of Greedy algorithms. Compare Greedy algorithms with Dynamic Programming
6. Consider Kanpsack capacity W=50, w=(10,20,40) and v=(60,80,100) find the maximum profit using greedy approach

Chapter - 6 : EXPLORING GRAPHS

1. Explain Depth First Search Traversal Method for Graph with algorithm with example.
2. Explain Breath First Search Traversal Method for Graph with algorithm with example
3. Explain: Acyclic Directed Graph, Articulation Point, Dense Graph, sparse graph, Breadth First Search Traversal, Depth First Search Traversal.
4. Differentiate BFS and DFS.
5. What is topological sort? Explain with example
6. Find out articulation points for the following graph. Consider vertex A as the starting point.

Chapter - 7 : BACKTRACKING AND BRANCH AND BOUND

1. Explain Backtracking Method. What is N-Queens Problem? Give solution of 4- Queens Problem using Backtracking Method.
2. Find an optimal solution to the knapsack instance n=4, M=8, (P1,P2,P3,P4)=(3,5,6,10) and (W1,W2,W3,W4)=(2,3,4,5) using backtracking. Also draw the corresponding state space tree.
3. Define backtracking. State types of constraints used in backtracking.

Chapter - 8 : STRING MATCHING

1. What is Finite Automata? Explain use of finite automata for string matching with suitable example.
2. Explain naïve string matching algorithm with example.
3. What is Rabin Karp algorithm? Where it is used? Explain the concept behind this algorithm and calculate its time complexity. OR Any example of Rabin Karp will be in examination such as : Working modulo q=11. How many spurious hits does the Rabin Karp matcher encounter in the text T= 3141592653589793 when looking for the pattern P = 26 .

Chapter - 9 : INTRODUCTION TO NP – COMPLETENESS

1. Explain P, NP , NP Compete.
2. Explain Polynomial time reduction algorithm
3. Which are the three major concepts used to show that problem is an NP Complete problem?
4. State whether travelling salesman problem is a NP-Complete problem? Justify your answer.

We are following some educational institutes for imp we are not responsible for exam questions