Algorithms
Q1.
Consider the following C function int fun (int n) { int i, j; for (i = 1; i < = n; i++) { for (j = 1 ; j < n ; j+=i) { printf ("%d %d , i, j ) ; } } } Asymptotic Notation of fun in terms of \theta notation isQ3.
Let f and g be functions of natural numbers given by f(n)=n and g(n)=n^2. Which of the following statements is/are TRUE?Q4.
Consider functions Function 1 and Function 2 expressed in pseudocode as follows:Let f_1(n) and f_2(n) denote the number of times the statement "x = x + 1" is executed in Function 1 and Function 2, respectively. Which of the following statements is/are TRUE?Q5.
What is the complexity of the following code? sum=0; for(i=1;i<=n;i*=2) for(j=1;j<=n;j++) sum++;Which of the following is not a valid string?Q7.
There are n unsorted arrays: A_1,A_2,...,A_n. Assume that n is odd. Each of A_1,A_2,...,A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case Asymptotic Notation of computing the median of the medians of A_1,A_2,...,A_n is ________ .Q8.
Consider the following three functions. f_1=10^n\; f_2=n^{\log n}\;f_3=n^{\sqrt {n}} Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?Q9.
In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E|=m and |V|=n, and the memory size is not a constraint, what is the Asymptotic Notation of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?Q10.
Consider the following functions from positive integers to real numbers: 10,\sqrt{n},n, log_{2}n,\frac{100}{n}. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is: