Anna University
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.
B.E. / B.Tech. DEGREE EXAMINATION. NOV/DEC 2011.
Fouth Semester
Computer Science and Engineering
CS2251 – DESING ANALYSIS OF ALGORITHMS
PART –A (2X10=20)
1.
What
do you mean by linear search?
2.
What
is the properties of big-oh notation?
3.
What
greedy algorithms?
4.
What
knapsack problem?
5.
What
is traveling salesperson problem?
6.
What
do you mean by multistage graphs?
7.
State
the general backtracking method?
8.
What
is graph cloning?
9.
What
is spanning tree? Give an example.
10. What is NP-completenes?
PART – B (5X16=80)
11. (a) (i)
define asymptotic notations. Distingush between asymptotic notation and
conditional asymptotic notation.
(ii) Explain
how the removing condition is done from the conditional symptotic notation with
an example.
OR
(b) (i)
Explain how analysis of linear search is done with a suitable illustration.
(ii) Define
recurrence equation and explain how solving recurrence equations are done.
12. (a) What
is divde and conquer strategy and explain the binary search with suitable
example problem.
OR
(b)
Distingush between quick sort and Merge sort, and arrange the following numbers
in increasing order using sort (18, 29,
68,32,43,37,87,24,47,50)
13.(a) (i)
Explain the multistage graph problem with an example
(ii)Find the
optimal solution to the knapsack instance n=7, m=15(p1,p2,p3,…p7)=(10,5,15,7,6,`18,3)
and (w1,w2,w3….w7)(2,3,5,7,1,4,1)
OR
(b) Describe
binary search tree with three traversal patterns? Give suitable example with
neat diagram for all three traversal of binary search.
14. (a) (i)
How backtracking work on the 8 Queens problem with suitable example?
(ii) Explain
elaborately recursive backtracking algorithm?
OR
(b) What is
Hamilton problem>?Expalin with an example using backtracing.
15. (a) Write
a complete LC branch-and-bound algorithm for the job sequencing with deadlines
problem. Use the fixed size formulation
OR
(b) Write a
non-deterministic algorithm to find whether a given graph contains a
Hamiltonian cycle.
***************************************
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.
DESIGN AND ANALYSIS OF ALGORITHMS
(COMMON TO COMPUTER SCIENCE AND ENGINEERING, INFORMATION TECHNOLOGY)
Time: 3 hours Max. Marks: 80
Answer any five questions
All questions carry equal marks
---
1.a) Give the control abstraction
for divide and Conquer strategy.
b) Determine the running time of
Quick sort algorithm in the average case. [16]
2.a) Explain how a max heap can be
used to implement a Priority queue.
b) Write Union and Find algorithms
that use weighting rule and collapsing rule respectively for disjoint sets
. [16]
3.a) Write Kruskal’s algorithm to
generate minimum cost spanning tree for a graph.
b) Explain the above algorithm with
an example. [16]
4.a) Give the essential difference
between the greedy method and dynamic programming.
b) Write an algorithm to solve
0/1-Knapsack problem. Note: Use dynamic programming approach. [16]
5.a) Write a non recursive procedure
for the inorder traversal of a given binary tree.
b) Define AVL tree. [16]
6.a) Write and explain a
backtracking algorithm which finds all m-colorings of a graph.
b) Determine an upper bound on the
computing time of the above backtracking algorithm which finds all m-colorings
of a graph. [16]
7.a) Discuss the general method of
Branch and Bound.
b) Write and explain the algorithm
for the Depth first traversal of a given Graph.
[16]
8.a) Give the Control abstraction
for LC-search strategy.
b) Explain with an example how
modular arithmetic can be used as a transformation technique. [16]
********
DESIGN AND ANALYSIS OF ALGORITHMS
(COMMON TO COMPUTER SCIENCE
AND ENGINEERING, INFORMATION TECHNOLOGY)
Time: 3 hours Max. Marks: 80
Answer any five questions
All questions carry equal marks
---
1.a) Write Kruskal’s algorithm to
generate minimum cost spanning tree for a graph.
b) Explain the above algorithm with
an example. [16]
2.a) Give the essential difference
between the greedy method and dynamic programming.
b) Write an algorithm to solve
0/1-Knapsack problem. Note: Use dynamic programming approach. [16]
3.a) Write a non recursive procedure
for the inorder traversal of a given binary tree.
b) Define AVL tree. [16]
4.a) Write and explain a
backtracking algorithm which finds all m-colorings of a graph.
b) Determine an upper bound on the
computing time of the above backtracking algorithm which finds all m-colorings
of a graph. [16]
5.a) Discuss the general method of
Branch and Bound.
b) Write and explain the algorithm
for the Depth first traversal of a given Graph. [16]
6.a) Give the Control abstraction
for LC-search strategy.
b) Explain with an example how
modular arithmetic can be used as a transformation technique. [16]
7.a) Give the control abstraction
for divide and Conquer strategy.
b) Determine the running time of
Quick sort algorithm in the average case. [16]
8.a) Explain how a max heap can be
used to implement a Priority queue.
b) Write Union and Find algorithms
that use weighting rule and collapsing rule respectively for disjoint sets.
[16]
********
DESIGN AND ANALYSIS OF ALGORITHMS
(COMMON TO COMPUTER SCIENCE AND ENGINEERING, INFORMATION TECHNOLOGY)
Time: 3 hours Max. Marks: 80
Answer any five questions
All questions carry equal marks
---
1.a) Write a non recursive procedure
for the inorder traversal of a given binary tree.
b) Define AVL tree. [16]
2.a) Write and explain a
backtracking algorithm which finds all m-colorings of a graph.
b) Determine an upper bound on the
computing time of the above backtracking algorithm which finds all m-colorings
of a graph. [16]
3.a) Discuss the general method of
Branch and Bound.
b) Write and explain the algorithm
for the Depth first traversal of a given Graph.
[16]
4.a) Give the Control abstraction
for LC-search strategy.
b) Explain with an example how
modular arithmetic can be used as a transformation technique. [16]
5.a) Give the control abstraction
for divide and Conquer strategy.
b) Determine the running time of
Quick sort algorithm in the average case. [16]
6.a) Explain how a max heap can be
used to implement a Priority queue.
b) Write Union and Find algorithms
that use weighting rule and collapsing rule respectively for disjoint sets.
[16]
7.a) Write Kruskal’s algorithm to
generate minimum cost spanning tree for a graph.
b) Explain the above algorithm with
an example. [16]
8.a) Give the essential difference
between the greedy method and dynamic programming.
b) Write an algorithm to solve
0/1-Knapsack problem. Note: Use dynamic programming approach. [16]
********
No comments:
Post a Comment