GATE CSE 2003
Q31.
Consider the following recurrence relation T(1)=1 T(n+1)=T(n)+\left \lfloor \sqrt{n+1} \right \rfloor for all n \geq 1 The value of T(m^{2} ) for m \geq 1 isQ32.
Nobody knows yet if P = NP. Consider the language L defined as follows : L=\left\{\begin{matrix} (0+1)^{*}\; \; \; if P=NP\\ \Phi \; \; otherwise \end{matrix}\right. Which of the following statements is true ?Q35.
In a permutation a_1.....a_n of n distinct integers, an inversion is a pair (a_i, a_j) such that i \lt j and a_i \gt a_j. What would be the worst case time complexity of the insertion Sort algorithm, if the inputs are restricted to permutations of 1....n with at most n inversions?Q36.
The usual \Theta (n^{2}) implementation of Insertion Sort to sort ab array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time willQ37.
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?Q39.
Let G = (V,E) be an undirected graph with a sub-graph G1 = (V1,E1), Weight are assigned to edges of G as follows w(e)=\left\{\begin{matrix} 0 &if \; e \in E, \\ 1& otherwise \end{matrix}\right. A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex v1 of V1 as the source. Which of the following can always be inferred from the path costs computed?Q40.
In a bottom-up evaluation of a syntax directed definition, inherited attributes can