Code No: 156AN R18

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

jn
B. Tech III Year II Semester Examinations, August - 2022
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE, ITE)
t
Time: 3 Hours [Link]
uh
Answer any five questions
All questions carry equal marks
---
us
1. Show that the following equalities are correct:
a) 5n2 - 6n = θ (n2)
b) n! = O(nn)
ed
c) 2n22n + n log n = θ (n22n)
d) n3 + 106n2 = θ (n3). [4+4+4+3]

2.a) What are asymptotic notations? Explain with examples.

b) Write and explain quick sort algorithm with an example. [8+7]
pa
3.a) Write and explain find algorithm with collapsing rule.
b) Describe the general method of backtracking. [8+7]
pe
4.a) What are union and find operations? Explain with suitable examples.
b) Explain about graph coloring algorithm. [8+7]
ra
5.a) Solve the following 0/1 knapsack problem using dynamic programming
n=3, (W1, W2, W3) = (2, 3, 3) (P1, P2, P3) =(1,2,4) and m=6.
ug
b) Differentiate between dynamic programming and divide and conquer. [8+7]

6. Consider four elements a1 < a2 < a3 < a4 with q(1, 2, 3, 4) = (1/8, 3/16, 1/16, 1/16) and
-2
(p1, p2, p3, p4) = (1/4, 1/8, 1/16, 1/16). Construct the table of values of W (i, j), R(i, j)
and C(i, j) computed by the algorithm to compute the roots of optimal sub-tree. [15]
02
7.a) Describe Greedy method control abstraction for the subset paradigm.
b) Write an algorithm of Greedy knapsack. [8+7]

8.a) Write a non-deterministic algorithm of sorting a list of elements in an array.

2
b) Explain the applications of branch and bound. [8+7]

---oo0oo---
 R18
U
Code No: 156AN
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
SE
B. Tech III Year II Semester Examinations, August/September - 2021
DESIGN AND ANALYSIS OF ALGORITHMS
(Computer Science and Engineering)
Time: 3 Hours Max. Marks: 75
Answer any five questions
D
All questions carry equal marks
---
PA
1.a) Write and explain randomized quick sort algorithm.
b) Discuss about Big oh O, Omega Ω and Theta θ notations with examples. [8+7]

2.a) Using Merge sort, sort the following elements:

PE
310, 285, 179, 652, 351, 423, 861, 254, 450, 520
b) Analyze the computing time complexity of binary search algorithm. [7+8]

3.a) Show that depth first search can be used to find the connected components of an
R
undirected graph.
b) Write an algorithm of n-queen’s problem and explain. [8+7]
SA
4. Suppose we start with n sets, each containing a distinct element.
a) Show that if u unions are performed, then no set contains more than u+1 elements.
b) Show that at most n – 1 unions can be performed before the number of sets
U
becomes 1.
c) Show that if fewer than (n/2) unions are performed, then at least one set with a single
element in it remains.
G
[5+5+5]

5.a) Solve the following 0/1 Knapsack Problem using dynamic programming
/S
n=4, m=30, (w1,w2,w3,w4) = (10,15,6,9) and (p1, p2, p3, p4) = (2,5,8,1).
b) Explain the concept of the traveling salesperson problem. [7+8]
EP
6. Use the function OBST to compute w(i,j), r(i,j), and c(i,j), 0 ≤ i < j ≤ 4, for the
identifier set (a1, a2, a3, a4) = (do, if, int, while) with p(1 : 4) = (3, 3, 1, 1) and
q(0:4)=(2,3,1,1,1). Using the r(i,j)’s construct the optimal binary search tree. [15]
-
7.a) Explain the general method of Greedy method.
20
b) Write and explain the Kruskal’s algorithm with an illustrative example. [7+8]

8.a) Explain with respect to branch and bound 0/1 knapsack problem.
21
b) Discuss in detail about the classes of NP-hard and NP-complete. [7+8]

---ooOoo---
Code No: 156AN R18
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech III Year II Semester Examinations, February - 2023
DESIGN AND ANALYSIS OF ALGORITHMS
JN
(Common to CSE, ITE)
Time: 3 Hours Max. Marks: 75

Note: i) Question paper consists of Part A, Part B.

