DAA - Important Questions

CS 2251 DESIGN AND ANALYSIS OF ALGORITHMS

IMPORTANT QUESTIONS

UNIT-II

Part A:

1.      What is the use of asymptotic notations?

2.      What are the properties of Big-Oh Notations?

3.      What is the idea behind binary search?

4.      What are the metrics that are used to measure the complexity of an algorithm?

5.      What is a Conditional Asymptotic notation?

6.      What kind of problems can be best solved using divide & conquer method.

7.      Define Recurrence equation. Give 1 example.

8.      How divide & conquer algorithms are implemented?

9.      Show that O(f(n)+O(g(n))=O(max{f(n),g(n)}

10.  What is the need for an algorithm analysis?

Part B:

1.      Develop an algorithm for binary search? Illustrate how best,Avg,Worst case complexities of binary search can be computed.(16)

2.      Explain the recursive function for finding the Maximum & Minimum of set of n elements& Find the Number of comparisons needed.(16)

3.      Apply the Merge sort algorithm for the following data set

999,45,12,99,65,43,121,21,122,32,44,55,77,66,11,222. Illustrate each step of algorithm.(16)

UNIT-II

Part A:

1.      What are the limitations of greedy algorithms?

2.      For what type of problems greedy algorithms are best suited?

3.      What is meant by greedy algorithm?

4.      Give the applications of greedy algorithms.

5.      Write down the advantages & disadvantages of greedy algorithms.

6.      What is meant by container loading?

7.      Give the greedy solution for container loading.

8.      Write down the analysis of container loading algorithm.

9.      Define Knapsack Problem.

10.  Define Fractional & 0/1 Knapsack Problem.

Part B:

1.      Solve the Container Loading Problem using Greedy Technique.(16)

2.      Explain Knapsack problem using Greedy Technique with example.(16)

UNIT III

Part A:

1.      What is multistage graph?

2.      What are optimal binary search trees?

3.      State the principles behind dynamic programming?

4.      State the travelling sales man problem.

5.      What in meant by All Pairs shortest path problem & How it is represented?

6.      Differentiate greedy method & dynamic programming.

7.      Differentiate divide & conquer & dynamic programming.

8.      Give an application of dynamic programming.

9.      Write the formula for Cost (I,j) of a multistage graph in forward & backward approach.

10.  Give the formula for All Pairs shortest path problem.

Part B:

1.      What is Dynamic programming? Apply this technique to find All Pairs shortest path in a graph.(16)

2.      Explain the multistage graph with either forward approach or backward approach.(16)

3.      Explain the travelling sales man problem and apply dynamic programming to solve it.(16)

4.      Explain Optimal binary Search trees using dynamic programming.(16)

5.      Explain about 0/1 Knapsack problem using dynamic programming.(16)

6.      What is Dynamic programming? Apply this technique to find All Pairs shortest path in a graph

                                                         UNIT IV

PART A:

1.      What is graph coloring problem?

2.      What is Hamiltonian path?

3.      What are solution states?

4.      Define a planar graph.

5.      Give the categories of the problem in backtracking?

6.      Define decision, optimization & enumeration problem.

7.      List out the application of backtracking.

8.      Define explicit & implicit constraints.

9.      Define state space tree.

10.  Define dead node.

PART B:

1.      Explain how backtracking technique works & apply it to 8Queens problem.(16)

OR

2.      Explain how sum of subsets is computed using backtracking technique with an example.(16)

3.      Explain Hamiltonian cycles & Explain the function to find as Hamiltonian cycles of a graph.(16)

OR

4.      What is Knapsack problem? Explain how backtracking technique is used to solve Knapsack problem.(16)

                                                          UNIT V

PART A:

1.      What is spanning trees?

2.      When is problem called to be NP-Hard?

3.      What are Biconnected components?

4.      List the two properties that must be satisfied by a problem L to be NP complete.

5.      What is nondeterministic polynomial time?

6.      Define Articulation point.

7.      List out the types of branch & bound technique.

8.      List out the types of graph.

9.      List out the types of graph traversal.

10.  Difference between DFS & BFS.

PART B:

1.      Explain the graph traversal algorithms with an example.(16)

OR

2.      What is the idea behind branch & bound technique? Explain how this technique is applied for global optimization problems? (16)

3.      Explain the tech used to find minimal spanning tree  & biconnected components with an example.(16)

OR

4.      What is the idea behind branch & bound technique? Explain how this technique is applied for knapsack problem.(16)