Subject: Algorithm Analysis and Design

Question Bank
Subject: Algorithm Analysis and Design

Module-I
1. If Explain briefly about the term Pseudo code conventions 2. What is mean by Asymptotic notation Explain 3. What is an algorithm, list the properties of it 4. Explain the recursive algorithm 5. Define Space and Time Complexities 6. Define the Omega notation of a function f(x) 7. For the given function what is (f(x))=(n3/1000)-100n2-100n+3 8. What is computational procedure, write down any two features that distinguish it from an algorithm 9. What is the need for obtaining the Space and Time Complexity measures of an algorithm [Link] the necessity of analyzing an algorithm [Link] a note on non-deterministic algorithm with an example [Link] is mean by complexity of an algorithm, what are the factors affecting the complexity of algorithm [Link] the help of example explain how a recursive algorithm can be represented by recurrence relation [Link] is mean by Asymptotic growth rate of algorithm [Link] profiling and its purpose [Link] the complexity calculation using recursive tree method [Link] substitution method for complexity evaluation [Link] Master method for complexity evaluation [Link] Master method solve T(n)=2T(n/2) + nlogn [Link] are the properties of an algorithm list out the difference between deterministic and non-deterministic algorithm Essay 1. What is the difference between Time and Space [Link] describe the notaytion used for describing the Complexity

2. Disscuss in detail about Deterministic and Non-deterministic Algorithm 3. Explain in detail about Computational Procudure and Program 4. Discuss in detail about Recursive algorithm and Space and Time Complexity 5. Write a short note on the following 1. Space and Time Complexity 2. Asymptotic Notations

6. Design ab algorithm to evaluate 2n in a computer and find the complexity of the algorithm 7. Find the asymptotic upper bound for the function i) ii) T(n)=2T(n)/2 + n2 T(n)3T(n)/2 +n

8. If S1,S2,S3,..Sk be the set of integersin the range 1to n Sum of cardinalities of Si is n .Find (n) algorithm to sort Si. 9. Explain the function of Recurrence Relation and Recurrence Treefor the Complexity evaluation. [Link] an algorithm for Merge Sort. [Link] the Recurrence T(n)=2T[[n/2]+1] + n,T(1)=1 [Link] the Recurrence i.T(n)=3T(n/4) + cn2 ii. T(n)=T(n-1) + T(n-2) + 1 [Link] the Recurrence Relation i.T(n)=2T(n/2) + nlogn ii.T(n)=2T(n/3) + T(2n/3) + cn [Link] T(n)=2T([n/2] + 17) + n is (nlogn) [Link] the Pseudo code convention of algorithm [Link] that the solution to T(n)=2T([n/2] + 17) is (n/log n) [Link] recurrence T(n)=7T(n/2) + n2 describe the running time of an algorithm A.A competing algorithm Ahas a running time of T(n)=aT(n/4) + n2 .What is the largest integer value for a such that A is asymptotically faster than A [Link] in detail about recursive algorithms, space and time complexity and Asymptotic Notations

Module II
1. With simple example explain how to find the Maximum and Minimum 2. Define the term Merge Sort

3. How many Key comparison are done by Merge Sort, if the Key are already in order when the sort begins. Justify your answer 4. Find the Time complexity of Binary Search algorithm 5. What you mean by Control Abstraction? Briefly explain it 6. Explain the Divide and Conquer strategy with a suitable example? 7. How to evaluate the complexity of Matrix Multiplication 8. Define the stability of Sorting Method 9. Analyze the time Complexity of merge Sort algorithm [Link] Divide and Conquer and Dynamic Programming Strategy [Link] the Control Abstration for Greedy Strategy [Link] the difference between merge and quick sort [Link] divide-conquer strategy with example Essay 1. Write short note o n the following i. ii. Divide and Conquer Matrix Multiplication Quick Sort

2. Write short note o n the following i. ii. Binary Search Stressens Matrix Multiplication

3. Write short note on Merge Sort and Quick Sort 4. Explain Stressens Matrix Multiplication method and find the Time Complixity of the algorithm 5. Analyze worst and average case complexity and Quick Sort 6. Show the various step involved in the quick sort of (1,3,4,-5,9,2,6,5,3) 7. Design an algorithm to evaluate the upper and lower bounds in a heap sort. Explain with typical example 8. Explain the algorithm to find the maximum and minimum and analyze its Time complexity 9. Show that the Binary Search requires at most K element comparison for a successful search and k-1 or k comparison for an unsuccessful search [Link] Stressens Matrix Multiplication and discuss its time complexity

Module III
1. Define the term Optimal Storages on Tapes