TU
ii) Part A is compulsory, which carries 25 marks. In Part A, Answer all questions.
iii) In Part B, Answer any one question from each unit. Each question carries 10 marks
and may have a, b as sub questions.
H
PART – A
(25 Marks)
U
1.a) What is an algorithm? [2]
b) Explain about big-oh notation. [3]
se
c) Define static space tree. [2]
d) Write and explain general iterative backtracking method. [3]
e) What is the time complexity of all pairs shortest path? [2]
d
f) Explain about OBST. [3]
g) What is Greedy method? [2]
h) Distinguish between Prim’s and Kruskal’s algorithms. [3]
pa
i) Define branch and bound technique. [2]
j) Explain about non-deterministic algorithms. [3]

PART – B
pe
(50 Marks)

2.a) Write and explain the general method of divide-and-conquer strategy.

rs
b) Derive the time complexity of Strassen’s matrix multiplication. [5+5]
OR
3.a) Write and explain recursive algorithm of binary search method.
20
b) What is space complexity? Explain with suitable examples. [5+5]

4.a) Describe recursive formulation of backtracking technique.

b) How to implement disjoint sets? Explain. [5+5]
23
OR
5.a) Explain about 4-queens problem with backtrack solution.
b) Discuss about number of connected components of a graph using disjoint set union.
[5+5]

6. Use the function OBST to compute w(i, j), r(i, j), and c(i, j), 0 ≤ i < j ≤ 4, for the
identifier set (a1, a2, a3, a4) = (do, if, int, while) with p(1:4) = (3, 3, 1, 1) and
q(0:4) = (2, 3, 1, 1, 1). Using the r(i, j)’s construct the optimal binary search tree. [10]
OR
7. Discuss about all pairs shortest problem using dynamic programming. [10]
8. Compute a minimum cost spanning tree for the graph shown below using
a) Prim’s algorithm and
b) Kruskal’s algorithm. [5+5]
JN
TU
H

OR
U
9. Explain about single source shortest path problem in Greedy method. [10]
se
10. Describe LC branch and bound solution of 0/1 Knapsack problem in detail. [10]
OR
11. Explain the following:
d
a) Nondeterministic knapsack algorithm
b) FIFO branch and bound. [5+5]
pa
---ooOoo---
pe
rs
20
23
 R18
us
Code No: 156AN
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech III Year II Semester Examinations, February/March - 2022
ed
DESIGN AND ANALYSIS OF ALGORITHMS
(Computer Science and Engineering)
Time: 3 Hours Max. Marks: 75
Answer any five questions
All questions carry equal marks
pa
---

1.a) Discuss in detail various notations used for expressing the time complexity of
pe
algorithms, with examples.
b) What is Performance Analysis? Explain Space Complexity and Time Complexity with
examples. [7+8]
rf
2.a) Explain the process of merge sort by a list of any 11 integers (distributed randomly).
Write the algorithm and analyze its time complexity.
eb
b) Write an algorithm to find matrix multiplication using Strassen’s. [8+7]

3.a) Describe the Backtracking technique to the m-coloring graph. Explain with an example.
b) Write an algorithm of weighted union and also compute the time complexity of the
/m
same. [8+7]

4.a) Draw the state space tree for ‘m’ coloring when n=3 and m=3.
ar
b) Write an algorithm for the 8-queens problem using backtracking. [8+7]

5.a) Solve the solution for 0/1 knapsack problem using dynamic programming:
-2
(p1,p2,p3, p4) = (11, 21, 31, 33), (w1, w2, w3, w4) = (2, 11, 22, 15), M=40, n=4.
b) State the principle of optimality in dynamic programming. How to apply this to the
0
shortest path problem? [8+7]
22
6.a) Explain about OBST.
b) Write an algorithm of all pairs shortest path problem. [8+7]

7. Explain the problem of job sequencing with deadlines by taking an example. Write the
jn
algorithm to solve the problem using the Greedy Method. Show how the algorithm
solves the following job sequencing with deadlines problem.
n = 4, (p1, p2, p3, p4) = (100, 10, 15, 27) and (d1, d2, d3, d4) = (2, 1, 2, 1) [15]
tu
8.a) Explain Cook’s theorem with an example.
h
b) Discuss the FIFO branch and bound. [8+7]

