Design and Analysis of Algorithms - Unit Wise Questions
1. Write down the formal definition of big-oh, big-omega and big-theta notation with examples.
1. Explain worst case, best case and average case of algorithm analysis with an example. [8]
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. 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 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.
1. What do you mean by complexity of an algorithm? Algorithm A has complexity O(2logn) and algorithm B has time complexity O(log2n) . Elaborate, how can you explain this statement.
1. Explain bog-oh, big-omega and big-theta notations for computing analysis of algorithm with example.
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=3n2+4n+7 is big theta of n2.
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;
2. Define recurrence relation. Explain the recursion tree method for solving the recurrence relation with example.
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 is recurrence relation? Find big-O of following recurrence using
recurrence tree method. 
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. What do you mean by recurrence relation? Solve the following recurrence relation using master 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.
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. 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]
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)
5. Solve the following recurrence relations using master method. (2.5+2.5)
a. T(n)=7T(n/2)+n2
b. T(n)=4T(n/4)+kn
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. 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)
8. Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy.(5)
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
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. What is heap sort? Trace the following data using heap sort algorithm.
X[]={10, 8, 12, 70, 20, 5, 30}
3. Write an algorithm for quick-sort and trace out the algorithm for the following array
A[ ] = { 16,7,15,14,18,25,55,32 }.3. Explain the divide and conquer approach for algorithm design. Design the binary search algorithm and analyze it’s time complexity.
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. What is quick sort? Trace the following data using quick sort algorithm.
A[]={99, 50, 60, 8, 5, 6, 20, 25, 40}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.
4. Define order statistics. Write an algorithm that is able to select ith largest element from an un-ordered list in linear time and analyzer for its complexity.
4. How can you solve the selection problem in linear time? Write the algorithm and analyze for its time complexity.
4. How can you solve the selection problem in linear time in worst case? Explain the algorithm.
4. Explain the merge-sort algorithm with example and analyze its time complexity.
4. What is order statistics? How can you devise an algorithm that guarantee the section of ith 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. 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 algorithm for binary search with an example and also discuss its time complexity.
3. Explain the quick sort algorithm with its complexity analysis. How randomized quick sort works efficiently even for worst case.
4. What is Huffman code? Write down Hoffman algorithm and find out its 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.
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. 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. Discuss how knapsack problem can be solved in greedy approach. Explain the algorithm and complexity.
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.
6. Define greedy paradigm. How can you define Huffman algorithm is greedy algorithm? Explain.
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. 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.
7. Explain the algorithm to find the all pair shortest path of a weighted connected graph. Trace the algorithm for the following graph.
7. What
is minimum spanning tree? Write the execution trace of the following graph to
construct minimum spanning tree by prims algorithm. 
7. What is shortest path problem? Explain Dijkstra’s algorithm for shortest path problem.
6. Explain the greedy algorithm for fractional knapsack problem with its time complexity. (5)
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.
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. What is dynamic programming? Find the longest common subsequence between “XYYXXY” and “XXYXXYY”.
5. Write algorithm to compute Longest Common Subsequence of given two sequences. Compute the LCS of “COMPANY” and “COLONY”.
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.
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 do you mean by dynamic programming approach for design of algorithm? Write the algorithm for matrix chain multiplication and estimate its time complexity.
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>.
7. Trace the algorithm for matrix chain multiplication for the given chain ABCD with size array {5, 2, 3, 5, 4}.
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 an algorithm for depth first search. Use depth first search to find a spanning tree of the following graph.
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. What do you mean by Dynamic Programming Strategy? Explain the elements of DP. (2+3)
9. What is directed acyclic graph? How to find the shortest path from a vertex of directed acyclic graph?
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 left turn and right turn? How to detect the intersection of two line segment? Explain with example.
7. What is convex hull? Describe the Graham’s scan algorithm to compute convex hull.
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.
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. Describe the term Class-P, Class-NP and NP-completeness.
8. Define convex hull in 2D. Explain the gram’s scan algorithm for computing convex hull and analyze it.
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.
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. Explain about Class P, Class NP and NP-complete with suitable examples.
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. Define the terms “Class P”, “Class NP” and “NP-completeness”.
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.
9. Define the term left turn and right turn. Explain, how can you detect the intersection of two given line segments efficiently.
8. Explain Graham’s scan algorithm to compute convex hull.
10. What is the application of approximate algorithms? Write the algorithm for approximate the vertex cover of a connected graph with example.
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.
9. Explain the approximation algorithm for solving vertex cover with suitable example. (5)
11. Explain in brief about the classes P, NP, NP complete with example. (5)