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 X 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 X 16 = 80 Marks)
11. (a) Explain how Time Complexity is calculated. Give an example. (16 Marks)
(Or)
(b) Elaborate on Asymptotic Notations with examples. (16 Marks)
12. (a) With a suitable algorithm, explain the problem of finding the maximum and minimum items in a set of n elements. (16 Marks)
(Or)
(b) Explain Merge Sort Problem using divide and conquer technique. Give an example. (16 Marks)
13. (a) Write down and explain the algorithm to solve all pairs shortest paths problem. (16 Marks)
(Or)
(b) Explain how dynamic programming is applied to solve traveling salesperson problem. (16 Marks)
14. (a) Describe the backtracking solution to solve 8- Queens problem. (16 Marks)
(Or)
(b) With an example, example Graph coloring Algorithm. (16 Marks)
15. (a) Explain in detail the graph traversals. (16 Marks)
(Or)
(b) With an example, explain how the branch - and - bound technique is used to solve O/I knapsack
problem. (16 Marks)
KEYWORDS:2010 ANNA UNIVERSITY CHENNAI B.E COMPUTER SCIENCE AND ENGINEERING B.E./B.TECH DEGREE EXAMINATION, APRIL/MAY 2010 CS2251 - DESIGN AND ANALYSIS OF ALGORITHM,ANNA UNIVERSITY QUESTION PAPER,ANNA UNIVERSITY,ANNA UNIVERSITY CHENNAI,ANNA UNIVERSITY COIMBATORE,ANNA UNIVERSITY TRICHY,ANNA UNIVERSITY TIRUNELVELI,ANNA UNIVERSITY MADURAI,ANNA UNIVERSITY SYLLABUS,ANNA-UNIVERSITY RESULTS,ANNA UNIVERSITY DISTANCE EDUCATION,ANNA UNIVERSITY MBA-CENTRE FOR DISTANCE EDUCATION,ANNA UNIVERSITY SCHEDULE OF EXAMINATIONS,ANNA UNIVERSITY ADMISSION,ANNA UNIVERSITY COURSES,ANNA UNIVERSITY ACADEMIC,ANNA UNIVERSITY DEPARTMENTS,ANNA UNIVERSITY RESEARCH,ANNA UNIVERSITY MAIL,ANNA UNIVERSITY QUESTION PAPERS,ANNA UNIVERSITY COUNSELLING DATES,ANNA UNIVERSITY RE-EVALUATION RESULTS
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 X 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 X 16 = 80 Marks)
11. (a) Explain how Time Complexity is calculated. Give an example. (16 Marks)
(Or)
(b) Elaborate on Asymptotic Notations with examples. (16 Marks)
12. (a) With a suitable algorithm, explain the problem of finding the maximum and minimum items in a set of n elements. (16 Marks)
(Or)
(b) Explain Merge Sort Problem using divide and conquer technique. Give an example. (16 Marks)
13. (a) Write down and explain the algorithm to solve all pairs shortest paths problem. (16 Marks)
(Or)
(b) Explain how dynamic programming is applied to solve traveling salesperson problem. (16 Marks)
14. (a) Describe the backtracking solution to solve 8- Queens problem. (16 Marks)
(Or)
(b) With an example, example Graph coloring Algorithm. (16 Marks)
15. (a) Explain in detail the graph traversals. (16 Marks)
(Or)
(b) With an example, explain how the branch - and - bound technique is used to solve O/I knapsack
problem. (16 Marks)
KEYWORDS:2010 ANNA UNIVERSITY CHENNAI B.E COMPUTER SCIENCE AND ENGINEERING B.E./B.TECH DEGREE EXAMINATION, APRIL/MAY 2010 CS2251 - DESIGN AND ANALYSIS OF ALGORITHM,ANNA UNIVERSITY QUESTION PAPER,ANNA UNIVERSITY,ANNA UNIVERSITY CHENNAI,ANNA UNIVERSITY COIMBATORE,ANNA UNIVERSITY TRICHY,ANNA UNIVERSITY TIRUNELVELI,ANNA UNIVERSITY MADURAI,ANNA UNIVERSITY SYLLABUS,ANNA-UNIVERSITY RESULTS,ANNA UNIVERSITY DISTANCE EDUCATION,ANNA UNIVERSITY MBA-CENTRE FOR DISTANCE EDUCATION,ANNA UNIVERSITY SCHEDULE OF EXAMINATIONS,ANNA UNIVERSITY ADMISSION,ANNA UNIVERSITY COURSES,ANNA UNIVERSITY ACADEMIC,ANNA UNIVERSITY DEPARTMENTS,ANNA UNIVERSITY RESEARCH,ANNA UNIVERSITY MAIL,ANNA UNIVERSITY QUESTION PAPERS,ANNA UNIVERSITY COUNSELLING DATES,ANNA UNIVERSITY RE-EVALUATION RESULTS