---oo0oo---
 Code No: 135AF R16
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech III Year I Semester Examinations, August - 2022
DESIGN AND ANALYSIS OF ALGORITHMS
jn
(Common to CSE, IT)
Time: 3 Hours Max. Marks: 75
tu
Answer any five questions
All questions carry equal marks
---
h
1.a) Explain about the types of Randomized algorithm.
us
b) Write an algorithm of Quick sort and analyze performance of quick sort in worst case.
[7+8]
ed
2.a) What are asymptotic notations? Explain with examples.
b) Sort the following elements using Merge sort: [7+8]
12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18

3.a) Explain the Union algorithm with weighing rule.

pa
b) Discuss about the general method of backtracking. [7+8]

4.a) Write an algorithm to determine Bi-connected components.

pe
b) Describe sum of subsets problem with an example. [7+8]

5.a) Show how Prim’s algorithm can be implemented using heap. What would be the time
ra
complexity of the algorithm?
b) Write the applications of Greedy method. [10+5]

6. Write the Greedy algorithm for sequencing unit time jobs with deadlines and profits.
ug
Trace the algorithm with suitable example. [15]

7.a) Use the function OBST to compute w(i, j), r(i, j), and c(i, j), 0 ≤ i < j ≤ 4, for the
-2
identifier set (a1,a2,a3,a4) = (cout, float, if, while) with p(1) = 1/20, p(2) = 1/5,
p(3) = 1/10, p(4) = 1/20, q(0) = 1/5, q(1) = 1/10, q(2) = 1/5, q(3) = 1/20, and
q(4) = 1/20. Using the r(i, j)’s construct the optimal binary search tree.
02
b) Discuss about chained matrix multiplication in dynamic programming. [10+5]

8. Explain the following:

a) LC branch and bound
2
b) Cook’s theorem. [8+7]

---ooOoo---
Code No: 135AF R16
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech III Year I Semester Examinations, February - 2022
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE, IT)
Time: 3 hours Max. Marks: 75
Answer any five questions
us
All questions carry equal marks
----
ed
1.a) Give Strassen’s matrix multiplication algorithm and derive the time complexity.
b) Illustrate with an example the working of quick sort. [7+8]

2.a) Explain various asymptotic notations for algorithm analysis.

pa
b) Derive the time complexity of binary search. [7+8]

3. Give the solution to the 8-queens problem using backtracking. [15]

pe
4. Explain the solution to the graph coloring problem using backtracking. [15]

5. Explain the Single source shortest path problem with an example. [15]
rf
6. What is the need for generating a spanning tree? Explain an algorithm for generating
spanning tree. [15]
eb
7. Discuss the time and space complexity of Dynamic Programming traveling sales person
algorithm. [15]
-2
8. Explain the LC branch and bound algorithm. [15]
2
jn
---ooOoo---
tu
Code No: 135AF R16
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech III Year I Semester Examinations, January/February - 2023
DESIGN AND ANALYSIS OF ALGORITHMS
JN
(Common to CSE, IT)
Time: 3 Hours Max. Marks: 75

Note: i) Question paper consists of Part A, Part B.

TU
ii) Part A is compulsory, which carries 25 marks. In Part A, Answer all questions.
iii) In Part B, Answer any one question from each unit. Each question carries 10 marks
and may have a, b as sub questions.
H
PART – A
(25 Marks)
U
1.a) Define Big ‘Oh’ notation. [2]
b) Compare Quick Sort and Merge Sort. [3]
se
c) What is an articulation point in a graph? Give an example. [2]
d) Construct the state space tree for 4-Queens problem with bounding function. [3]
e) Write an algorithm for simple Union operation. [2]
d
f) What is Minimum Spanning Tree? Give an example. [3]
g) Write the difference between the Dynamic programming and the Greedy method. [2]
h) What is mean by state space tree? Give an example. [3]
pa
i) Define cook’s theorem. [2]
j) Draw the relation of P, NP, NP-Hard and NP-Complete. [3]

PART – B
pe
(50 Marks)

