Design and Analysis of Algorithms - B.Tech 4th Semester Exam., 2022

Any decision trees that sorts elements has height

1. \( \Omega(\lg n) \)
2. \( \Omega(n) \)
3. \( \Omega(n \lg n) \)
4. \( \Omega(n^2) \)

Which one of the following is an application of Queue Data Structure?

1. When a resource is shared among multiple consumers
2. When data is transferred asynchronously between two processes
3. Load balancing
4. All of the above

The complexity of binary search algorithm is

1. \( O(n) \)
2. \( O(\log n) \)
3. \( O(n^2) \)
4. \( O(n \log n) \)

In linear search algorithm the worst case occurs when

1. the item is somewhere in the middle of the array
2. the item is not in the array at all
3. the item is the last element in the array
4. the item is the last element in the array or is not there at all

Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

1. Insertion sort with time complexity \( O(kn) \)
2. Heap sort with time complexity \( O(n \log k) \)
3. Quick sort with time complexity \( O(k \log k) \)
4. Merge sort with time complexity \( O(k \log k) \)

Approach of dynamic programming is similar to

1. parsing
2. hash table
3. divide and conquer algorithm
4. greedy algorithm

In the divide and conquer process, breaking the problem into smaller sub-problems is the responsibility of

1. divide/break
2. sorting/divide
3. conquer/solve
4. merge/combine

A priority queue is implemented as a Max-heap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements '1' and '7' are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is

1. 10, 8, 7, 5, 3, 2, 1
2. 10, 8, 7, 2, 3, 1, 5
3. 10, 8, 7, 1, 2, 3, 5
4. 10, 8, 7, 3, 2, 1, 5

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called

1. dynamic programming
2. greedy
3. divide and conquer
4. recursion

The choice of polynomial class has led to the development of an extensive theory called

1. computational complexity
2. time complexity
3. problem complexity
4. decision complexity

Calculate the time complexity of the following problem using divide and conquer strategies:
(i) \( T(n) = \sqrt{n} T(\sqrt{n}) + n \), \( n > 2 \)
\( = a \), \( n \le 2 \)
(ii) \( T(n) = T(n-1) + 1/n \), \( n > 1 \)
\( = 1 \), \( n = 1 \)

Write time function and calculate the time complexity, space complexity and number of function calls of the following pseudocode using substitution method:
rec (n) {
if (\( n \le 1 \)) return(1);
else { rec (n/2); for (\( i=1; i \le n; i++ \)) printf("algorithm"); }
}

Explain the working of merge sort algorithm with an example. Give the complexity calculation of merge sort.

What are the rules of manipulate Big-Oh expression and about the typical growth rates of algorithms.

What is heap sort? What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?

Explain how radix sort works, to what inputs it can be applied and what is its asymptotic complexity?

What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider the given graph \( G=(V,E) \) and find the minimum spanning tree by Prim's algorithms.

Find the optimal way to multiply the following matrices to perform the fewest multiplications:
A1: \( 5 \times 11 \), A2: \( 11 \times 4 \), A3: \( 4 \times 15 \), A4: \( 15 \times 23 \)

You are given a graph containing n vertices and m edges and given that the graph doesn't contain cycle of odd length. What is the time complexity of the best known algorithm to find out whether the graph is bipartite or not?

What is activity selection problem? Suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.