CS6402 DESIGN AND ANALYSIS OF ALGORITHMS Nov Dec 2015 Important Questions

Looking for important questions and answers for CS6402 DESIGN AND ANALYSIS OF ALGORITHMS . You will here find important questions / question bank for Anna University B.E CSE course . Read more details below.

Anna University Chennai
Department of Computer Science and Engineering
CS6402 DESIGN AND ANALYSIS OF ALGORITHMS
UNIT 4- ITERATIVE IMPROVEMENT
(100% NUMERICAL)
QUESTION BANK WITH SHORT ANSWER QUESTIONS

SYLLABUS: ITERATIVE IMPROVEMENT: The Simplex Method-The Maximum-Flow Problem–
Maximum Matching in Bipartite Graphs- The Stable marriage Problem.
1. Explain the simplex method with suitable example in detail? (16 or 8 Marks) Short answer questions:
1. What is meant by linear programming?
2. What is meant by simplex method?
3. What is meant by objective function? Or Define objective function?
4. Define optimal value?
5. Define optimal solution?
6. What is meant by decision variables?
7. What is meant by basic feasible solution?
8. Define pivoting?
9. What is meant by entering variable?
10. What is meant by departing variable?
11. What is meant by Z-value?
12. What are the steps involved while solving a linear programming problem?
13. How to create initial table in LP?
14. How to find basic feasible solution?
15. How to check optimality?
16. How to find entering variable?
17. How to find departing variable?
18. How to find a pivot?
19. Write a formula for Gauss Jordan elimination method?
20. How to obtain Departing variable?
21. How to locate departing variable?
22. Draw a graph to represent feasible solution region?

2. Consider the following linear programming problem with two variables –x + y ≤ 12, x + y ≤
30, 2x + 5y ≤ 90. Find the maximum value of z= 4x + 6y , where x ≥ 0 and y ≥ 0. (16 or 8
Marks)
Short answer questions:
1. How to check optimality?
2. How to find entering variable?
3. How to find departing variable?
4. How to find a pivot?
5. Write a formula for Gauss Jordan elimination method?
3. Explain the maximum flow problem with suitable example in detail? (16 or 8 Marks)
Short answer questions:
1. What is meant by maximum flow? Or Define maximum flow?
2. What is meant by maximum feasible flow? Or Define maximum feasible flow?
3. What is meant by flow? Or Define flow?
4. Define capacity? Or How to find capacity?
5. What are the methods are there to find maximum flow?
6. How to find maximum flow by using Ford-Fulkerson algorithm?
7. What is meant by flow network? Or Define flow network?
8. What is meant by source node? Or Define source node?
9. What is meant by sink node? Or Define sink node?
10. What are the important properties of flow networks?
11. What is meant by Capacity constraint?
12. What is meant by Skew symmetry?
13. What is meant by Flow conservation?
14. What is meant by Ford-Fulkerson Method?
15. What is the purpose of using Ford-Fulkerson method?
16. Write an algorithm for Ford-Fulkerson method?
17. Give the analysis for Ford-Fulkerson method?
18. Give the time complexity for Ford-Fulkerson method?
19. What are the main things involved in Ford-Fulkerson method?
20. What is meant by residual network?
21. How to find residual network?
22. What is meant by augmenting path?
23. How to find augmenting path?
24. What is meant by cuts?
25. How to find cuts in flow networks?
4. Explain the Ford – Fulkerson method with suitable example in detail? (16 or 8 Marks)
Short answer questions:
1. What is meant by Ford-Fulkerson Method?
2. What is the purpose of using Ford-Fulkerson method?
3. Write an algorithm for Ford-Fulkerson method?
4. Give the analysis for Ford-Fulkerson method?
5. Give the time complexity for Ford-Fulkerson method?
6. What are the main things involved in Ford-Fulkerson method?
7. What is meant by residual network?
8. How to find residual network?
9. What is meant by augmenting path?
10. How to find augmenting path?
11. What is meant by cuts?
12. How to find cuts in flow networks?
5. Apply the Ford Fulkerson method for the following graph (16 or 8 Marks)
Short answer questions:
1. What is meant by Ford-Fulkerson Method?
2. What is the purpose of using Ford-Fulkerson method?
3. Write an algorithm for Ford-Fulkerson method?
4. Give the analysis for Ford-Fulkerson method?
5. Give the time complexity for Ford-Fulkerson method?
6. Explain the maximum matching bipartite graph algorithm with suitable example in detail? (16 or 8 Marks)
Short answer questions:
1. What is meant by Bipartite graph? Or Define Bipartite graph?
2. Draw a Bipartite graph?
3. What is meant by matching? Or Define matching?
4. What is meant by Two-colorable graph?
5. What is meant by free vertex?
6. How to find free vertex?
7. What is meant by alternating path?
8. How to find alternating path?
9. What is meant by augmenting path?
10. How to find augmenting path?
11. How to find maximum matching or maximum cardinality matching?
12. What is meant by maximum matching or maximum cardinality matching? Or Define Maximum matching or
maximum cardinality matching?
13. What is meant by Maximum matching problem? Or Define Maximum matching problem?
14. What are the steps involved in iterative improvement technique?
15. How to find perfect matching?
16. What is meant by perfect matching? Or Define perfect matching?
17. Write an algorithm for maximum matching?
18. Give the applications of maximum matching problem?
7. Apply the maximum matching algorithm to the following bipartite graph. (16 or 8 Marks)
Short answer questions:
1. What is meant by Bipartite graph? Or Define Bipartite graph?
2. Draw a Bipartite graph?
3. What is meant by matching? Or Define matching?
4. What is meant by Two-colorable graph?
5. What is meant by free vertex?
8. Explain the stable marriage problem with suitable example in detail? (16 or 8 Marks)
Short answer questions:
1. Define stable marriage problem? Or what is meant by stable marriage problem?
2. Write an algorithmic version of bipartite matching problem?
3. What is meant by classic problem?
4. How to find stable matching between two sets?
5. What are the steps involved while solving the stable marriage problem?
9. Consider that there are 4 Men and 4 Women. The Men are named as A,B,C,D and the Women are named as X,Y,Z,W. (16 or 8 Marks).
Short answer questions:
1. Define stable marriage problem? Or what is meant by stable marriage problem?
2. Write an algorithmic version of bipartite matching problem?
3. What is meant by classic problem?
4. How to find stable matching between two sets?
5. What are the steps involved while solving the stable marriage problem?

Share This