2.a) Sort the following data using Quick Sort and illustrate each step with appropriate figure
rs
for each iteration. [ 20, 12, 35, 15, 11, 19, 35 ]
b) Write the Recurrence relation and derive the best case complexity for the Quick Sort.
[5+5]
20
OR
3.a) Describe asymptotic notations Big Oh (O), Omega (Ω) and Theta (Ɵ) notations and show
their behavior using graphical representation.
b) Give the asymptotic bounds for the equation f(n)=2n3-6n+30 and represent in terms of Ɵ
23
notation. [5+5]

4. Generate the state space tree and find the solutions for the subset sum for N=7, m=35,
w={5,7,10,12,15,18,20} using back tracking approach. [10]
OR
5. Write an algorithm for Graph Coloring problem and explain with an example. [10]
6. Explain the concept of minimum cost spanning tree? What are the different algorithms
exist for obtaining minimum cost spanning tree. Compute the minimum cost spanning
tree using Prim’s algorithm for the given graph. Draw the spanning tree generated at each
step. [10]
JN
TU
H
OR
7. Write greedy algorithm for knapsack problem. Find the solution for the following
U
Knapsack problem using greedy method.
(p1,p2,p3,p4)=(2,5,8,1), (w1,w2,w3,w4)=(10,15,6,9) and m=30. [10]
se
8.a) Write an algorithm for all pairs shortest path. Define its complexity.
b) Compute the shortest distance between each pair of nodes for the following graph using
d
all pair shortest path algorithm. [5+5]
pa
pe
OR
Use the function OBST to compute w(i, j), r(i, j) and c(i, j), 0≤i≤j≤4 for the identifier set
rs
9.
(a1,a2,a3,a4)=(do, if, int, while) with p(1:4)=(3,3,1,1) and q(0:4)=(2,3,1,1,1) using
r(i,j)’s construct optimal binary search tree. [10]
20
10. Generate the state space tree using FIFO Branch and Bound and find the shortest path
followed by the travelling salesperson instance defined by the cost matrix given below.
[10]
23
∞ 7 3 12 8
3 ∞ 6 14 9
5 8 ∞ 6 18
9 3 5 ∞ 11
[ 18 14 9 8 ∞ ]

OR
11. Explain circuit satisfiability problem with a circuit diagram. Show that circuit
satisfiability problem is NP- hard. [10]

---ooOoo---
 Code No: 135AF R16
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
U
B. Tech III Year I Semester Examinations, March - 2021
DESIGN AND ANALYSIS OF ALGORITHMS
SE
(Common to CSE, IT)
Time: 3 Hours Max. Marks: 75
Answer any five questions
All questions carry equal marks
D
---

1.a) Discuss Strassen’s matrix multiplication as well as classical O (n^2) one. Determine
when Strassen’s method outperforms the classical one.
0P9A
b) Define Time Complexity. Describe different notations used to represent these
complexities. [8+7]
-P0
2. List and explain the applications of backtracking. [15]

3. Apply the greedy method to solve Knapsack problem for given instance.
3E-R
Where n=3, m=20, (p1,p2,p3)=(25,24,15), and weight (w1,w2,w3)=(18,15,10). [15]
20
4. What is travelling salesman problem? Explain how it can be solved using Branch and
Bound method. Show the steps and solution by taking any one example containing
atleast 5 cities and 10 ways to travel between them. [15]
M2
5.a) Using branch and bound technique explain the 0/1 knapsack problem.
A1 R
b) Give a note on FIFO branch and bound solution. [7+8]

6. Explain the Bi-connected components in detail. [15]

ACM
7.a) Explain binary search and find its time complexity.
b) Write an algorithm for finding maximum element of an array; perform best, worst and
average case complexity with appropriate order notations. [7+8]
H
8. State and prove the Cook’s theorem. [15]
-2
---ooOoo---
02
1
 Code No: 135AF
R16
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech III Year I Semester Examinations, May/June - 2019
us
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE, IT)
Time: 3 hours Max. Marks: 75
ed
Note: This question paper contains two parts A and B.
Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B
consists of 5 Units. Answer any one full question from each unit. Each question carries
10 marks and may have a, b, c as sub questions.
pa
PART - A
(25 Marks)
pe
1.a) In what way a time complexity differs from space complexity. [2]
b) Give the general plan of divide and conquer algorithms. . [3]
c) Write an algorithm for collapsing find. [2]
r2
d) Define Backtracking? List the applications of Backtracking [3]
e) What is the importance of knapsack algorithm in our daily life? [2]
f) Write Control Abstraction of Greedy method. [3]
5-
g) What you mean by dynamic programming. [2]
h) Define optimal binary search tree with an example. [3]
i) State the difference between FIFO and LC Branch and Bound algorithms. [2]
05
j) Write the Control Abstraction of Least – Cost Branch and Bound. [3]

