Admin Welcomes U CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS question banks ~ ANNA UNIVERSITY QUESTION BANKS PAPERS WITH SOLUTIONS

JOIN WITH US :)

If any add appear like this please click skip add

Category

INFO

CLICK HERE
FOR LATEST RESULTS
LATEST NEW TIME TABLE/EXAM DATES FOR ALL LINK1 LINK2
ANNA UNIVERSITY COLLEGES RANK LIST 2012 CHECK SOON
LATEST FREE PLACEMENT PAPERS FOR ALL COMPANIES CHECK SOON
GET FREE MINI PROJECTS AND FINAL YEAR PROJECTS CLICK HERE
LATEST HOT HACKING TRICKS CLICK HERE

LATEST QUESTION BANKS /PAPERS/entrance FOR ALL EXAMS CLICK HERE link1 link2




our sites
www.tricksnew.blogspot.com www.questionbank.tk
www.freeminiproject.blogspot.com and
www.onlineinfocity.
blogspot.com


NOTE:

FEEL FREE TO CONTACT US click on me
DONT FORGET TO SUBSCRIBE YOUR MAIL ID ----->>>TO GET DAILY question banks IN YOUR INBOX::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: SEE RIGHT SIDE CORNER

Thursday, April 26, 2012

CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS question banks


click here to download  ful paper qb updated part 1



click here to download  ful paper qb updated part 2


http://www.mediafire.com/?7bu6dklkz5bznuq
sorry for the this error





Reg. No. :
B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2010
Fourth Semester
Computer Science and Engineering
CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
Time : Three hours
Answer ALL questions
Maximum : 100 Marks
PART A — (10 × 2 = 20 Marks)
1.
2.
3.
If f (n ) = a m n m + ....a1 n + a 0 , then prove that f (n ) = O(n m ) .
Establish the relationship between O and Ω .
Trace the operation of the binary search algorithm for the input –15, –6, 0, 7,
9, 23, 54, 82, 101, 112, 125, 131, 142, 151, if you are searching for the
element 9.
State the general principle of greedy algorithm.
State the principle of optimality.
4.
5.
6.
7.
8.
9.
10.
Compare divide and conquer with dynamic programming and dynamic
programming with greedy algorithm.
Explain the idea behind backtracking.
Define and solve the graph colouring problem.
Define NP Hard and NP Completeness.

What is a Minimum spanning tree?
Explain briefly the Time Complexity estimation, space complexity
estimation and the trade off between Time and Space complexity. (6)
Solve the following recurrence equations completely
 (1)
T (n ) =
T (n ) = 1, if n = 1 .
T (n ) = 5T (n 1) 6T (n 2)

 
n 1
i =1
T (i ) + 1, if n 2
(4)
(3)
(3)
(2)
(3)
            n
T (n ) = 2T   + n lg n .
            2
Or


 
Question Paper Code : 53099


(b)
(i)
Write the linear search algorithm and analyse for its best, worst
and average case time complexity.(10)
Prove that for any two functions
f (n ) and
g (n ) , we have
(ii)
f (n ) = è ( g (n )) if and only if f (n ) = O ( g (n )) and f (n ) = Ω( g(n )) . (6)
12.
(a)
(i)
Write a recursive algorithm to determine the max and min from a
given element and explain. Derive the time complexity of this
algorithm and compare it with a simple brute force algorithm for
finding max and min.(10)
For the following list of elements trace the recursive algorithm for
finding max and min and determine how many comparisons have
been made.
22, 13, –5, –8, 15, 60, 17, 31, 47.
Or
(ii)
(b)
(i)
Write the container loading greedy algorithm and explain. Prove
that this algorithm is optimal.(8)
Suppose you have 6 containers whose weights are 50, 10, 30, 20,
60, 5 and a ship whose capacity is 100. Use the above algorithm to
find an optimal solution to this instance of the container loading
problem.(8)
Write and explain the algorithm to compute the all pairs source
shortest path using dynamic programming and prove that it is
optimal(8)
For the following graph having four nodes represented by the
matrix given below determine the all pairs source shortest path (8)
(ii)
13.
(a)
(i)
(ii)

