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

In the following C++ function, let \( n \ge m \). What is the time complexity of the above function assuming \( n > m \)?
int gcd(int n, int m) { if(n%m==0) return m; if(n < m) swap(n, m); while(m>0) { n=n%m; swap(n, m); } return n; }

1. \( \Theta(\log n) \)
2. \( \Omega(n) \)
3. \( \Theta(loglogn) \)
4. \( \Theta(sqrt(n)) \)

Time complexity of Kadane's Algorithm is

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

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?

1. \( 1/8 \)
2. \( 1 \)
3. \( 7 \)
4. \( 8 \)

Any decision tree that sorts 'n' elements has height

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

An all-pairs shortest-paths problem is efficiently solved using

1. Dijkstra's algorithm
2. Bellman-Ford algorithm
3. Kruskal algorithm
4. Floyd-Warshall algorithm

Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

1. In adjacency list representation, space is saved for sparse graphs.
2. DFS and BFS can be done in \( O(V+E) \) time for adjacency list representation.
3. Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
4. All of the above

Which of the following is true about Huffman Coding?

1. Huffman coding may become lossy in some cases.
2. Huffman codes may not be optimal lossless codes in some cases.
3. In Huffman coding, no code is prefix of any other code.
4. All of the above

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

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

The complexity of binary search algorithm is

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

Discuss the steps in mathematical analysis for recursive algorithm. Do the same for finding the factorial of a number?

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

What are the advantages of merge-sort over the quick-sort algorithm?

What is the time complexity of the matrix multiplication and Strassen's algorithm?

Prove that if \( f_1(n) = O(g_1(n)) \) and \( f_2(n) = O(g_2(n)) \), then \( f_1(n)+f_2(n) = O(g_1(n)+g_2(n)) \).

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

Compare the various programming paradigms such as divide-and-conquer, dynamic programming and greedy approach.

Consider the array A = {26, 17, 41, 14, 21, 30, 47, 10, 16, 19, 21, 28, 38, 7, 12, 14, 20, 35, 39, 3}. Create binary search tree with one more attributes its size of node. Retrieve 17th smallest element in the tree and rank the 12th element.

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

Explain back-tracking, DFS and BFS with help of small example. Differentiate in between backtracking and dynamic programming. Apply the backtracking algorithm to solve the three-colouring problem for the graph using state space tree. Assume three colours red, green and blue.