ISL ENGINEERING COLLEGE
DEPARTMENT OF COMPUTER
SCIENCE AND ENGINEERING
DESIGN AND ANALYSIS OF ALGORITHMS
QUESTION BANK
Academic Year: 2020-21
SHORT ANSWER
QUESTIONS
UNIT-I
1. Why is an algorithm analysis required?
2.
State about UNION & FIND operations.
3.
List out the UNION algorithm using weighting rule.
4. Given f(n)=10n2+4n+3, then prove
that f(n)=O(n2).
5. List and define operations performed on sets?
6. What do you mean by performance analysis of an algorithm? Explain.
7.
Explain the significance of
input size of a problem.
8. State the weighting, collapsing rules in sets.
9. Explain set representation and write algorithm
for FIND.
10. Solve T(n)=3T(n/3)+√n.
11. Define the terms direct recursive
and indirect recursive algorithms.
UNIT-II
1.
Briefly differentiate quick sort and
merge sort.
2.
Define optimal storage
on tapes.
3. Write control abstraction for
i.
greedy method.
ii.
divide and conquer approach?
4. Define feasible
solution w.r.t greedy knapsack problem.
5.
What do you understand by worst-case time complexity? Give it
for merge sort algorithm.
6.
Define the terms
feasible solution, optimal
solution and objective function.
7.
What is job sequencing using deadlines?
8. Solve fractional knapsack problem for the given problem instance
weights W:{1,4,8,2,6} Profit
P:{4,10,5,15,20}. The Knapsack capacity is 30.
9. Write an algorithm for finding minimum element in a list of
elements.
10. What is the time required to compute a minimum weight
spanning tree for any
given weighted graph
with E edges and V vertices?
UNIT-III
1.
State travelling sales
person problem
2.
Differentiate knapsack problem
and 0/1 knapsack problem.
3. When do you apply dynamic
programming to solve
a problem?
4. What do you mean by forward and backward approach of problem
solving in dynamic programming?
5. Differentiate greedy
method and dynamic
programming.
6. Explain All pairs shortest path problem with
suitable example?
7. Define principle
of optimality
8. Solve the fractional
knapsack problem by considering the instance:
Weights are W : {1,3,5,6,7}, profits
,P: {3,9,7,11,18}. The knapsack capacity is
15.
9. Is dynamic programming better than greedy
algorithm design technique? Justify?
10. Differentiate greedy method
and dynamic programming.
11. Define chromatic number of a graph
12. Explain about
explicit and implicit
constraints of 8-queen’s problem.
13. What is Hamiltonian cycle? How it is different from the tour of travelling salesperson problem?
14. Define the properties of LC search
15. Differentiate FIFO and LC branch and bound techniques
16. State 4-Queens’ problem.
17. What is meant by lower
bound theory?
18. Explain graph
coloring problem.
19. What is the objective of m-colorability optimization problem?
20. Differentiate FIFO, LIFO branch and bound.
21. Differentiate Backtracking with branch and bound.
22. What are explicit and implicit constraints in backtracking algorithm?
23. What is a Hamiltonian cycle? Give an example.
24. Write about Least Count Search.
25. Define Chromatic number
26. Differentiate LCBB and
FIFO branch and bound?
27. What is chromatic number? Give an example.
UNIT-IV
1.
Explain bi-connected components with an example.
2.
Define articulation point. Give an example
3.
What is B-Tree?
4.
What is a Bi-connected component?
5. Give an example of a biconnected
graph.
6. Define Tries and different
types of tries?
7.
List out the properties of biconnected graphs
8. What is a tree edge and back edge. Explain with
an example.
UNIT-V
1. State node cover decision problem
2. What is NP completeness
3.
Define the terms
cliques, node cover.
4. Differentiate between
NP-hard and NP-complete.
5. State Cook’s theorem.
6.
Discuss Clique Decision
problem.
7. List out the functions used to specify non deterministic algorithm?
8. Define NP-complete and NP-hard problems. Give an example
for each.
9.
List out the NP-Hard code generation problems
10. What is meant by satisfiability?
11. State the problem of selection
12. Define Satisfiability problem.
13. List out the various
NP-Hard graph problem
14. What is meant by Halting
Problem?
15. Show the relationship
between P, NP, NP-Complete and NP-Hard and explain.
16. Differentiate NP-Hard
and NP-complete problems.
17. Define the terms cliques,
node cover.
18. What are NP-Hard code generation problems?
19. What is satisfiability?
20. Differentiate between
NP-hard and NP-complete.
LONG ANSWER QUESTIONS
UNIT-I
1.
What is asymptotic complexity of an algorithm? Give an
example of an algorithm whose complexity is O(nlogn).
2.
Explain Disjoint set operation in detail.
3.
What is basic data structures.
Write short notes on
i.
Big Oh
notation & Theta notation
ii.
DAG for common
sub expression
iii.
Priori and posteriori analysis
iv.
Disjoint set
union
v.
Asymptomatic Notations
UNIT-II
1. Write algorithm to find maximum and minimum from a set.
2. Write algorithm to find maximum and minimum using divide and conquer.
3. Explain Binary Search?
4. Explain Single Source
Shortest Path Problem using Greedy Method with suitable example?
5. Write an algorithm for merge sort and write the time
complexities.
6.
Derive the time complexity of quick sort algorithm.
7.
Find feasible solution
for given jobs with deadlines.
N=7, (p1,p2,….p7)=(3,5,20,18,1,6,30), (d1,d2,……d7)=(1,3,4,3,2,1,2)
8. What is a
knapsack problem? Explain. Find an optimal solution to the knapsack problem
when (W1,W2,W3,W4)=(10,15,6,9) ,
(P1,P2,P3,P4)=(2,5,8,1) , Knapsack Capacity=25.
9.
Find the minimum
cost spanning tree for the
given graph (Consider any example.)
10. Define spanning
tree and explain
Prim’s algorithm for finding minimum
spanning tree of the graph
using any graph.
11. Briefly explain
spanning tree and their application.
12. Explain job sequencing with deadline algorithm with an example.
13. Explain in detail any two problems that can
be solved using
divide & conquer strategy.
14. Write short notes on:
i.
Job scheduling with deadlines using greedy
approach.
UNIT-III
1. Explain the forward and backward approaches of problem solving in dynamic programming.
2.
Solve the travelling salesperson problem using dynamic programming for the following
3. Explain about all pairs shortest path
problem with example and write algorithm.
4.
Using dynamic programming approach, identify the articulation points in the graph below
5.
Solve the all pairs
shortest path problem for a
digraph with the following weight
matrix
6. Write an algorithm for all pairs shortest paths
7. Solve the 0/1 Knapsack
instance where
n=3, (w1,w2,w3) = (2,3,4) , (p1,p2,p3) =( 1,2,5) and using dynamic
programming.
8.
Define m – coloring problem. Write an algorithm to
solve it using backtracking.
9.
Write an algorithm to find
all m-coloring of a graph.
10. Explain about DFS with example. Write algorithm and its time complexity.
11. Differentiate between
back tracking and branch and bound strategies.
12. Write an algorithm for N-Queens
problem.
13. Explain solution
of graph coloring
problem using backtracking.
14. What is branch and bound strategy? Explain.
15.Consider travelling sales person instance
Obtain the state space
tree that is generated by LCBB.
16. Explain back tracking. Give the various
applications of backtracking.
17. Solve the 8-Queens’s problem
using backtracking.
18. Write an algorithm for 8-Queen’s problem using backtracking.
19. What are Hamiltonian cycles? Present an algorithm that finds all the Hamiltonian cycles of a given graph.
20. What is Hamiltonian cycle? How is it different from the tour of traveling sales person problem? Explain.
21. Write short notes on
i.
State space tree
ii.
Graph Coloring
iii.
Lower bound theory
22. Write short notes on
i.
Control abstraction for dynamic programming
ii.
Reliability Design
iii.
Divide & Conquer
iv.
State Space Tree
v.
Principle of optimality
vi.
Control abstraction for Least cost Search
UNIT-IV
1. Define biconnected component of a graph. Identify
articulation point and draw biconnected components of (Consider any example from this topic)
2.
Explain about DFS with example.
Write algorithm and its time complexity.
3. Explain
in detail Breath
First Search (BFS) with suitable
example?
4. Explain Tries in detail.
5. What is B-tree explain in
detail.
6.
Define chromatic number. Draw the state space tree for the following
graph with n=5, m=3.
UNIT-V
1.
Explain in brief NP hard
and NP complete problems.
2. Differentiate between
NP-complete and NP-hard.
3.
Briefly explain three
NP-hard graph problems.
4.
Explain the terms NP-Complete and NP-hard.
5. Define node covering problem. Give an example.
6. Write non deterministic algorithm
for searching.
7.
Write non deterministic algorithm for sorting.
8. Explain about NP-Hard scheduling problems.
9. State Cooks theorem and prove it. Explain its significance in NP- Complete theory.
10. Discuss NP-Hard
code generation problems.
11. Difference between
NP-Hard and NP-Complete.
12. Write short notes on
i.
Node Cover Decision
Problem
ii.
DAG for common sub expression
iii.
Satisfiability problem
iv.
Non deterministic algorithms
v.
Reducibility
M and m logico solutions
ReplyDeleteWelcome to MandM Logico Solutions, your premier destination for best LIMO rental services in the USA. We are famous for offering a fleet of luxurious vehicles that display elegance and style. Whether you’re in need of a stylish party bus, an exotic or vintage car, or the comfort of chauffeur services, we deliver unforgettable journeys.