Analysis & Design of Algorithms (AL-402) - Important Questions

Apply quick sort (partition exchange sort) on the following array and show all partitioning steps: 65, 70, 75, 80, 85, 60, 55, 50, 45.

Solve the recurrence T(n) = 2T(n/2) + n with T(1) = O(1) to obtain the asymptotic bound using recursion tree / Master method.

Define time complexity and describe the different asymptotic notations - Big-Oh, Omega and Theta - used to represent it with examples.

Write the algorithm for Strassen's matrix multiplication and analyze its complexity.

Write Dijkstra's algorithm for the single source shortest path problem and illustrate it with an example.

Apply Kruskal's algorithm to a given weighted graph to construct the minimum cost spanning tree, illustrating with an example.

Solve a fractional knapsack instance using the greedy method by profit-to-weight ratio for given n, profits, weights and capacity M.

Describe the job sequencing with deadlines problem and find the optimal sequence for given profits and deadlines.

Explain Floyd-Warshall algorithm with a suitable example.

Solve a given 0/1 Knapsack instance for maximum profit using dynamic programming.

Explain the multistage graph problem and its dynamic programming solution, giving the algorithm and its computing time.

Obtain any two solutions to the 4-Queens problem and establish the relationship between them.

Solve a travelling salesperson problem instance using (least cost) branch and bound.

Explain the Hamiltonian cycle problem and how to solve it using backtracking, including the algorithm with an example.

Explain the P, NP, NP-Hard and NP-Complete classes, their relation, with examples.

Explain approximation algorithms for Vertex Cover with an example.