Design & Analysis of Algorithms

In the following C++ function, let $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;
}

What is the time complexity of the above function assuming $n > m$?

• (i) $\Theta(\log n)$
• (ii) $\Omega(n)$
• (iii) $\Theta(\log \log n)$
• (iv) $\Theta(\sqrt{n})$

Any decision trees that sorts $n$ elements has height:

• (i) $\Omega(\lg n)$
• (ii) $\Omega(n)$
• (iii) $\Omega(n \lg n)$
• (iv) $\Omega(n^2)$

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

• (i) When a resource is shared among multiple consumers
• (ii) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
• (iii) Load balancing
• (iv) All of the above

Any decision tree that sorts $n$ elements has height:

• (i) $\Omega(\lg n)$
• (ii) $\Omega(n)$
• (iii) $\Omega(n \lg n)$
• (iv) $\Omega(n^2)$

In linear search algorithm the worst case occurs when:

• (i) the item is somewhere in the middle of the array
• (ii) the item is not in the array at all
• (iii) the item is the last element in the array
• (iv) the item is the last element in the array or is not there at all

What is the minimum number of stacks of size $n$ required to implement a queue of size $n$

• (i) one
• (ii) two
• (iii) three
• (iv) four

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?

• (i) Insertion sort with time complexity $O(kn)$
• (ii) Heap sort with time complexity $O(n \log k)$
• (iii) Quick sort with time complexity $O(k \log k)$
• (iv) Merge sort with time complexity $O(k \log k)$

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

• (i) When a resource is shared among multiple consumers
• (ii) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
• (iii) Load balancing
• (iv) All of the above

An algorithm is made up of two independent time complexities $f(n)$ and $g(n)$. Then the complexity of the algorithm is in order of:

• (i) $f(n) \times g(n)$
• (ii) $\max(f(n), g(n))$
• (iii) $\min(f(n), g(n))$
• (iv) $f(n) + g(n)$

Define Asymptotic Notation. Show that $n^2 + 3\log n = O(n^2)$

Discuss the average, worst, and best time complexity of the algorithm. Give suitable examples.

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

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

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 <= 1) return(1);
    else {
        rec(n / 2);
        for (i = 1; i <= n; i++)
            printf("algorithm");
    }
}

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

Solve the recurrence relation $T(n) = 2T(n/2) + O(n)$

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

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))$.

State Master's theorem and find the time complexity for the following recurrence: $$T(n) = 2T(n^{1/2}) + \log n$$

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

Write short notes on: Asymptotic notations

Write short notes on: Amortized analysis.

Write short notes on: Masters theorem