CSIT-403 – Analysis & Design of Algorithm (ADA)

With the help of a flow chart, explain the various steps of algorithm design and analysis process.

What are the significance of various asymptotic notations? Express the following assertions using three asymptotic notations with proof from its definition

i) $n(n-1)/2$

ii) $6*2^n + n^2$

iii) $100n + 7$

Write an algorithm to sort n numbers using Quick Sort. Trace the algorithm to sort the following list in an ascending order: 7 65 70 75 80 85 60 55 50

Discuss the general Divide and Conquer technique with control abstraction and recurrence relation.

Discuss how to find maximum and minimum element in an array recursively? Trace the same for the following data set 65, 70, 75, 80, 85, 60, 55, 50. Also derive the worst care complexity.

Briefly explain the Strassen's matrix multiplication. Apply it to multiply the following matrices. Explain how this method is better than direct multiplication method.

$\begin{pmatrix} 4 & 3 \\ 2 & 1 \end{pmatrix} \text{ and } \begin{pmatrix} 2 & 5 \\ 1 & 6 \end{pmatrix}$

Recall the concept of greedy techniques. Find the optimal solution to the Knapsack instance $n = 7, m = 15$. $(P_1, P_2, \dots, P_7) = (10, 5, 15, 7, 6, 18, 3)$ $(W_1, W_2, \dots, W_7) = (2, 3, 5, 7, 1, 4, 1)$

Using the Prim's Algorithm, determine the minimum cost spanning tree of the graph of figure: alt=''

Explain the dynamic programming. Generate transitive closure of the graph given in the figure give below: alt=''

Using Floyd's algorithm, find all pairs of shortest path for the graph in the figure given below: alt=''

Explain Backtracking Concept. Construct the state-space tree for solving 4-Queen's problem. using backtracking.

What is Branch and Bound algorithm? Write the steps and apply nearest neighbour approximation algorithm on the Travelling Salesperson Problem with the starting vertex a, and calculate the accuracy ratio of approximation. alt=''

What is a Decision Tree? Give a decision tree for 3 elements selection sort for arranging the items in ascending order and estimate its lower bound.

Apply DFS algorithm to solve the topological sorting problem for the graph in the figure given below: alt=''

AVL Tree

Hamiltonian Problem

M - Coloring

NP-Complete Problem