ISL ENGINEERING COLLEGE
DEPARTMENT OF INFORMATION TECHNOLOGY
DESIGN AND ANALYSIS OF ALGORITHMS
QUESTION BANK
BE III Year II Semester – PC 602 IT
Academic Year:
2020-21
SHORT ANSWER
QUESTIONS
UNIT-I
1.
Explain linear probing
in Hashing with an example.
2. Define Heap.
3. List out the collision
resolution techniques in hashing.
4. Why is an algorithm analysis required?
5.
State about UNION & FIND operations.
6.
List out the UNION algorithm using weighting rule.
7. Given f(n)=10n2+4n+3, then prove
that f(n)=O(n2).
8. List and define operations performed on sets?
9. What do you mean by performance analysis of an algorithm? Explain.
10. Explain the significance of input size of a problem.
11. State the weighting, collapsing rules in sets.
12. Explain set representation and write algorithm
for FIND.
17. Solve T(n)=3T(n/3)+√n.
18. 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 is the time complexity of
the optimal storage on tapes problem?
6.
What do you understand by worst-case time complexity? Give it
for merge sort algorithm.
7. State the optimal storage on multiple tapes problem.
8.
Define the terms
feasible solution, optimal
solution and objective function.
9.
What is job sequencing using deadlines?
10. Explain optimal
merge pattern with an example.
11. 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.
12. Write an algorithm for finding minimum element in a list of
elements.
13. 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.
Define articulation point. Give an example
3.
Differentiate knapsack problem
and 0/1 knapsack problem.
4. When do you apply dynamic
programming to solve
a problem?
5. What do you mean by forward and backward approach of problem
solving in dynamic programming?
6.
Explain biconnected components with an example.
7. Differentiate greedy
method and dynamic
programming.
8. What is multistage graph?
9.
List out the properties of biconnected graphs
10. Define principle
of optimality
11. What is a Bi-connected component?
12. What is depth first search?
13. 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.
14. Give an example of a biconnected
graph.
15. Is dynamic programming better than greedy
algorithm design technique? Justify?
16. Differentiate greedy method
and dynamic programming.
UNIT-IV
1.
Define chromatic number
of a graph
2. Explain about
explicit and implicit
constraints of 8-queen’s problem.
3.
What is Hamiltonian cycle? How it is different from the tour of travelling salesperson problem?
4.
Define the properties of LC search
5. Differentiate FIFO and LC branch and bound techniques
6. State 4-Queens’ problem.
7. What is meant by lower
bound theory?
8.
Explain graph coloring
problem.
9. What is Hamiltonian cycle? How is it different from the tour of traveling
salesperson problem?
10. What is a tree edge and back edge. Explain with
an example.
11. What is the objective of m-colorability optimization problem?
12. Differentiate FIFO, LIFO branch and bound.
13. Differentiate Backtracking with branch and bound.
14. What are explicit and implicit constraints in backtracking algorithm?
15. What is a Hamiltonian cycle? Give an example.
16. State the purging rule and
list out its applications
17. Write about Least Count Search.
18. Define Chromatic number
19. Differentiate LCBB and
FIFO branch and bound?
20. What is chromatic number? Give 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 the basic
requirement of a planar
graph?
15. What is meant by Halting
Problem?
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.
Construct 10-entry Hash table for hashing the keys 15,
32, 12, 77, 85, 67, 26, 48, 113, 54 using the function (i+6) mod 10
using linear probing.
2.
Explain step by step
heap sort with example
and write an algorithm for heap sort.
3. Write an algorithm to delete an element from max heap.
4. Write an algorithm to form a heap using Heapify and
discuss its time complexity.
5.
Solve the following recurrence relation using
6.
What is asymptotic complexity of an algorithm? Give an
example of an algorithm whose complexity is O(nlogn).
Write short notes on
i.
Big Oh
notation & Theta notation
ii.
Priori and posteriori analysis
iii.
Hash Function
iv.
Collision Resolution Techniques
v.
Disjoint set
union
vi.
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. Find an optimal binary merge pattern
for ten files whose length are 28, 43, 9, 18,
74,53,94,36,13,11.
4. Write an algorithm for merge sort and write the time
complexities.
5.
Derive the time complexity of quick sort algorithm.
6.
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)
7.
Explain about DFS with example.
Write algorithm and its time complexity.
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.
ii.
Optimal merge pattern
UNIT-III
1. Solve the following instance
of optimal cost binary
search tree n=4; (a1-a4)=(do,if,int,while), P(1:4)=(3,3,1,1), Q(0:4)=(2,3,1,1,1)
2. Explain the forward and backward approaches of problem solving in dynamic programming.
3.
Solve the travelling salesperson problem using dynamic programming for the following
4. Explain about all pairs shortest path
problem with example and write algorithm.
5.
Using dynamic programming approach, identify the articulation points in the graph below
6.
Solve the all pairs
shortest path problem for a
digraph with the following weight
matrix
7.
Consider the multistage graph. Find the shortest
path from S to T.
8. Write an algorithm for all pairs shortest paths
9. Define biconnected component of a graph. Identify
articulation point and draw biconnected components of (Consider any example from this topic)
10. 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.
11. Consider traveling
sales person instance
Obtain the state space tree
that is generated by LCBB
12. Write short notes on
i.
Control abstraction for dynamic programming
ii.
Reliability Design
iii.
Divide & Conquer
iv.
State Space Tree
v.
Optimal Binary Search
Tree
vi.
Principle of optimality
vii.
DFS with example
viii.
Control abstraction for Least cost Search
UNIT-IV
1.
Define m – coloring problem. Write an algorithm to
solve it using backtracking.
2.
Write an algorithm to find
all m-coloring of a graph.
3.
Differentiate between back tracking and branch and bound strategies.
4.
Define chromatic number. Draw the state space tree for the following
graph with n=5, m=3.
5. Write an algorithm for N-Queens
problem.
6.
Explain solution of graph coloring
problem using backtracking.
7.
What is branch
and bound strategy? Explain.
8. Consider travelling sales person instance
Obtain the state space
tree that is generated by LCBB.
10. Explain back tracking. Give the various
applications of backtracking.
11. Solve the 8-Queens’s problem
using backtracking.
12. Write an algorithm for 8-Queen’s problem
using backtracking.
13. What are Hamiltonian cycles?
Present an algorithm that finds all the Hamiltonian cycles of a given graph.
14. What is Hamiltonian cycle? How is it different from the tour of traveling
sales person problem?
Explain.
15. Write short notes on
i.
State space tree
ii.
Graph Coloring
iii.
Lower bound theory
UNIT-V
1.
Explain in brief NP hard
and NP complete problems.
2. Differentiate between
NP-complete and NP-hard.
3. Explain in detail
about the AND-OR graph decision problem.
4.
Briefly explain three
NP-hard graph problems.
5.
Explain the terms NP-Complete and NP-hard.
6. Define node covering problem. Give an example.
7. Write non deterministic algorithm
for searching.
8.
Write non deterministic algorithm for sorting.
9. Explain about NP-Hard scheduling problems.
10. State Cooks theorem and prove it. Explain its significance in NP- Complete theory.
11. Discuss NP-Hard
code generation problems.
12. Difference between
NP-Hard and NP-Complete.
13. Write short notes on
i.
Node Cover Decision
Problem
ii.
Satisfiability problem
iii.
Non deterministic algorithms
iv.
Reducibility
Comments
Post a Comment