**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

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 )**

- 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**.

**FOR MORE QUESTION PAPERS CLICK HERE**

**070230017 DESIGN ANALYSIS OF ALGORITHMS**

**PREVIOUS YEAR QUESTION PAPERS**