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

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 / recursive method, including algorithm, trace/example, and worst-case complexity.

Write the merge sort and merge algorithms and prove/derive that the running time is $\theta(n \log n)$, illustrating on an example array.

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

Explain the steps involved in designing and analyzing algorithms and the criteria used to evaluate algorithm efficiency.

Write a recursive algorithm for computing the $n^{th}$ Fibonacci number.

Estimate minimum sorting time for a different input size using Quick Sort time complexity.

Find the time complexity of the recurrence relation $T(n)= n + T(n/10) + T(7n/5)$.

Analyze the time complexity of Strassen's algorithm compared to conventional matrix multiplication.

Given $T(n) = 7T(n/2) + n^2$ and $T'(n) = aT'(n/4) + n^2$, find the largest integer $a$ such that $A'$ is asymptotically faster than $A$.

Explain properties of Binomial Heap and give algorithms for uniting two Binomial Heaps and finding the minimum key.

Define stable sorting algorithm and identify which common sorting algorithms are stable vs unstable with explanation.

Solve the fractional knapsack problem with knapsack capacity $=60$ kg for the given 7 items with weights and values using the greedy approach.

What is Greedy algorithm? How greedy methods can be used to solve the optimization problem?

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

Define minimum cost spanning tree and explain Kruskal's algorithm with its algorithmic steps.

Suppose character a, b, c, d, e, f has probabilities 0.07, 0.09, 0.12, 0.22, 0.23, 0.27 respectively. Find an optional Huffman code and draw the Huffman tree. What is the average code length?

Prove uniqueness of MST with distinct edge weights with example, and discuss Kruskal's MST algorithm in detail.

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.

Compute the optimal solution for job sequencing with deadlines using greedy method. $N = 4$, profits $(p_1, p_2, p_3, p_4) = (100, 10, 15, 27)$, deadlines $(d_1, d_2, d_3, d_4) = (2, 1, 2, 1)$.

Apply Kruskal's algorithm to a given graph to find the minimum spanning tree and explain the steps.

Use Prim's algorithm to determine the minimum cost spanning tree of a given graph.

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

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

Explain the reliability design problem using the dynamic programming approach and steps to obtain an optimal solution with example.

Explain the dynamic programming algorithm for the 0/1 knapsack problem.

Solve a given 0/1 knapsack instance using dynamic programming.

Explain the significance of overlapping sub-problems in dynamic programming.

Design a three stage reliability system with device types $d_1, d_2$ and $d_3$. The costs are $$30, $15$ and $$20$ respectively. The cost of the system is to be no more than $$105$. The reliability of each device is 0.9, 0.8 and 0.5 respectively.

Introduce the Floyd-Warshall algorithm for all-pairs shortest paths.

On which type of problem we apply multi stage graph technique? Explain with example.

Explain dynamic programming and compute transitive closure of a given graph.

Apply Floyd's algorithm to find all-pairs shortest paths for a given graph.

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/design the backtracking algorithm to solve it.

Explain the concept of lower bound theory and describe the fundamentals of parallel algorithms.

Describe the 8-queens problem and explain how backtracking finds a solution, with algorithm.

Explain the Traveling Salesperson Problem and give the branch-and-bound algorithm to find an optimal solution.

Explain backtracking and solve the subset sum problem using backtracking.

What is a decision tree and how is it used to illustrate lower bound theory with an example such as sorting?

Explain the concept of backtracking in algorithmic design.

Identify the Hamiltonian cycle in a given graph.

Explain what the Hamiltonian Cycle problem is and how it is solved using backtracking.

Explain the backtracking concept and construct the state-space tree for solving the N-queens (4-queens) problem.

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

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

Construct a BST by inserting given keys and perform inorder, preorder, and postorder traversals.

Explain B-Tree, its properties, and deletion cases with example.

Construct a binary tree from given preorder and inorder traversals and find its postorder traversal.

Discuss the operations performed on the binary search tree for the following data : 20, 49, 41, 93, 69, 90, 76, 62, 81, 75, 10, 79, 87, 38 and delete 41 and 76.

Differentiate between BFS and DFS.

What is a B-tree and what are its advantages over other tree structures?

Explain the difference between P, NP and NP-complete problems

Apply DFS-based topological sorting to the given graph.

Write short notes on any two of the following.

When is it appropriate to sacrifice code readability for the sake of optimization, and when is it not? Explain.

Explain any two of: AVL Tree, Hamiltonian Problem, M-Coloring, NP-Complete Problem with examples