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)