PART - B
-2
(50 Marks)

2.a) What are the different mathematical notations used for algorithm analysis.
0
b) Write Divide – And – Conquer recursive Quick sort algorithm and analyze the
algorithm for average time complexity. [10]
19
OR
3. Write Randomized algorithm of Quicksort. [10]

4. Write an algorithm to determine the Hamiltonian cycle in a given graph using

PM
backtracking. [10]
OR
5. Explain the AND/OR graph problem with an example. [10]

6.a) Explain the Knapsack problem with an example.

b) Write a greedy algorithm for sequencing unit time jobs with deadlines and profits.
[10]
OR
7. State the Job – Sequencing with deadlines problem. Find an optimal sequence to the
n = 5 Jobs where profits (P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and deadlines
(d1, d2, d3, d4, d5) =(2, 2, 1, 3, 3). [10]
 8. Draw an Optimal Binary Search Tree for n=4 identifiers (a1,a2,a3,a4) = ( do, if, read,
while) P(1:4)=(3,3,1,1) and Q(0:4)=(2,3,1,1,1). [10]
OR
us
9. Explain how Matrix – chain Multiplication problem can be solved using dynamic
programming with suitable example. [10]
ed
10. Solve the Travelling Salesman problem using branch and bound algorithms. [10]
OR
11. Explain the FIFO BB 0/1 Knapsack problem procedure with the knapsack instance for
n=4, m=15,(p1,p2,p3,p4)=(10,10,12,18), (w1,w2,w3,w4) =(2, 4, 6, 9). Draw the portion
of the state space tree and find optimal solution. [10]
pa
pe
---ooOoo---
r2
5-
05
-2
0 19
PM
 Code No: 135AF
R16
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech III Year I Semester Examinations, November/December - 2018
us
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE, IT)
Time: 3 hours Max. Marks: 75
ed
Note: This question paper contains two parts A and B.
Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B
consists of 5 Units. Answer any one full question from each unit. Each question carries
10 marks and may have a, b, c as sub questions.
pa
PART - A
(25 Marks)
pe
1.a) Write an algorithm to find the number of digits in the binary representation of a
positive decimal integer. [2]
How can we measure an algorithm’s running time?
r2
b) [3]
c) What is a set? List the operations that can be performed on it. [2]
d) Give brief note on graph coloring. [3]
e) State the Job – Sequencing Deadline Problem. [2]
7-
f) Find an optimal solution to the knapsack instance n=4 objects and the capacity of
knapsack m=15, profits (10, 5, 7, 11) and weight are (3, 4, 3, 5). [3]
g) What is Travelling Sales Man Problem? [2]
11
h) Give the statement of Reliability design problem. [3]
i) State the methodology of Branch and Bound. [2]
j) Define Bounding Function? Give the statement of 0/1 Knapsack FIFO BB. [3]
-2
PART - B
(50 Marks)
0
2.a) Explain Recursive Binary search algorithm with suitable examples.
18
b) Distinguish between Merge sort and quick sort. [5+5]
OR
3.a) What is stable sorting method? Is Merge sort a stable sorting method? Justify your
answer.
AM
b) Explain partition exchange sort algorithm and trace this algorithm for n =8 elements:
24,12, 35, 23,45,34,20,48. [5+5]

4. Write and explain the algorithm of Bi connected components with an example. [10]
OR
5. Give the solution to the 8-queens problem using backtracking. [10]

6. What is Minimum cost spanning tree? Explain an algorithm for generating minimum
cost Spanning tree and list some applications of it. [10]
OR
7.a) Explain the greedy technique for solving the Job Sequencing problem.
b) Write with an example of Prim’s algorithm. [5+5]
 8.a) Discuss the time and space complexity of Dynamic Programming traveling sales person
