Design and Analysis of Algorithms - Unit Wise Questions

1.  What do you mean by complexity of an algorithm? Algorithm A has complexity O(2^logn) and algorithm B has time complexity O(log₂n) . Elaborate, how can you explain this statement.  

1.  Why do you need the algorithm analysis? Explain the best, worst and average case complexities with suitable example.                                                                            

1.  Explain the term Big-oh, Big-omega and Big-theta. Show that a function f=3n²+4n+7  is big theta of n².             

1.  Use RAM model to estimate the big-oh of the running time for following code segment.

for(i=0;i<n;i++){

                             small pos = i;

                                    smallest = Array[small pos];

                                    for(j=i+1; j<=n; j++){

                                    if(Array[j]<smallest){

                                                small pos = j;

                                                smallest=Array[small pos];

                                    }

            }

            Array[small pos]=Array[i];

            Array[i] = smallest;

1.  Write down the formal definition of big-oh, big-omega and big-theta notation with examples.

1.  Explain bog-oh, big-omega and big-theta notations for computing analysis of algorithm with example.

1.  What do you mean by complexity of an algorithm? Explain about the asymptotic notations used to describe the time/space complexity of any algorithm with their geometrical interpretation and example.    (1+9)

1. What are the elementary properties of algorithm ? Explain. Why do you need analysis of algorithm? Discuss about the RAM model for analysis of algorithm with suitable example. (2+2+6)

1.  Explain worst case, best case and average case of algorithm analysis with an example. [8]

1.  What do you mean by time and space complexity? Explain Big Oh, Big Omega and Big Theta.

1.  What do you mean by complexity of an algorithm? Explain RAM model for the analysis of algorithm with example.                                                                                           

2.  What do you mean by recurrence relation? Solve the following recurrence relation using master method.  

2.  What is recurrence relation? Find big-O of following recurrence using recurrence tree method.                                                                                                                                 

2. Explain about the divide and  conquer paradigm for a algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity. (4+6)

2.  What is recurrence relation? Find big-O of following recurrence using recurrence tree method.      [2+6]

2.  What do you mean by recurrence relation? Estimate the running time of algorithm given by following recurrence relations using master method.

2.  What do you mean by a recurrence relation? Solve the following recurrence relation using iterative expansion method                                                                                              

2.  Explain the big Oh of the following recurrence relations using the iterative expansion method.                                                                                                                                                                                                                                                       

2.  Explain the master method for solving the recurrence relations. Solve the following recurrence relations using this method.                                                                                     

2.  Define the Master theorem for solving the recurrence relation and solve the following recurrence relation using this method.

2.  What is recurrence tree method? Determine a good asymptotic upper bound of following relation using recurrence tree method. 

2.  Define recurrence relation. Explain the recursion tree method for solving the recurrence relation with example.

3.  Make a tight big-O analysis of following code.

void main()

{

   int m, n, i, j, a[], b[], c[];

   printf(“Enter value of m and n”);

   scanf(“%d%d”,&m,&n);

   for(i=1;i<=m;i++)

      a[i]=i*i;

   for(j=1;j<=n;j++)

      b[j]=-j;

   for(i=1;i<=m;i++)

      printf(“%d”, a[i]);

   for(j=1;j<=n;j++)

      printf(“%d”, b[j]);

3. Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 knapsack problem using the dynamic programming approach and explain its complexity. (2+2+6)

3.  Make a tight big-O analysis of following code.

void main()

{

   int m, n, i, j, a[], b[], c[];

   printf(“Enter value of m and n”);

   scanf(“%d%d”,&m,&n);

   for(i=0;i<n;i++)

   {

      a[i]=i;

      b[i]=i*i;

      c[i]=-i;

   }

   for(j=0;j<m;j++)

   {

      printf(“%d\\t%d\\t%d\\n”,a(j), b(j), c(j);

   }

}                                                                                                                                   [8]

4. Explain the recursion tree method for solving the recurrence relation. Solve following recurrence relation using using this method. T(n) = 2T(n/2)+1 for n>1, T(n) = 1 for n = 1 (2+3)

5.  Solve the following recurrence relations using master method.    (2.5+2.5)

        a. T(n)=7T(n/2)+n²

        b. T(n)=4T(n/4)+kn

5. Write an algorithm to find the maximum element of an array and analyze its time complexity.(5)

6. Write the algorithm for bubble sort and explain its time complexity.(5)

7. What do you mean by optimization problem? Explain the greedy strategy for algorithm design to solve optimization problems.(1+4)

10.  Explain worst case, best case and average case of algorithm analysis with an example. 

10.  What is BST? Write the algorithm of insertion and deletion operation of BST

8. Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy.(5)

9. What do you mean by memoization strategy? Compare memoization with dynamic programming.(2+3)

10. Explain the concept of backtracking. How it differ with recursion?(2+3)

11. Explain in brief about the complexity classes P,NP and NP Complete.(5)

12. Write short notes on:(2*2.5)

a. NP Hard Problems and NP Completeness

b. Problem Reduction

1.  Describe the best case and worst case complexity of an algorithm. Write algorithm for insertion sort and estimate the best and worst case complexity.  

4.  Write the algorithm for Selection Sort and explain its time and space complexity.    (5)

2.  Explain about divide and conquer paradigm for algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity.    (4+6)

3.  Write the algorithm for Merge sort and find its time complexity. Compare merge sort with quick sort in terms of time and space complexity.

3.  Write an algorithm for quick-sort and trace out the algorithm for the following array

3.  What is the worst-case of quick sort? Show the how quick sort can be made to run in optimal time in the worst case.                                                                              

3.  Explain the divide and conquer approach for algorithm design. Design the binary search algorithm and analyze it’s time complexity.                                                               

3.  What is quick sort? Trace the following data using quick sort algorithm.

3.  What is heap sort? Trace the following data using heap sort algorithm.                      

X[]={10, 8, 12, 70, 20, 5, 30}

4.  Define order statistics. Write an algorithm that is able to select i^th largest element from an un-ordered list in linear time and analyzer for its complexity.

4.  What is order statistics? How can you devise an algorithm that guarantee the section of i^th order statistics in linear time? Write the algorithm of it and analyze it.                   [1+3+4]

4.  What is linear data structure? Write down the algorithm of heap sort and find its complexity analysis.

4.  How can you solve the selection problem in linear time in worst case? Explain the algorithm.

4.  How can you solve the selection problem in linear time? Write the algorithm and analyze for its time complexity.                                                                                                      

4.  Explain the merge-sort algorithm with example and analyze its time complexity. 

4.  Trace the heap-sort algorithm for the following data: {16, 41, 18, 99, 74, 20, 17, 25, 10}.   

5.  What is divide and conquer technique? Using this technique. Write an algorithm of quick sort then analyze it.                                                                                                        

5.  What is the main idea of randomized algorithm? Write an algorithm quick sort and analyze it.                                                                                                                       [2+6]

7.  Trace the heap-sort algorithm for the following data: {12, 45, 62, 50, 85, 15, 28}.    (5)

3.  Explain the quick sort algorithm with its complexity analysis. How randomized quick sort works efficiently even for worst case.

3.  Explain the algorithm for binary search with an example and also discuss its time complexity.

4.  What is Greedy paradigm? Write down the Greedy job sequencing algorithm.

4.  Compare the algorithms for quick sort, merge sort and heap sort in terms the time and space complexity.

4.  What is Huffman code? Write down Hoffman algorithm and find out its complexity.[

5.  Sketch the Prim’s algorithm for computing MST of a graph and analyze its complexity. Also trace the algorithm for the following graph.

5.  Discuss the fractional knapsack problem and how this problem can be solved? Explain the algorithm.

5.  What is prefix code? You have given a message text having seven distinct characters  {p, q, r, s, t, u, v} with frequency {40, 20, 15, 12, 8, 3, 2}. Trace the Huffman algorithm to build the tree and obtain the optimum prefix codes for each characters.                 

5.  What do you mean by a prefix code? How Huffman algorithm generates prefix codes? Explain with an example.

5.  What is prefix code? How Huffman algorithm generates optimal prefix codes? Explain with suitable example. 

5.  Discuss how knapsack problem can be solved in greedy approach. Explain the algorithm and complexity.

6.  Describe prim's algorithm for finding the minimum spanning tree of a graph. Also trace the algorithm for a weighted connected graph.

6.  Explain Prim’s algorithm for computing the MST of a given graph and analyze it. Also verify the correctness of this algorithm.                                                                        

6.  Explain the Kruskal’s algorithm for computing spanning tree of weighted connected graph with an example of seven nodes graph.

6.  Give the job sequencing algorithm with deadlines. You have given 5 jobs with profit pi and deadline di as

job i = { 1, 2, 3, 4, 5}

pi = {20, 10, 5, 15, 1}

di = { 2, 1, 3, 2, 3}

6.  Define greedy paradigm. How can you define Huffman algorithm is greedy algorithm? Explain.

7.  What is shortest path problem? Explain Dijkstra’s algorithm for shortest path problem. 

7.  What is minimum spanning tree? Write the execution trace of the following graph to construct minimum spanning tree by prims algorithm.                                                                   

7.  Explain the algorithm to find the all pair shortest path of a weighted connected graph. Trace the algorithm for the following graph. 

7.  Write the Dijkstra’s algorithm for single source shortest path in a weighted connected graph. Find the shortest path from the node S to other nodes in the following graph.

7.  Describe the prism’s algorithm for finding the maximum spanning tree of a graph. Also trace the algorithm for a weighted connected graph with at least 7 vertices.

6.  Explain the greedy algorithm for fractional knapsack problem with its time complexity.    (5)

9.  What is short path problem? Explain Dijkstra’s algorithm to compute shortest path.  

10.  Explain Dijkstra’s algorithm for computing the single source shortest path in a graph with suitable example.                                                                                                               

10.  Explain the Prim's algorithm for MST problem and analyze its time complexity.    (5)

5.  Write algorithm to compute Longest Common Subsequence of given two sequences. Compute the LCS of “COMPANY” and “COLONY”. 

5.  What is dynamic programming? Find the longest common subsequence between “XYYXXY” and “XXYXXYY”.                                                                                  

6.  What do you mean by dynamic programming approach for design of algorithm? Write the algorithm for matrix chain multiplication and estimate its time complexity.  

6.  Discuss the 0/1 knapsack problem and how this problem can be solved? Explain the algorithm.          

6.  What do you mean by dynamic programming approach for algorithm design? Explain the algorithm to solve the longest common subsequences and analyze its complexity.  

6.  What are the advantages of dynamic programming? Find Longest Common Subsequence (LCS) between “abbaab” and “aabaabb”.                                                                     

6.  What is Floyd’s algorithm? Write the details of Floyd’s algorithm to find shortest path in a graph.                                                                                                                          

7.  Trace the algorithm for matrix chain multiplication for the given chain ABCD with size array {5, 2, 3, 5, 4}.

7.  Explain and analyze the Floyd’s warshall algorithm for all pair shortest path problem. Trace the algorithm for the following graph.

7.  Distinguish the main idea for divide and conquer approach with dynamic programming approach. Find the longest common subsequence between two sequences <A,B,C,B,D,A,B> and <B,D,C,A,B,A>.

8.  Write an algorithm to compute the LCS of given two sequences. Trace the running of the algorithm to find the LCS of the sequences “XMJYAUZ” and “MZJAWXU”.  

8.  Write algorithm for single source shortest path in a DAG. Trace the algorithm for finding the shortest path from a source vertex in the following graph.

8.  Write an algorithm for depth first search. Use depth first search to find a spanning tree of the following graph.

9.  What is directed acyclic graph? How to find the shortest path from a vertex of directed acyclic graph?

8.  What do you mean by Dynamic Programming Strategy? Explain the elements of DP.    (2+3)

10.  What is the concept of dynamic programming? Find the longest common subsequence (LCS) between “XMJYAUZ” and “MZJAWXU”. [2+6]

3.  Explain in brief about the Backtracking approach for algorithm design. How it differs with recursion? Explain the N-Queen Problem and its algorithm using backtracking and analyze its time complexity.    (2+2+6)

12.  Write short notes on:        (2x2.5)

        a. Backtracking Strategy

        b. Tractable and Intractable problems

7.  What is convex hull? Describe the Graham’s scan algorithm to compute convex hull.

7.  What is left turn and right turn? How to detect the intersection of two line segment? Explain with example.                                                                                                   

8.  What types of problems are called class-P, class-NP and NP-completeness? Explain with examples.                                                                                                                       

8.  Define the convex hull in 2D. Write the Graham's scan algorithm and discuss its correctness and analyze its time complexity.

8.  Define convex hull in 2D. Explain the gram’s scan algorithm for computing convex hull and analyze it.                                                                                                                

8.  Describe the term Class-P, Class-NP and NP-completeness.   

8.  What is left turn and right turn? Give an algorithm for finding two lines segments intersect or not by using left turn and right turn. Does this algorithm works for all cases? Justify with example.

8.  What do you mean by left turn and right turn for given three points in 2D? Explain the method for computing the intersection of two line segment efficiently.

9.  Define the terms “Class P”, “Class NP” and “NP-completeness”. 

9.   Define the term diagonal, ear and mouth of a simple polygon. How can you determine the intersection of two line segment efficiently? Explain in detail.

9.  Define the term left turn and right turn. Explain, how can you detect the intersection of two given line segments efficiently.

9.  Define the terms “Class P”, “Class NP” and “NP-completeness”.                                  

9.  Define the convex hull in 2D. Write the Grahm’s scan algorithm and its correctness for computing the convex hull of points in 2D and analyze its time complexity.    

9.  Explain about Class P, Class NP and NP-complete with suitable examples.

8.  Explain Graham’s scan algorithm to compute convex hull.

9.  Explain about the complexity classes P, NP and NP complete with suitable examples. 

9.   Define the convex hull in 2D. Write the Grahm’s scan algorithm for computing the convex hull of points in 2D and analyze its time complexity. 

10.  What is the application of approximate algorithms? Write the algorithm for approximate the vertex cover of a connected graph with example.

9.  Explain the approximation algorithm for solving vertex cover with suitable example.    (5)

10.  What is the concept of randomized algorithm? Write an algorithm of approx..-vertex-cover problem and analyze it.

10.  What do you mean by approximation algorithm? Write the algorithm for approximate the vertex cover of a connected graph with example.

10. Explain the Gram’s scan algorithm with example to compute the convex hull of the set of points in 2D.       

10.  Discuss NP completeness. What is the role of approximation algorithms? Explain the algorithm for vertex cover of a graph with running example.                                                                    

10.  Why approximation algorithms are used? Write the algorithm for approximate the vertex cover of a connected graph with example.                                                                    

11.  Explain in brief about the classes P, NP, NP complete with example.    (5)