Fish

Thursday, 16 May 2013

Design and analysis of algorithms QUESTION PAPERS




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.

REFER THE FOLLOWING LINK FOR MORE QUESTION PAPERS YEAR BY YEAR CLICK HERE

cs1201-Design and analysis of algorithms
fourth semester
APRIL/MAY - 2008

Part - A [each carry 2 marks]
1. Define Big oh notation
2. Enumerate some important types of problem
3. How will you measure input size of algorithms
4. what is the average case complexity of linear search algorithm
5. Write the procedure for selection sort
6. Define depth first searching technique
7. what is the fundamental philosophy of transform and conquer method
8. what is AVL tree
9. State if backtracking always produces optimal solution
10. Explain briefly branch and bound technique for solving problems

Part - B

11.(a) (i) Define the asymptotic notations used for best case average case and worst case analysis of
algorithms
(ii) Write an algorithm for finding maximum element of an array , perform best , worst and average
case complexity with appropriate order notations.
(or)
(b) Write an algorithm to find mean and variance of an array perform best, worst and average case
complexity , defining the notations used for each type of analysis.

12. (a) Derive the recurrence equation for fibonnocci series. Perform Complexity analysis for the same.
(or)
(b) Explain in detail, the techiques for algorithm visualization.

13. (a) Explain in detail quick sorting method. Provide a complete analysis of quick sort.
(or)
(b) Explain in detail merge sort. illustrate the algorithm with a numeric example. Provide complete
analysis of the same.

14 (a)

// see anany levitin book back exercise for graph

Apply Prim's Algorithm and Kruskal algorithm to the graph to obtain minimum spanning tree. Do
these algorithms generate same output - Justify
(or)
(b) Solve the following instance of the single-source shortest paths problem with vertex a as the source.

// see anany levitin book for graph

write the algorithm for the above problem

15. (a) Explain N-queens problem with an algorithm.Explain why backtracking is defined as a default
procedure of last resort for solving problems.
(or)
(b) job 1 job 2 job 3 job 4
a 9 2 7 8
b 6 4 3 7
c 5 8 1 8
d 7 6 9 4
Consider the above matrix for assigment problem involving persons and jobs. Explain in detail how
branch and bound technique is useful is solving assignment problems



REFER THE FOLLOWING LINK FOR MORE QUESTION PAPERS YEAR BY YEAR CLICK HERE


Question Paper Code : 10263
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 )
  1. Define Big ‘Oh’ notation.
  2. What is meant by linear search?
  3. What is the drawback of greedy algorithm?
  4. What is the time complexity of binary search?
  5. State principle of optimality.
  6. Differentiate greedy method and dynamic programming.
  7. What is the difference between explicit and implicit constraints?
  8. Define the basic principles of back tracking.
  9. What is an articulation point in a graph?
  10. What is the difference between BFS and DFS methods?
PART B – ( 5 x 16 = 80 marks  )
  1. (a) Discuss in detail all the asymptotic notations with examples.
OR
(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.

FOR MORE QUESTION PAPERS CLICK HERE


070230017 DESIGN ANALYSIS OF ALGORITHMS
PREVIOUS YEAR QUESTION PAPERS