2. Write about the technical term Job sequencing with deadlines 3. Describe the control abstraction for greedy strategy 4. Briefly explain about minimum cost spanning tree 5. Write Kruskals algorithm for finding minimum cost spanning tree 6. What is the relevance of Greedy method to solve Knapsack problem 7. Explain the complexity of Optimal storages on tapes 8. Explain various types of Knapsack problem 9. What is the general knapsack problem [Link] down an algorithm that can be solved only using the back tracking approach, Justify [Link] the worst case of Prims algorithm [Link] how Greedy strategy can be used in optimal storage problem on Tapes [Link] machine scheduling using greedy method [Link] is the application of minimum cost spanning tree [Link] about prims algorithm

Essay 1. Discuss in detail about Knapsack Problem with an example 2. Describe Prims algorithm. Find the time complexity for the algorithm 3. Explain Knapsack problem, Also device a greedy method to solve the problem 4. Describe Kruskals algorithm, find the time complexity and its application 5. Solve the Knapsack problem for n=3,m=20,(p1,p2,p3)=(25,24,15) and (w1,w2,w3)=(18,15,10) suggest feasible solution 6. What is Job Sequencing problem. Analyze the problem and determine its complexity 7. Let J be a set of K jobs and =i1,i2,ik be the permutation of jobs in J such that di1di2d13..dik. then show that J is a feasible solution if the jobs in J can be processed in the order without violating any deadline 8. Show that if l1l2..ln then the ordering ij=j 1jn minimizes lij over all permutation of the ij 9. Find the all pair shortest path for the given graph 6 1 4 2

11 3

[Link] the multi stage graph problem for finding the minimum path

4 2

9 7 3 1 2

1 3 6 9 1 0 0 0 0 0 1 0 1 4 2 5

7 11 11 7

4 3 5

[Link] the minimum cost spanning tree using Prims algorithm

1 55 25

45

15 2 5 5 35 10 6 3 40 15 7 20

30 8

50

Module -IV
1. What is meant by multi-stage Graph 2. Describe the principle of Optimality 3. Explain briefly about the function of adversary argument 4. Explain the complexity of Kth element selection 5. What is dynamic programming strategy 6. What are comparison trees, what sort of problem are they used to find the solution and how 7. Explain the lower bound for searching problem 8. Explain the elementary concept of dynamic programming Essay 1. Explain the all pair shortest path problem, Solve it using dynamic programming strategy 2. Write short note on i)Principle of Optimality ii)Comparison trees for Searching and sorting iii)Various methods in Tree-Sort 3. Explain Travelling salesman Problem. Suggest a solution for problem using dynamic programming 4. Explain the comparison tree for searching and sorting with suitable example 5. With suitable example explain about Merging, Insertion and Selection Sort in Oracle and Adversary Argument 6. What are the various method available in tree sort 7. What are multi-stage graph, write down a problem on this data structure. devise an algorithm to solve it with its time complexity 8. Explain General Knapsack problem with an example 9. Explain the algorithm for obtaining optimal binary search tree, Using dynamic programming technique [Link] the following Travelling Salesperson problem

0 5 6 8

10 0 13 8

15 20 9 0 9 10 12 0

Module V
1. What is meant by Oracle and Adversary argument 2. What you mean by bounding function ,Explain 3. Define the term FIFO and LIFO 4. Briefly explain the concept of backtracking 5. Define Bounding function 6. Write short note on N-Queen problem 7. Does an N-queen problem with 3X3 board have a solution. How many solutions are there for a 8-queen problem 8. Explain the control abstraction for Backtracking technique 9. Write a short note on 15-puzzle problem [Link] the control abstraction for branch and bound technique [Link] the lower bound for selection problem [Link] Explicit and Implicit constraints [Link] Static and Dynamic Tree [Link] live node and Dead node [Link] state space and problem state [Link] the 0/1 Knapsack problem [Link] the permutation tree for 4-queen problem [Link] the purpose of lower bound theory [Link] how tournament graph can be used for finding Largest and Second largest element

Essay 1. Describe the term N-queen problem and sum of subset 2. Describe how 15-puzzle problem is solved 3. Discuss the sum of subset problem and find a solution for it using backtracking method 4. Discuss in detail about control abstraction and bounding function in backtracking 5. Explain in detail about Branch and Bound Technique in Backtracking 6. Explain an algorithm to solve N-queen problem

7. Derive an algorithm for finding the Kth smallest element from a list of n elements and derive the complexity 8. Explain in detail the FIFO and LIFO search method of the state space tree 9. Solve Knapsack problem using Backtracking method [Link] Travelling salesman Problem using branch and Bound Technique [Link] the technique of placing elements in a N-queen problem with satisfying the constraints 12. With the tree explain the placing of 4-queens on a 4X4 board using Backtracking