(b)
(i)

Write the algorithm to compute the 0/1 knapsack problem using
dynamic programming and explain it.(8)

(ii)
Solve the following instance of the 0/1, knapsack problem given the
knapsack capacity is W = 5(8)
Items
1
2
3
4
Weight
2
1
3
2
Value
12
10
20
15

 
    
0 3
2 0 ∞ ∞
7 0 1
6 ∞ ∞ 0
Or
 
2


 
(6)
53099


14.
(a)
Or
(b)
Write an algorithm to determine Hamiltonian cycle in a given graph
using back tracking. For the following graph determine the Hamiltonian
cycle.(8 + 8)
15.
(a)

(b)
Write an algorithm and explain to determine Biconnected Components.
Prove the theorem that two biconnected components can have at most
one vertex as common and this vertex is an articulation point.(10 + 6)







Powered by

www.annaunivquestionbanks.blogspot.com

1
2
3
4
4
7
5
3
40
42
25
12
Items
Weight
Value
Or
——————
3

Explain with an algorithm as to how 0/1 knapsack problem is solved
using branch and bound technique. Apply branch and bound technique to
solve the following 0/1 knapsack instance if W = 10.(8 + 8)



53099
Write an algorithm to determine the Sum of Subsets for a given Sum and
a Set of numbers. Draw the tree representation to solve the subset sum
problem given the numbers set as {3, 5, 6, 7, 2} with the Sum = 15. Derive
all the subsets.(8 + 8)


click here to download  full paper qb updated


set 2 click here to download



DESIGN AND ANALYSIS OF ALGORITHMS QUESTION BANK
UNIT – I


PART A(2MARKS)

1. What is an algorithm?

2. What is meant by open hashing?

3. Define Ω-notation

4.Define order of an algorithm.

5. Define O-notation

6. Define conditional big-oh notation.

7. What do you mean by best case efficiency?

8. What is meant by worst case?

9. Define average case efficiency.

10. Why space complexity of a program is necessary?

11. What is an algorithm design technique?

12. Define little-oh notation.

13. Compare the order of growth n! and 2!

14. What are the types of algorithm efficiencies?

15. Prove or disprove if t(n) E O(g(n))then g(n) E omega t(n)?

PART B(16 MARKS)

1.(i) Explain the various criteria used for analyzing algorithms.

(ii) List the properties of various asymptotic notations.

2. (i) Explain the necessary steps for analyzing the efficiency of recursive algorithms.

(ii) Write short notes on algorithm visualization.

3. Describe briefly the notations of complexity of an algorithm.

4. (i) What is pseudo-code?Explain with an examples.

(ii) Find the complexity (C(n)) of the algorithm for the worst case ,best case and average case.(evaluate average case complexity for n=3,where n is number of inputs)

5. (i) What are the important problem types focused by the researchers?Explain any two with examples.

(ii) What is empirical analysis of an algorithm?Discuss its strength &weakness?

UNIT II


PART A (2 MARKS)

1. Give an non-recursive algorithm to find out the largest element in a list of n numbers.

2. What is meant by divide &conquer?

3. Give the recurrence relation for divide &conquer.

4. What is meant by greedy algorithm?

5. What is meant by knapsack problem?

6. Define fractional knapsack problem.

7. What is the difference between quicksort and mergesort?

8. Give the algorithm of quick sort.

9. What is binary search?

10. What is the average case complexity of linear search algorithm?

11.Define depth first searching technique.

12. Write the procedure for selection sort.

13. Differentiate dynamic programming and divide and conquer..

14. Give two real time problems that could be solved using greedy algorithm.

15. State the time complexity of bubble sort algorithm.

PART B(16 MARKS)

1.(i) Write a psedocode for divide and conquer algorithm for merging two sorted arrays into a single sorted one.Explain with an example. 8

(ii) Set up and solve a recurrence relation for the number of key comparisions made the above psedo code. 8

2. Design a recursive decrease by-one algorithm for sorting the n real numbers in an array with an examples and also determine the number of key comparisions and time efficiency of an algorithm.

16

3. (i)Define heap.Explain the properties of heap.

8

(ii) Write a simple example to explain heap sort algorithm.

