Code No.

: 22CSC14N
CHAITANYA BHARATHI INSTITUTE OF TECHNOLOGY (Autonomous)
B.E. / B.Tech (CSE /CSM / AI&ML) V Sem (Main) Examination December 2024
Design and Analysis of Algorithms
Time: 3 Hours Max Marks: 60
Note: Answer ALL questions from Part-A at one place in the same order and Part–B
(Internal Choice)
Part - A
(5Q X 2M = 10 Marks)
M CO BT
1 Distinguish between Algorithm and Pseudocode. (2) 1 4
2 Discuss the terms feasible solution, optimal solution and objective functions (2) 2 2
with example
3 Describe the time complexity of the graph coloring problem using back (2) 3 2
tracking.
4 Define bi-connected components. (2) 2 2
5 Distinguish between NP hard and Np complete. (2) 6 4

Part - B
(5Q X 10M = 50 Marks)
M CO BT
6 (a) Explain the general method of divide and conquer approach. (5) 2 2
(b) Describe the Pseudo code conventions for specifying algorithms of (5) 2 2
recursive and an iterative algorithm to compute n!
(OR)
7 2
(a) For T (n)=7T(n/2)+18n Solve the recurrence relation and find the time (5) 1 2
complexity.
(b) Estimate the time complexity using f(n) and g(n) functions in (5) 1 2
asymptotic notations.

8 (a) Evaluate the effectiveness of the greedy approach in solving the 0/1 (5) 4 3
knapsack problem. Compare its outcome to the optimal solution
obtained using dynamic programming with an example
(b) Apply dynamic programming to find the optimal order of multiplying 3 (5) 3 3
matrices A 5X25, B25X10, C10X15.
(OR)
9 (a) Develop algorithm to insert more number of jobs in feasible solution set (3) 3 2
J={} to maximize the profit using greedy method?
(b) Apply dynamic programming to obtain optimal binary search tree for (7) 3 3
the identifier set (a1, a2, a3, a4)=(cin, for, int, while) with (p1, p2, p3,
p4)=(1, 4, 2, 1), (q0, q1, q2, q3, q4)=(4, 2, 4, 1, 1) and also write
algorithm for its construction.

10 (a) What is a Hamiltonian Cycle? Explain how to find Hamiltonian path (5) 3 2
and cycle using backtracking algorithm.

Page 1 of 2
Code No.: 22CSC14N

(b) Draw the portion of the state space tree generated by FIFO-Branch and (5) 3 3
Bound for the given knapsack problem m=5
(p1..p5)=(w1..w5)=(3,6,5,7,9) and m=15.
(OR)
11 (a) Find the chromatic number for the given graph with undirected (5) 3 3
connections v1→v2, v1→v3, v1→v4,v2→v3, v2→v4, v2→v5,v3→v4,
v4→v5 using backtracking technique.
(b) Obtain reduced cost matrix for travelling sales person problem. (5) 3 3
Consider the instance define by the cost matrix:
1 2 3 4 5
1 ∞ 5 1 10 6
2 1 ∞ 4 12 7
3 3 6 ∞ 4 16
4 7 1 3 ∞ 9
5 16 12 7 5 ∞

12 Find all the bi-connected components of the following undirected graph (10) 3 3
(A-B), (A-C), (B-C), (B-D), (C-D), (D-E), (E-F) using Depth-First
Search (DFS). Identify any articulation points present in the graph.
(OR)
13 (a) Describe the Johnson’s algorithm in detail. (5) 3 2
(b) Develop Dijkstra’s Algorithm and analyses its time complexity. (5) 5 3

14 (a) What are the classes P and NP in computational complexity theory, and (5) 6 3
why is the P vs NP question significant in computer science?
(b) Why is the Clique Problem NP-complete, and how can it be reduced (5) 6 L3
from another NP-complete problem?
(OR)
15 (a) What is the difference between NP-hard and NP-complete problems? (5) 6 4
Can a problem be NP-hard but not NP-complete? Provide examples of
each.
(b) Explain the Subset Sum Problem. Show that the Subset Sum Problem is (5) 6 2
NP-complete by reducing it from the 3-CNF problem.

*****

Page 2 of 2