Design and Analysis of Algorithms

Which of the following sorting algorithms has the best time complexity in the average case?
(i) Bubble sort
(ii) Insertion sort
(iii) Quick sort
(iv) Selection sort

A FIFO Branch-and-Bound strategy is typically implemented using which data structure?

(i) Stack
(ii) Queue
(iii) Priority Queue
(iv) Array

Which strategy solves problems by solving subproblems and combining their solutions?
(i) Brute Force
(ii) Greedy
(iii) Dynamic Programming
(iv) Backtracking

The 0/1 Knapsack problem is traditionally solved using which approach to ensure an optimal solution?

(i) Greedy Method
(ii) Dynamic Programming
(iii) Brute-Force only
(iv) Linear Search

What is the primary advantage of dynamic programming over brute-force algorithms?
(i) Dynamic programming guarantees finding the global optimum.
(ii) Dynamic programming reduces the time complexity by avoiding redundant computations.
(iii) Dynamic programming simplifies the problem by dividing it into smaller subproblems.
(iv) Dynamic programming is more intuitive to implement.

In which algorithmic strategy are problems systematically divided into smaller subproblems until the solution to the original problem is found?
(i) Brute-force
(ii) Greedy
(iii) Dynamic programming
(iv) Backtracking

Kruskal algorithm is a
(i) Divide & conquer algorithm
(ii) Branch and bound algorithm
(iii) Greedy algorithm
(iv) Dynamic programming

Write the Knuth-Morris-Pratt algorithm for pattern matching. Apply the KMP algorithm for the pattern $p = "ababaca"$ and string $s = "bacbabababacaab"$. Show every step.

Write the algorithm for quick sort. Find the best-case, worst-case and average-case time complexities of this algorithm.

Write the step-by-step process of Quick Sort using an example. Write the advantages and disadvantages of Quick Sort compared to other sorting algorithms, such as Merge Sort and Bubble Sort.

Answer the following:
(i) Compare dynamic programming and greedy algorithms in terms of their problem-solving approaches, solution spaces, and efficiency.
(ii) Discuss scenarios where dynamic programming is necessary because greedy strategies fail. Use suitable problem examples to support your explanation.
(iii) Explain how overlapping subproblems and optimal substructure are utilized in dynamic programming.

The 0/1 Knapsack Problem is a classical combinatorial optimization problem. Explain how this problem can be solved using:
(i) Brute-force method
(ii) Greedy method
(iii) Dynamic Programming
(iv) Branch-and-Bound
For each approach, explain the algorithm, time complexity, and limitations. Highlight why the greedy method may not always yield the optimal solution.

Find an optimal solution to the knapsack instance $n=4$ objects and the capacity of knapsack $m=15$, profits are $(10, 5, 7, 11)$ and weights are $(3, 4, 3, 5)$.

State the graph coloring problem and write the algorithm. Apply backtracking technique to solve the 3-colouring problem for the following graph.

Consider a TSP with 4 cities A, B, C, D and the following distance matrix:

	A	B	C	D
A	0	10	15	20
B	10	0	35	25
C	15	35	0	30
D	20	25	30	0

Answer the following:
(i) Use the branch-and-bound algorithm to find the shortest possible route that visits all cities exactly once and returns to the starting city.
(ii) Show the branching steps and calculate lower bounds for each partial solution.
(iii) Identify how the bounding helps prune the search tree.

You are a thief planning to rob a jewelry store. The store contains 7 items, each with a profit $P$ and weight $W$ as follows:

Object	1	2	3	4	5	6	7
Profit (P)	5	10	15	7	8	9	4
Weight (W)	1	3	5	4	1	3	2

You have a knapsack with a weight capacity of 15. Apply the step-by-step greedy approach to obtain the maximum profit.

Differentiate between divide & conquer, greedy method and dynamic programming with suitable examples.

Apply the backtracking approach and find the Hamiltonian cycle for the graph given in the form of matrix. Show all the steps to find the cycle.

	A	B	C	D	E	F
A	0	1	1	0	0	1
B	1	0	1	1	0	0
C	1	1	0	0	1	0
D	0	1	0	0	1	0
E	0	0	1	1	0	1
F	1	0	1	0	1	0

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

Differentiate between backtracking and branch & bound.

Explain solution pseudocode for N-Queens problem using backtracking.

Find Huffman codes for the text of characters with given frequencies:

Characters	T	I	V	K	L	E	O	Z	P	R
Frequencies	43	38	16	8	50	12	56	13	22	7

We are given the sequence $\{4, 10, 3, 12, 20, \text{and } 7\}$. The matrices have size $4 \times 10, 10 \times 3, 3 \times 12, 12 \times 20, 20 \times 7$. Find the most efficient way to multiply these matrices together using dynamic programming. The efficient way is the one that involves the least number of multiplications. Write all the steps with time complexity.

Find the optimal solution using greedy criteria for a knapsack having capacity 100 kg for the following list of items having values and weights as shown in the table.

Item	Value	Weight
$I_1$	10	15
$I_2$	20	25
$I_3$	30	35
$I_4$	40	45
$I_5$	50	55

Explain the Brute Force method of algorithm design with suitable examples.

Write a short note on:

Dynamic Programming