Design & Analysis of Algorithms

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following is TRUE?

I. Quicksort runs in $\Theta(n^2)$ time
II. Bubblesort runs in $\Theta(n^2)$ time
III. Mergesort runs in $\Theta(n)$ time
IV. Insertion sort runs in $\Theta(n)$ time

• (i) I and II only
• (ii) I and III only
• (iii) II and IV only
• (iv) I and IV only

Worst-case complexity of heap sort is -

• (i) $O(\log n)$
• (ii) $O(n^2)$
• (iii) $O(n \log n)$
• (iv) $O(n)$

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

• (i) $\Theta(n \log n)$, $\Theta(n \log n)$ and $\Theta(n^2)$
• (ii) $\Theta(n^2)$, $\Theta(n^2)$ and $\Theta(n \log n)$
• (iii) $\Theta(n^2)$, $\Theta(n \log n)$ and $\Theta(n \log n)$
• (iv) $\Theta(n^2)$, $\Theta(n \log n)$ and $\Theta(n^2)$

The complexity algorithm of binary search is:

• (i) $O(n)$
• (ii) $O(\log n)$
• (iii) $O(n^2)$
• (iv) $O(n \log n)$

The minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers is

• (i) $O(n)$
• (ii) $O(\log n)$
• (iii) $O(n \log n)$
• (iv) $O(1)$

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

• (i) divide/break
• (ii) sorting/divide
• (iii) conquer/solve
• (iv) 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:

• (i) 10, 8, 7, 5, 3, 2, 1
• (ii) 10, 8, 7, 2, 3, 1, 5
• (iii) 10, 8, 7, 1, 2, 3, 5
• (iv) 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:

• (i) dynamic programming
• (ii) greedy
• (iii) divide and conquer
• (iv) recursion

The complexity of binary search algorithm is:

• (i) $O(n)$
• (ii) $O(\log n)$
• (iii) $O(n^2)$
• (iv) $O(n \log n)$

Write the algorithm for quick-sort and find its complexity.

Write Divide - And - Conquer Quick sort algorithm and analyze the algorithm for average time complexity.

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

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

Simulate Quick sort algorithm for the following example
25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65, 78

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

Construct the max heap for the following: 35 33 42 10 14 19 27 44 26 31

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 Strassen's matrix multiplication and its time complexity.

Write short notes on: Heap creation technique

Write short notes on: Strassen's matrix multiplication