[go: up one dir, main page]
Scribd
Upload
146 views2 pages

DAA Questions-A

This document contains questions from 5 units on the topics of algorithms analysis, algorithm design techniques, dynamic programming, backtracking, and complexity theory. Some key topics covered include: - Defining algorithms and analyzing time complexity using asymptotic notations like Big-Oh, Omega, and Theta. - Algorithm design techniques like divide-and-conquer, greedy algorithms, and minimum spanning trees. - Dynamic programming and its applications to problems like knapsack, shortest paths, and optimal binary trees. - Backtracking and its use for solving problems like the n-queens puzzle and graph coloring. - The complexity classes P, NP, NP-complete and NP-hard, and their relationships

Uploaded by

A Raghava Chowdary maddipati
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
146 views2 pages

DAA Questions-A

This document contains questions from 5 units on the topics of algorithms analysis, algorithm design techniques, dynamic programming, backtracking, and complexity theory. Some key topics covered include: - Defining algorithms and analyzing time complexity using asymptotic notations like Big-Oh, Omega, and Theta. - Algorithm design techniques like divide-and-conquer, greedy algorithms, and minimum spanning trees. - Dynamic programming and its applications to problems like knapsack, shortest paths, and optimal binary trees. - Backtracking and its use for solving problems like the n-queens puzzle and graph coloring. - The complexity classes P, NP, NP-complete and NP-hard, and their relationships

Uploaded by

A Raghava Chowdary maddipati
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Unit-1

1. Define an algorithm. Describe the characteristics of an algorithm?


2. Prove that:
a. f(n)+g(n) = O(n2) where f(n) = 3n2-n+4 and g(n) = n log n+5
b. f(n)=4n2-64n+288 = (n2)
3. Write the non-recursive algorithm for finding the Fibonacci sequence and derive its time
complexity?
4. Express the following functions in Big-Oh, Omega and Theta notations:
a. 10n2+5n
b. 10logn+6
5. Describe the performance analysis in detail?
6. Solver the following recurrence relation using substitution method:
a. T(n) = 1, n ≤ 4, 2T(n) + log n, n>4
7. Write short notes on randomized algorithms?
8. What are the various asymptotic notations? Bring out the importance of the same with suitable
examples?
9. What is the time complexity of following function fun()? Explain:
Int function(int n){
for(int i = 1; i<=n;i++){
for(int j = 1; j < n; j+=i) {
sum = sum + i * j;
}
}
Return(sum);
}

Unit-2
1. Write algorithm for abstract Divide and Conquer strategy. Relate the method to real-time
applications
2. Trace the quick sort algorithm to sort the list C, O, L, L, E, G, E in alphabetical order
3. Explain in the control abstraction for greedy method. List out the advantages
4. Prove that, if p1/w1 ≥ p2/w2 ≥ …. ≥ pn/wn then Greedy knapsack generates an optimal solution
to the given instance of the knapsack problem.
5. Give an algorithm for Merge sort. Derive it’s time complexity.
6. Perform merge sort on the array of elements a[1:10] = [310, 285, 179, 652, 351, 423, 861, 254, 450,
520]. Represent tree of calls for merge sort.
7. Write Kruskal’s algorithm to find the maximum spanning tree.
8. Compute a minimum cost spanning tree for the following graph shown in Fig.1, using Kruskal’s
Algorithm:
9. Write the general method of divide-and-conquer approach
10. Explain the problem of finding minimum and maximum and try to apply divide and conquer strategy
to solve it. Give general algorithm for doing the same.
11. Write Prim’s algorithm to find the minimum spanning tree?
12. Compte a minimum cost spanning tree for the following graph in fig.1 using prim’s algorithm
13. Write binary search algorithm and explain?
14. Compare merge sort and quick sort complexities for the given data set: {10, 30, 15, 45, 25, 30, 35,
20, 30, 40, 50}
15. Explain control abstraction for greedy method?
16. Explain the job sequencing with dead line algorithm and also find the solution for the instance n=7,
{P1..P7} = {3,5,20,18,1,6,30} and {D1…D7} = {{1,3,4,3,2,1,2}

Unit-3
1. Define and describe Dynamic Programming. Give its applications
2. How the reliability of a system is determined using dynamic programming? Explain
3. Define and describe Dynamic programming. Give its applications.
4. Describe the problem of single source shortest path and give a solution using dynamic
programming.
5. Write an algorithm for 0/1 Knapsack problem using Dynamic programming.
6. Describe the matrix multiplication chains problem apply the recursive solution of dynamic
programming to determine optimal sequence of pair wise matrix multiplications.
7. Explain the methodology of dynamic programming. List the applications of dynamic programming.
8. How the reliability of a system is determined using dynamic programming? Explain?
9. What is travelling sales person problem? And what are its applications?
10. Find the shortest tour of a TSP for following instance using dynamic programming:
11. Explain 0/1 knapsack problem solution using dynamic programming?
12. Solve the following instance of 0/1 knapsack problem using dynamic programming n=3, {w1, w2,
w3} = {3, 5, 7}; {p1, p2, p3} = 3, 7, 12}; m=4
13. Explain optimal binary search tree problem with an example
14. Design an algorithm to find solution for optimal binary search tree.
15. Write an algorithm of all pairs shortest path problem using dynamic programming
16. Find the shortest path between all pairs of nodes in the following graph in Fig.1:

Unit-4
1. State and explain the subset sum problem with an example
2. Consider the following sum of subsets problem instance: n=6, m=30, and w[1:6] = {5, 10, 12, 13,
15, 18}. Find all possible subsets of w that sum to m. draw the portion of state space tree that is
generate.
3. Define the method of backtracking with suitable example?
4. What is graph colouring? Present an algorithm which finds all m-colouring of a graph?
5. Explain the basic principle of backtracking and list the applications of backtracking.
6. Explain how backtracking is used for solving n-queens problem. Show the state space tree?
7. Give the solution to the 8-queens problem using backtracking. Draw the state space tree.
8. Describe the algorithm for Hamiltonian cycles and determine the order of magnitude of the worst-
case computing time for the backtracking procedure that finds all Hamiltonian cycles.

Unit-5
1. What are differences between NP-Hard and NP-Complete classes? Explain with examples?
2. Explain any two problems of polynomial time algorithms?
3. With a neat diagram, explain the relevance of NP-Hard and NP-Complete problems.
4. Write about the theory of NP-Completeness.
5. Write short notes on Cook’s theorem?
6. Explain nod deterministic algorithms. Give some examples?
7. Explain the satisfiability problem
8. How are P and NP problems related? Give the relation between NP-Hard and NP-Complete
problems?
9. What is string matching? Give its applications?
10. Write about Navie string matching algorithm?

You might also like