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

Apply / trace quick sort (partition exchange sort) on a given array, showing partitioning steps

Apply / trace quicksort (partition exchange sort) on the array $15, 31, 1, 9, 80, 12, 14, 7, 24$.

Write an algorithm to search an element using binary search method and analyse its best, average and worst cases.

Solve the recurrence $T(n) = 2T(n/2) + n$ with $T(1)=O(1)$ to obtain asymptotic bound.

Find the Big-O notation for the function $f(n) = 1000n^2 + 100n + 6$.

Define time complexity and describe the different asymptotic notations used to represent it.

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

Solve the recurrence $T(n) = 2T(n/2) + n$ with $T(1)=O(1)$

Solve the recurrence $T(n) = 2T(n/2) + n \log n$ using Master's theorem

Find the number of comparisons made by sequential search in the best and worst cases.

Write an algorithm for implementing binary search.

Explain the various criteria used for performance analysis of an algorithm.

Write Dijkstra's algorithm for the single source shortest path problem and illustrate/apply it.

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

Define/write Kruskal's algorithm for minimum spanning tree and explain its steps and time complexity

Apply Kruskal's algorithm to construct the minimum cost spanning tree / MST for a given graph with example.

Solve a fractional knapsack instance using the greedy method by profit-to-weight ratio.

Define Greedy Algorithm, give its pseudocode, and apply it to graph vertex colouring.

Solve fractional knapsack instance using greedy method (profit/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.

List various problems solvable using the greedy algorithm approach.

Explain fractional Knapsack problem in detail

How the Optimal Merge Pattern algorithm works? Explain with a suitable example.

Discuss the importance of proving both the greedy choice property and the optimal substructure property for establishing the correctness of a greedy algorithm.

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

Explain Floyd-Warshall algorithm with a suitable example.

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

Explain Floyd-Warshall algorithm with a suitable example/graph.

Compare dynamic programming, greedy method, and divide and conquer, including commonalities and main differences.

Explain the 0-1 Knapsack problem and discuss its solution.

Design a three-stage reliability system with device types $D_1, D_2, D_3$ with given costs and reliabilities subject to a maximum total cost.

Explain the 0/1 Knapsack problem and discuss its solution, including whether the greedy method is effective.

Compare dynamic programming with divide and conquer (and greedy method), explaining commonalities and main differences.

Explain how dynamic programming can be used to solve reliability design problems.

Write short notes on reliability design (among choice of topics including greedy correctness, parallel algorithms, graph coloring).

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

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

What is a Hamiltonian cycle? Explain how to find it using backtracking with an example.

Describe the lower bound theory and its use in solving algebraic problems.

Explain the Travelling Salesman Problem in detail.

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

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

Solve an instance of the Knapsack problem using the branch and bound technique.

Describe graph coloring problem and write an algorithm for m-coloring problem.

Explain the 4-Queens problem using the backtracking algorithm.

Explain the matrix reduction method for solving TSP using branch and bound.

Find a solution to the 8-Queens problem using backtracking and draw the solution space with bounding function.

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

Explain the difference between P and NP.

Explain approximation algorithms for Vertex Cover.

Compare and contrast NP-Hard and NP-Complete classes.

Explain the NP-Complete class with example.

Determine which of the given numbers of nodes could form a Full Binary Tree.

Write short notes on any two of the following.

Explain the purpose of design and complexity of parallel algorithms in detail.

Write short note differentiating between Prim's algorithm and Kruskal's algorithm

Show the inorder, preorder and postorder traversals for the given tree.

Create a B-tree for the given list of elements with given minimum degree / minimization factor.

What are B-trees? How are they created? Explain with a suitable example.

Write short notes on any three of the following.