Design and Analysis of Algorithms - End Semester Examination - 2023

The fractional Knapsack problem can be solved by using

1. Greedy method
2. Divided and conquer method
3. Dynamic programming
4. None of these

BFS on a graph \( G=(V,E) \) has running time

1. \( O(|V|+|E|) \)
2. \( O(|V|) \)
3. \( O(|E|) \)
4. None of the above

The minimum number of colors needed to color a graph having \( n>3 \) vertices and 2 edges is

1. 2
2. 3
3. 4
4. 1

Complexity the recurrence relation \( T(n)=8T(\frac{n}{2})+n^2 \) is

1. \( O(n) \)
2. \( O(n^2) \)
3. \( O(\log_2 n) \)
4. \( O(n^3) \)

Travelling salesman problem belongs to

1. P class
2. NP class
3. NP- hard
4. NP- complete class

Kruskal's algorithm uses ___ and Prism' algorithm uses ___ in determining the MST

1. Edges, vertex
2. Vertex, edges
3. Edges, edges
4. Vertex, vertex

Level order traversal of a rooted tree can be done by starting from root and performing

1. Depth first search
2. Breadth first search
3. Pre-order traversal
4. In-order traversal

An algorithm is made up of two independent time complexities \( f(n) \) and \( g(n) \). Then the complexities of the algorithm is in order of

1. \( f(n) \times g(n) \)
2. \( \max(f(n), g(n)) \)
3. \( \min(f(n), g(n)) \)
4. \( f(n)+g(n) \)

Which of the following standard algorithms is not a greedy algorithm?

1. Dijkstra's shortest path algorithm
2. Kruskal algorithm
3. Bellman ford shortest path algorithm
4. Prim's algorithm

The node removal of which makes a graph disconnected is called

1. Pendant vertex
2. Bridge
3. Articulation point
4. Coloured vertex

Write the algorithm for quick-sort and find its complexity.

Discuss the average, worst, best time complexity of the algorithm. Give suitable examples.

Construct the Huffman coding tree for the text of characters with given frequencies: T:43, I:38, V:16, K:8, L:56, E:12, O:41, Z:13, P:22, R:6.

State the general Knapsack problem. Write a greedy algorithm for this problem and derive its time complexity.

State master's theorem and find the time complexity for the following recurrence: \( T(n) = 2T(n^{1/2}) + \log n \)

What is negative weight-cycle? Write Bellman-Ford algorithm to find single source shortest distance of a directed graph.

Find the minimum number of operations required for the following matrix chain multiplication using dynamic programming: \( A(10 \times 20) * B(20 \times 50) * C(50 \times 1) * D(1 \times 100) \)

Write Knuth-Morris-Pratt algorithm for string matching problem.

Write an algorithm to find a minimum spanning tree (MST) for an undirected graph. Estimate the time complexity of your algorithm.

Using greedy strategy. Schedule the following jobs within deadline so as to maximize the profit. Deadline and profits are mentioned as follow:
Job i: 1, 2, 3, 4
Deadline d: 3, 2, 3, 1
Profit g: 9, 7, 7, 2

Write an algorithm for n-queen's problem find its time-complexity and explain the algorithm using an example.

Solve the single source shortest path problem for the following graph considering '1' as the source vertex using Dijkstra's algorithm.

Define the classes P and NP.

Discuss what you mean by polynomial reduction.

Discuss diagrammatically the relation among P class, NP class, NP hard and NP complete.

Describe Clique Decision Problem (CDP).

Explain the max-flow min-cut theorem with an example.