algorithm.
b) Write an algorithm of matrix chain multiplication. [5+5]
us
OR
9. With the help of suitable example explain the all pairs shortest path problem. [10]
ed
10.a) Give the 0/1 Knapsack LCBB algorithm.
b) Differentiate between deterministic and non deterministic algorithm. [5+5]
OR
11. Draw the portion of state space tree generated by LCBB for the 0/1 Knapsack instance:
n = 5, (p1,p2,…,p5) = (10,15,6,8,4), (w1,w2,..,w5) = (4,6,3,4,2) and m=12. And also
pa
find an optimal solution of the same. [10]
pe
---ooOoo---
r2
7-
11
-2
0 18
AM
 R16
H
Code No: 135AF
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech III Year I Semester Examinations, October - 2020
U
DESIGN AND ANALYSIS OF ALGORITHMS
(Common to CSE, IT)
se
Time: 2 hours Max. Marks: 75

Answer any five questions

d
All questions carry equal marks
---
Pa
1.a) Explain the general method of divide and conquer with an example.
b) Write an algorithm for stressan’s matrix multiplication and analyze the complexity of
your algorithm. [7+8]
pe
2.a) List the disjoint set operations and explain with examples.
b) Explain GRAPH coloring problem with example. Analyze the running time for that
problem/algorithm. [7+8]
rB
3. Differentiate between prim’s algorithm and krushkars algorithm for finding the
minimum cost spanning tree. [15]
TE
4.a) Write an algorithm of all pairs shortest path problem.
b) Solve the following 0/1 Knapsack problem using dynamic programming
P= (11, 21, 31, 33), W= (2, 12, 23, 15), C=42, n=4. [7+8]
C
5.a) Compare NP Hard and NP Complete.
b) Explain about 0/1 Knapsack Problem using branch and bound with example. [7+8]
H
6. Explain the merge sort algorithm with an example. Design an algorithm for merge sort.
[15]
-1
7.a) Explain the major drawbacks of backtracking method with example.
3-
b) Write an algorithm for sum of subsets problem. [8+7]

8.a) Write an algorithm for Knapsack problem using Greedy method.

10
b) Find the optimal solution by using primis minimum cost spanning of the following
graph. [7+8]
- 20
2

---ooOoo---
Code No: 135AF R16
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
B. Tech III Year I Semester Examinations, September - 2021
DESIGN AND ANALYSIS OF ALGORITHMS
U
(Common to CSE, IT)
Time: 3 hours Max. Marks: 75
SE
Answer any five questions
All questions carry equal marks
----
D
1. Design an algorithm to sort the given list of elements using Quick Sort incorporating
divide and conquer technique. Sort the following list using the same and compute its
best case time efficiency: 4, 2, 0, 8, 7, 1, 3, 6. [15]
PA
2. Consider the following recurrence
T(n)=3T(n/3)+ n
Obtain asymptotic bound using substitution method. [15]
PE
3. Using disjoint-sets find the connected components in the undirected graph G = (V, E),
where the vertices V = {a, b, c, d, e, f, g, h, i, j} and edges E = {(a, c), (a ,b), (e, f),
(h, i), (e, g), (a, d), (e, d) (b, d), (c, a), (h, j)}. The edges are processed in the order
given. List the vertices in each connected component after each step. [15]
R
4. Find a solution to the 8-Queens problem using backtracking strategy. Draw the solution
SS
space using necessary bounding function. [15]

5. Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge
weighted directed graph with vertex P as the source (figure 1). In what order do the
EP
nodes get included into the set of vertices for which the shortest path distances are
finalized? [15]
-2
02
1

Figure 1

6. A thief enters a house for robbing it. He can carry a maximal weight of 60 kg into his
bag. There are 5 items in the house with the following weights and values. What items
should thief take if he can even take the fraction of any item with him? (w1, w2, w3,
w4, w5) = (5, 10, 15, 22, 25), (b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90). [15]
7. Given a set of cities and distance between every pair of cities, the problem is to find the
shortest possible route that visits every city exactly once and returns to the starting
point. (figure 2) [15]
U
SE
D
Figure 2
PA
8. Given a set of 4 items, each with weight {2,2,4,5} and benefit {3,7,2,9}, Using LC
branch and Bound determine the items to include in the knapsack so that the total
weight is less than or equal to a given weight limit and the total benefit is maximized.
PE
The weight limit for this knapsack is 10? [15]
R
---ooOoo---
SS
EP
-2
02
1