Design and Analysis of Algorithms - B.Tech 5th Semester Special Exam., 2020

Find the complexity of the below program:
void function(int n) { int i=1, s=1; while(s<=n) { i++; s+=i; printf("*"); } }

1. \( \Omega(n) \)
2. \( O(\sqrt{n}) \)
3. \( \Theta(loglogn) \)
4. \( \Theta(sqrt(n)) \)

How many undirected graphs (not necessarily connected) can be constructed out of a given set \( V = \{V_1, V_2, \dots, V_n\} \) of n vertices?

1. \( n(n-1)/2 \)
2. \( 2^n \)
3. \( n! \)
4. \( 2^{n(n-1)/2} \)

The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is

1. \( T(n)=2T(n-2)+2 \)
2. \( T(n)=2T(n-1)+n \)
3. \( T(n)=2T(n/2)+1 \)
4. \( T(n)=2T(n-1)+1 \)

Dijkstra's algorithm is based on

1. dynamic programming
2. divide and conquer
3. greedy programming
4. None of the above

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

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

Name three sorting algorithms which are stable by nature.

1. Bubble sort, Insertion sort, Merge sort
2. Bubble sort, Quick sort, Heap sort
3. Insertion sort, Radix sort, Heap sort
4. Count sort, Radix sort, Quick sort

What is the worst time complexity of insertion sort?

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

The most efficient algorithm for finding the number of connected components in an undirected graph of n vertices and m edges has the time complexity

1. \( O(n) \)
2. \( O(m) \)
3. \( O(m+n) \)
4. \( O(mn) \)

Which of the following statement is not true about breadth-first search (BFS) in an undirected graph starting at a vertex v?

1. BFS identifies all vertices reachable from v.
2. Using an adjacency list instead of an adjacency matrix can improve the worst case complexity to \( O(n+m) \).
3. BFS cannot be used to check for cycles in the graph.
4. BFS can be used to identify the furthest vertex from v in any graph, in terms of number of nodes.

Finding the location of the element with a given value is

1. traversal
2. search
3. sort
4. None of the above

Write the asymptomatic notation used for best case, average case and worst case analysis of algorithm. Write an algorithm for finding maximum element in an array. Give best, worst and average case complexities.

Explain the brute force method to find the two closet points in a set of n points in k-dimensional space.

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

Write an algorithm based on divide-and-conquer strategy to search an element in a given list. Assume that the elements of list are in sorted order.

What is the relationship among P, NP and NP-complete problems? Show with the help of a diagram.

Give the complete solution (step-by-step using state space tree) for N-Queen problem using back-tracking with pseudocode. Give the complexity analysis.

Construct the Huffman coding tree for the text of characters with given frequencies: T:43, I:38, V:16, K:8, L:56, E:12, O:41, Z:13, P:22, R:6. Also find the variable length Huffman codes and frequency path length for corresponding above characters.

Find the optimal way to multiply the following matrices to perform the fewest multiplications:
\( A_1: 5 \times 11 \), \( A_2: 11 \times 4 \), \( A_3: 4 \times 15 \), \( A_4: 15 \times 23 \)