Updated Previous Year Question paper for Design Analysis of Algorithm Regulation 2008
B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2010
Fourth Semester
Computer Science and Engineering
CS2251 — DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
Time: Three hours Maximum: 100 Marks
Answer ALL Questions
PART A — (10 × 2 = 20 Marks)
1. Differentiate Time Complexity from Space complexity.
2. What is a Recurrence Equation?
3. What is called Substitution Method?
4. What is an Optimal Solution?
5. Define Multistage Graphs.
6. Define Optimal Binary Search Tree.
7. Differentiate Explicit and Implicit Constraints.
8. What is the difference between a Live Node and a Dead Node?
9. What is a Biconnected Graph?
10. What is a FIFO branch-and-bound algorithm?
PART B — (5 × 16 = 80 Marks)
11. (a) Explain how Time Complexity is calculated. Give an example.
Or
(b) Elaborate on Asymptotic Notations with examples.
12. (a) With a suitable algorithm, explain the problem of finding the maximum
and minimum items in a set of n elements.
Or
(b) Explain Merge Sort Problem using divide and conquer technique. Give an
example.
13. (a) Write down and explain the algorithm to solve all pairs shortest paths
problem.
Or
(b) Explain how dynamic programming is applied to solve travelling
salesperson problem.
14. (a) Describe the backtracking solution to solve 8-Queens problem.
Or
(b) With an example, explain Graph Coloring Algorithm.
15. (a) Explain in detail the Graph Traversals.
Or
(b) With an example, explain how the branch-and-bound technique is used to
solve 0/1 knapsack problem.
Fourth Semester
Computer Science and Engineering
CS2251 — DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
Time: Three hours Maximum: 100 Marks
Answer ALL Questions
PART A — (10 × 2 = 20 Marks)
1. Differentiate Time Complexity from Space complexity.
2. What is a Recurrence Equation?
3. What is called Substitution Method?
4. What is an Optimal Solution?
5. Define Multistage Graphs.
6. Define Optimal Binary Search Tree.
7. Differentiate Explicit and Implicit Constraints.
8. What is the difference between a Live Node and a Dead Node?
9. What is a Biconnected Graph?
10. What is a FIFO branch-and-bound algorithm?
PART B — (5 × 16 = 80 Marks)
11. (a) Explain how Time Complexity is calculated. Give an example.
Or
(b) Elaborate on Asymptotic Notations with examples.
12. (a) With a suitable algorithm, explain the problem of finding the maximum
and minimum items in a set of n elements.
Or
(b) Explain Merge Sort Problem using divide and conquer technique. Give an
example.
13. (a) Write down and explain the algorithm to solve all pairs shortest paths
problem.
Or
(b) Explain how dynamic programming is applied to solve travelling
salesperson problem.
14. (a) Describe the backtracking solution to solve 8-Queens problem.
Or
(b) With an example, explain Graph Coloring Algorithm.
15. (a) Explain in detail the Graph Traversals.
Or
(b) With an example, explain how the branch-and-bound technique is used to
solve 0/1 knapsack problem.
B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2011
Fourth Semester
Computer Science and Engineering
CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions
PART A — (10 × 2 = 20 marks)
1. Using the step count method analyze the time complexity when 2 m × n
matrices are added.
2. An array has exactly n nodes. They are filled from the set {0, 1, 2,...,n-1, n}.
There are no duplicates in the list. Design an O(n) worst case time algorithm to
find which one of the elements from the above set is missing in the array.
3. Show the intermediate steps when the numbers 123, 23, 1, 43, 54, 36, 75, 34
are sorted using merge sort.
4. Devise an algorithm to make a change for 1655 using the Greedy strategy. The
coins available are {1000, 500, 100, 50, 20, 10, 5}.
5. Write the difference between Greedy Method and Dynamic Programming.
6. Write an algorithm to find the shortest path between all pairs of nodes.
7. Define the chromatic number of a graph.
8. Draw a graph with a cycle but with no Hamiltonian cycle.
9. Define a strongly connected digraph and give the minimum in degree of all the
nodes in the graph.
10. Perform depth first and breadth first search on the following graph and find all
the nodes reachable from ‘a’.
PART B — (5 × 16 = 80 marks)
11. (a) Write the recursive and non-recursive versions of the factorial function.
Examine how much time each function requires as ‘n’ becomes large.
Or
(b) (i) Explain asymptotic notations in detail. (8)
(ii) Write an algorithm for linear search and analyze the algorithm for
its time complexity. (8)
12. (a) Write an algorithm to perform binary search on a sorted list of elements.
Analyze the algorithm for the best case, average case and worst case.
Or
(b) Using the divide and conquer approach to find the maximum and
minimum in a set of ‘n’ elements. Also find the recurrence relation for the
number of elements compared and solve the same.
13. (a) Use function OBST to compute w(i, j), r(i, j), and c(i, j), 0<=i<j<=4, for the
identifier set ( ) 4 3 2 1 , , , a a a a = (cout, float, if, while) with p(1) = 1/20, p(2) =
1/5, p(3) = 1/10, p(4) = 1/20, q(0) = 1/5, q(1) = 1/10, q(2) = 1/5, q(3) = 1/20,
and q(4) 1/20. Using the r(i, j)’s, construct the optimal binary search tree.
Or
(b) Using dynamic approach programming, solve the following graph using
the backward approach.
14. (a) Using backtracking, find the optimal solution to a knapsack problem for
the knapsack instance n = 8, m = 110, (p1, p2. ... p7) = (11, 21, 31, 33, 43,
53, 55, 65) and (w1, w2,...,w7) = (1, 11, 21, 33, 43, 53, 55, 65).
Or
(b) Write an algorithm for N QUEENS Problem and Trace it for n=6.
15. (a) Write the Kruskal’s algorithm apply it to find a minimum spanning tree
for the following graph :
Or
(b) Write short notes on NP-hard and NP-completeness.
Fourth Semester
Computer Science and Engineering
CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions
PART A — (10 × 2 = 20 marks)
1. Using the step count method analyze the time complexity when 2 m × n
matrices are added.
2. An array has exactly n nodes. They are filled from the set {0, 1, 2,...,n-1, n}.
There are no duplicates in the list. Design an O(n) worst case time algorithm to
find which one of the elements from the above set is missing in the array.
3. Show the intermediate steps when the numbers 123, 23, 1, 43, 54, 36, 75, 34
are sorted using merge sort.
4. Devise an algorithm to make a change for 1655 using the Greedy strategy. The
coins available are {1000, 500, 100, 50, 20, 10, 5}.
5. Write the difference between Greedy Method and Dynamic Programming.
6. Write an algorithm to find the shortest path between all pairs of nodes.
7. Define the chromatic number of a graph.
8. Draw a graph with a cycle but with no Hamiltonian cycle.
9. Define a strongly connected digraph and give the minimum in degree of all the
nodes in the graph.
10. Perform depth first and breadth first search on the following graph and find all
the nodes reachable from ‘a’.
PART B — (5 × 16 = 80 marks)
11. (a) Write the recursive and non-recursive versions of the factorial function.
Examine how much time each function requires as ‘n’ becomes large.
Or
(b) (i) Explain asymptotic notations in detail. (8)
(ii) Write an algorithm for linear search and analyze the algorithm for
its time complexity. (8)
12. (a) Write an algorithm to perform binary search on a sorted list of elements.
Analyze the algorithm for the best case, average case and worst case.
Or
(b) Using the divide and conquer approach to find the maximum and
minimum in a set of ‘n’ elements. Also find the recurrence relation for the
number of elements compared and solve the same.
13. (a) Use function OBST to compute w(i, j), r(i, j), and c(i, j), 0<=i<j<=4, for the
identifier set ( ) 4 3 2 1 , , , a a a a = (cout, float, if, while) with p(1) = 1/20, p(2) =
1/5, p(3) = 1/10, p(4) = 1/20, q(0) = 1/5, q(1) = 1/10, q(2) = 1/5, q(3) = 1/20,
and q(4) 1/20. Using the r(i, j)’s, construct the optimal binary search tree.
Or
(b) Using dynamic approach programming, solve the following graph using
the backward approach.
14. (a) Using backtracking, find the optimal solution to a knapsack problem for
the knapsack instance n = 8, m = 110, (p1, p2. ... p7) = (11, 21, 31, 33, 43,
53, 55, 65) and (w1, w2,...,w7) = (1, 11, 21, 33, 43, 53, 55, 65).
Or
(b) Write an algorithm for N QUEENS Problem and Trace it for n=6.
15. (a) Write the Kruskal’s algorithm apply it to find a minimum spanning tree
for the following graph :
Or
(b) Write short notes on NP-hard and NP-completeness.
B.E/B.Tech. DEGREE EXAMINATION, MAY/JUNE 2012
Fourth Semester
Computer Science and Engineering
CS 2251/141401/CS 41/CS 1251/10144 CS 402/0802300013 – DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
Time : Three Hours Maximum: 100 marks
Answer ALL questions.
PART A – ( 10 x 2 = 20 marks )- Define Big ‘Oh’ notation.
- What is meant by linear search?
- What is the drawback of greedy algorithm?
- What is the time complexity of binary search?
- State principle of optimality.
- Differentiate greedy method and dynamic programming.
- What is the difference between explicit and implicit constraints?
- Define the basic principles of back tracking.
- What is an articulation point in a graph?
- What is the difference between BFS and DFS methods?
PART B – ( 5 x 16 = 80 marks )
- (a) Discuss in detail all the asymptotic notations with examples.
(b) with a suitable example, explain the method of solving recurrence equations.
2. (a) Explain divide – and – conquer method with merge sort algorithm. Give an example.
OR
(b) Explain how greedy method can be applied to solve the Knapsack problem.
3. (a) With a suitable example, explain all – pair shortest paths problem.
OR
(b) How is dynamic programming applied to solve the traveling salesperson problem? Explain in detail with an example.
4. (a) Explain the algorithm for finding all m-colorings of a graph.
OR
(b) Write down and explain the procedure for tackling the 8 – queens problem using a backtracking approach.
5. (a) Discuss in detail about the biconnected components of a graph.
OR
(b) Compare and contrast FIFO and LC branch – and – bound search techniques.
No comments:
Post a Comment