Analysis Design of Algorithm (CS-402) - Important Questions

Trace / apply the quick sort algorithm step-by-step to sort a given list/array.

What is Merge sort (and Quicksort)? Sort a given list of elements using Merge sort.

Give the divide and conquer algorithm for binary search and analyze its time complexity including best, average and worst cases.

Use the substitution method to obtain the asymptotic $\Theta(n \log n)$ bound for the recurrence $T(n) = aT(n/b) + n$.

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

Solve the following recurrence relations using the substitution method.

$$T(n) = \begin{cases} 1 & n \le 4 \\ 2T(\sqrt{n}) + \log n & n > 4 \end{cases}$$

What is the best-case time complexity of merge sort given worst case $O(n \log n)$, and can its time be said to be $O(n \log n)$?

Sort the given array/data using heap sort, including the concept of a heap.

Write short notes on any two of the following :

Find asymptotic bounds and Theta notation for the polynomial function $f(n) = 2n^2 - 4n + 20$.

Obtain the asymptotic bound in Theta notation for the recurrence $T(n) = 3T(n/3) + n$ using the substitution method.

Write the algorithm for matrix multiplication using Strassen's method.

Construct optimal Huffman codes for given message frequencies and draw the decode tree, including applications of Huffman coding.

Solve the job sequencing with deadlines problem using the Greedy method for given profits and deadlines.

Apply the greedy method to solve the Knapsack instance with $n=3$, $m=20$

Define greedy algorithm, give its pseudocode, and apply it to graph vertex coloring.

Explain Kruskal's algorithm with the help of a suitable example.

Use algorithm shortest paths to obtain in non-decreasing order the lengths of the shortest paths from vertex 1 to all remaining vertices in the di-graph.

Suppose there are $n$ jobs to be executed but only $k$ processors that can work in parallel. The time required by jobs $i$ to $t_{i}$, write an algorithm that determines which jobs are to be run on which processors and the order in which they should be run so that the finish time of the last job is minimized.

Define spanning tree? Construct a minimal spanning tree for the given graph using Prim's algorithm.

Apply the greedy method to solve the 0/1 Knapsack problem for $n = 3$, $m = 20$, $(w_1, w_2, w_3) = (18, 15, 10)$ and $(p_1, p_2, p_3) = (25, 24, 15)$.

Solve job sequencing with deadlines problem using greedy method for given profits and deadlines

Explain how to solve the Knapsack problem using the greedy method

Write the algorithm for the single-source shortest path (Dijkstra's) problem, with explanation/example and complexity.

Explain the Floyd-Warshall algorithm with a suitable example.

Solve a 0/1 knapsack instance with given weights, profits and capacity to find the optimal solution.

Find the optimal solution to a given 0/1 knapsack instance using dynamic programming.

Construct a multistage graph for the given graph using the Greedy method.

Explain the Floyd-Warshall all-pairs shortest path algorithm with a suitable example, including pseudocode.

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

Compare dynamic programming, greedy method, and divide and conquer method in detail.

How reliability design / system reliability can be obtained using dynamic programming?

Give an example family of 0/1 knapsack instances with $|S^i| = 2^i$ for $0 \le i \le n$.

Use the function OBST to compute $w(i, j)$, $r(i, j)$ and $c(i, j)$, $0 \le i < j \le 4$ for the identifier set $(a_1, a_2, a_3, a_4) =$ (char, float, while, else) with $p(1) = \frac{1}{20}$, $p(2) = \frac{1}{5}$, $p(3) = \frac{1}{10}$, $p(4) = \frac{1}{20}$, $q(0) = \frac{1}{5}$, $q(1) = \frac{1}{10}$, $q(2) = \frac{1}{5}$, $q(4) = \frac{1}{20}$. Using $r(i, j)$'s construct the optimal binary search tree.

Give an example family of knapsack instances with $|S^{i}| = 2^{i}$ for $0 \le i \le n$.

Explain forward and backward approaches to problem solving in dynamic programming.

Write an algorithm for the 8-queens problem using backtracking.

Explain graph coloring / $m$-coloring and illustrate with example / state space tree

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

Obtain two solutions to the 4-queens problem and establish the relationship between them

What is Hamiltonian cycle? Explain how it can be solved using backtracking approach?

Explain Travelling Salesman Problem in detail.

Given an $n \times n$ chessboard, a knight is placed on an arbitrary square with coordinates $(x, y)$. The problem is to determine $n^{2}-1$ Knight moves such that every square of the board is visited once if such a sequence of moves exists. Present an algorithm to solve this problem.

Solve the traveling salesperson problem for the given cost matrix using branch and bound.

Explain the 8-queens problem and solve it using backtracking

Explain in detail about the FIFO branch and bound.

Explain the 0/1 knapsack problem using the branch and bound technique.

Give control abstraction for LC-Search and explain solving TSP using LC branch and bound.

Explain balance factor and height-balanced AVL tree with a suitable example of balancing.

Explain the difference between P and NP.

Explain approximation algorithms for Vertex Cover.

Write short notes on following. (any two)

Show that DFS visits all vertices in G reachable from V.

Obtain a nondeterministic algorithm of complexity O($n$) to determine whether there is a subset of $n$ numbers $a_{i}, 1 \le i \le n$, that sums of $m$.

Write an algorithm to delete an element $x$ from a binary search tree $t$ and give its time complexity.

Compare / differentiate between BFS and DFS.

Compute $w(i,j)$, $r(i,j)$ and $c(i,j)$ using OBST for given $p$ and $q$ and construct the optimal binary search tree.

Explain in detail about 2-3 Trees with an example.

Write a function to construct a binary tree from given inorder and postorder sequences and give its complexity.

Give an example of an n-vertex graph where DFS recursion depth from V is $n-1$ while BFS queue from V holds at most one vertex.

Write short notes on any two of the following.

Discuss briefly any two of the following: a) Heap sort b) Dynamic Programming c) Height balanced tree d) Parallel algorithm