8

4.(i) Write an algorithm to sort a set of N numbers using insertion sort.

8

(ii) Trace the algorithm for the following set of numbers:20,35,18,8,14,41,3,39.

8

5. (i) Explain the difference between depth first and depth first searches.

8

(ii) Mention any three search algorithm which is referred in general.

8

UNIT III


PART A(2 MARKS)

1. Define dynamic programming.

2. Differentiate between greedy method and dynamic programming.

3. Differentiate between divide and conquer and dynamic programming.

4. Define multistage graph.

5.What is meant by all pairs shortest path problem?

6.Write the running time of 0/1 knapsack problem.

7.Define optimal binary search tree.

8. What is meant by all pairs shortest path problem?

9. Give an application of dynamic programming algorithm.

10. Give the running time of the optimal BST algorithm.

11. Write recurrence relation for 0/1 knapsack problem.

12. Write down the floyds algorithm.

13. What is meant by bottom up dynamic programming?

14. What is meant by travelling salesperson problem?

15. What is the running time of dynamic programming TSP?

Part B (16 MARKS)

1. Describe the travelling salesman poblem and discuss how to solve it using dynamic programming?

2. Solve the all pairs shortest path problem for the diagraph with the weight matrix given below.

a

b

c

d

a

0


3


b

2

0



c


7

0

1

d

6



0

3. Find the optimal binary search tree for the key and probabilities given below.



4. Find the optimal solution for the given knapsack problem.



5. Solve all pairs shortest path problem for the digraph. 16

b to a -2,a to c-3,c to d-1,c to b-7,d to a- 6



UNIT IV


PART A (2marks)

1. State if backtracking always produces optimal solution.

2. Define backtracking.

3. What are the two types of constraints used in backtracking?

4. What is meant by optimization problem?

5. Define Hamiltonian circuit problem.

6. What is Hamiltonian cycle in an undirected graph?

7. Define 8queens problem.

8. List out the application of backtracking.

9. Define promising node and non-promising node.

10. Give the explicit and implicit constraint for 8-queen problem.

11. How can we represent the solution for 8-queen problem?

12. Give the categories of the problem in backtracking.

13. Differentiate backtracking and over exhaustive search.

14. What is state space tree?

15. Find optimal solution for the knapsack instance n =3,w=[20,15,15],P =[40,25,25]and C =30

PART B (16 MARK)

1.Apply backtracking technique to solve the following instance of the subset sum problem S = [1,3,4,5} and d=11 16

2. Explain subset-sum problem and discuss the possible solution strategies using backtracking.

3.Explain N-quence problem with an algorithm.Explain why backtracking is defined as a default procedure of last resort for solving problems.

4. (i) Explain ithe subset-sum problem in detail by justifying it using backtracking algorithm. 8 (ii) Apply backtracking to the problem of finding a Hamiltonian circuit for the following graph.



5. What is backtracking?Explain in detail.

UNIT- V

PART A(2 MARKS)

1. What is heuristics?

2. Explain briefly branch and bound technique for solving problems.

3. Differentiate between DFS and BFS.

4. What is travelling salesperson problem?

5. What is the formula used to find upper bound for knapsack problem?

6. Differentiate between back tracking and branch and bound.

7. Define articulation point.

8. Define spanning tree.

9. List out the application of branch and bound technique.

10. What is the assignment problem?

11.What is tree edge and cross edge?

12.Define back edge and tree edge.

13.What is the real time application of the assignment problem?

14. What is the metric used to measure the accuracy of approximation of algorithm?

15. What is pre-structuring ?Give examples.

PART B (16 MARK)

1.Solve the following instance of the knapsack problem by the branch and bound algorithm.

Item

Weight

Value

1

4

$40

2

7

#42

3

5

$25

4

3

$12

The Knapsack’s capacity W=10

2. Discuss the solution for knapsack problem using branch and bound technique.

3. What is branch and bound technique?Explain how knapsack problem could be solved using branch and bound technique.Solve the following instance of the knapsack problem by branch and bound algorithm for W=16



4.What is branch and bound?Explain in detail. 16

Reactions:

0 comments:

chitika