Analysis and Design of Algorithm (IT-403) - Important Questions

Write the merge sort and merge algorithms and derive that the running time is Theta(n log n), illustrating on an example array.

Explain the general divide and conquer technique, its key steps / control abstraction and recurrence relation.

Write the Quick Sort / partition algorithm and analyze its efficiency including best-case and worst-case time complexity, with application to an example list.

Give the divide-and-conquer recursive binary search algorithm, generate its recurrence relation, and analyze its time complexity.

Find the smallest/minimum and largest/maximum elements in an array of n numbers using divide and conquer method, including algorithm, trace with example, and worst-case complexity.

Explain the Quick Sort algorithm and trace it to sort a given list in ascending order.

Explain the heap sort algorithm step by step with suitable example and analyze its time complexity.

Solve the fractional knapsack instance with n=7, m=15, profits (10,5,15,7,6,18,3) and weights (2,3,5,7,1,4,1) using the greedy method.

Explain the job sequencing with deadlines problem and demonstrate how the greedy algorithm schedules jobs to maximize profit with an example.

Solve a 0/1 Knapsack instance using dynamic programming to find the optimal solution.

Apply Floyd-Warshall / Floyd's algorithm to compute all-pairs shortest-path distances for a given weighted graph / cost matrix.

Explain the 8-queens / N-queens problem and solve it using backtracking, including algorithm and state-space tree.

Solve the Travelling Salesman Problem using least-cost branch and bound, drawing the state space tree and showing reduced cost matrices.

Describe the graph coloring (m-coloring) problem and explain the backtracking algorithm to solve it.

Demonstrate insertion of given keys into an empty B-tree and deletion of keys from the resulting B-tree.

Explain the P, NP, NP-complete and NP-hard complexity classes, their relationships and differences, with an example of each.