Design & Analysis of Algorithms

The fractional Knapsack problem can be solved by using:

• (i) Greedy method
• (ii) Divide and conquer method
• (iii) Dynamic programming
• (iv) None of these

Time complexity of Kadane's Algorithm is:

• (i) $O(n)$
• (ii) $O(n^2)$
• (iii) $O(n \log n)$
• (iv) $O(n(\log n)^2)$

An all-pairs shortest-paths problem is efficiently solved using:

• (i) Dijkstra's algorithm
• (ii) Bellman-Ford algorithm
• (iii) Kruskal algorithm
• (iv) Floyd-Warshall algorithm

Approach of dynamic programming is similar to:

• (i) parsing
• (ii) hash table
• (iii) divide and conquer algorithm
• (iv) greedy algorithm

Which of the following is true about Huffman Coding?

• (i) Huffman coding may become lossy in some cases.
• (ii) Huffman codes may not be optimal lossless codes in some cases.
• (iii) In Huffman coding, no code is prefix of any other code.
• (iv) All of the above

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

• (i) Dijkstra's shortest path algorithm
• (ii) Kruskal algorithm
• (iii) Bellman ford shortest path algorithm
• (iv) Prim's algorithm

Kruskal's Algorithm for finding the Minimum Spanning Tree of a graph is a kind of a?

• (i) DP Problem
• (ii) Greedy Algorithm
• (iii) Adhoc Problem
• (iv) None of the above

Construct the Huffman coding tree for the text of characters with given frequencies.

Character	T	I	V	K	L	E	O	Z	P	R
Frequency	43	38	16	8	56	12	41	13	22	6

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

What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider the graph $G=(V, E)$ given below. Find the minimum spanning tree by Prim's algorithms.

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)$$

State Huffman Tree. Explain with examples.

Write Knuth-Morris-Pratt (KMP) algorithm for string matching problem.

Compare the various programming paradigms such as divide-and-conquer, dynamic programming and greedy approach.

Find the optimal way to multiply the following matrices to perform the fewest multiplications:

Matrix	Dimension
$A_1$	$5 \times 11$
$A_2$	$11 \times 4$
$A_3$	$4 \times 15$
$A_4$	$15 \times 23$

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

How 8-Queen's problem can be solved using back tracking and explain with an example.

Using greedy strategy, schedule the following jobs within deadline so as to maximize the profit.

Job $i$	1	2	3	4
Deadline $d$	3	2	3	1
Profit $g$	9	7	7	2

Distinguish greedy method and dynamic programming

What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider the graph $G = (V, E)$ given below. Find the minimum spanning tree by Prim's algorithms.

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

Construct minimum cost spanning tree using Kruskal's algorithm

Define spanning tree and minimum spanning tree

What is activity selection problem? Suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, prove that it yields an optimal solution.

Explain Knapsack Problem.

Write short notes on: Kruskal algorithms.

Write short notes on: Travelling Salesman Problem

Write short notes on: Divide-and-Conquer vs Dynamic programming

Write short notes on: Divide-N-Conquer vs Dynamic Programming