Recent questions tagged algorithms / GATE Overflow for GATE CSE

15 votes

2 answers

3181

TIFR CSE 2013 | Part B | Question: 17
In a connected weighted graph with $n$ vertices, all the edges have distinct positive integer weights. Then, the maximum number of minimum weight spanning trees in the graph is $1$ $n$ equal to number of edges in the graph. equal to maximum weight of an edge of the graph. $n^{n-2}$

In a connected weighted graph with $n$ vertices, all the edges have distinct positive integer weights. Then, the maximum number of minimum weight spanning trees in the gr...

makhdoom ghaya

1.9k views

makhdoom ghaya asked Nov 8, 2015

25 votes

2 answers

3182

TIFR CSE 2013 | Part B | Question: 12
It takes $O(n)$ time to find the median in a list of $n$ elements, which are not necessarily in sorted order while it takes only $O(1)$ time to find the median in a list of $n$ sorted elements. How much time does it take to find the median of $2n$ elements which are ... $O (n)$ but not $O (\sqrt{n})$ $O \left(n \log n\right)$ but not $O (n)$

It takes $O(n)$ time to find the median in a list of $n$ elements, which are not necessarily in sorted order while it takes only $O(1)$ time to find the median in a list ...

makhdoom ghaya

3.3k views

makhdoom ghaya asked Nov 7, 2015

4 votes

1 answer

3183

TIFR CSE 2013 | Part B | Question: 7
Which of the following is not implied by $P=NP$? $3$SAT can be solved in polynomial time. Halting problem can be solved in polynomial time. Factoring can be solved in polynomial time. Graph isomorphism can be solved in polynomial time. Travelling salesman problem can be solved in polynomial time.

Which of the following is not implied by $P=NP$?$3$SAT can be solved in polynomial time.Halting problem can be solved in polynomial time.Factoring can be solved in polyno...

makhdoom ghaya

1.7k views

makhdoom ghaya asked Nov 6, 2015

29 votes

3 answers

3184

TIFR CSE 2013 | Part B | Question: 5
Given a weighted directed graph with $n$ vertices where edge weights are integers (positive, zero, or negative), determining whether there are paths of arbitrarily large weight can be performed in time $O(n)$ $O(n . \log(n))$ but not $O (n)$ $O(n^{1.5})$ but not $O (n \log n)$ $O(n^{3})$ but not $O(n^{1.5})$ $O(2^{n})$ but not $O(n^{3})$

Given a weighted directed graph with $n$ vertices where edge weights are integers (positive, zero, or negative), determining whether there are paths of arbitrarily large ...

makhdoom ghaya

4.5k views

makhdoom ghaya asked Nov 6, 2015

2 votes

1 answer

3185

Can these be solved by Master's theorem?
1) $T(n)=T(n/2)+2^n$ 2) $T(n)=2T(n/2)+n / \log n$ 3) $T(n)=16T(n/4)+n!$ 4) $T(n)= \sqrt 2T ( n/2 ) + \log n$

1) $T(n)=T(n/2)+2^n$2) $T(n)=2T(n/2)+n / \log n$3) $T(n)=16T(n/4)+n!$4) $T(n)= \sqrt 2T ( n/2 ) + \log n$

Himani Srivastava

3.8k views

Himani Srivastava asked Nov 4, 2015

18 votes

3 answers

3186

TIFR CSE 2012 | Part B | Question: 14
Consider the quick sort algorithm on a set of $n$ ... $\Theta (n^{2})$. None of the above.

Consider the quick sort algorithm on a set of $n$ numbers, where in every recursive subroutine of the algorithm, the algorithm chooses the median of that set as the pivot...

makhdoom ghaya

3.7k views

makhdoom ghaya asked Nov 2, 2015

30 votes

4 answers

3187

TIFR CSE 2012 | Part B | Question: 13
An array $A$ contains $n$ integers. We wish to sort $A$ in ascending order. We are told that initially no element of $A$ is more than a distance $k$ away from its final position in the sorted list. Assume that $n$ and $k$ are large ... $A$ can be sorted with constant $\cdot k^{2}n$ comparisons but not fewer.

An array $A$ contains $n$ integers. We wish to sort $A$ in ascending order. We are told that initially no element of $A$ is more than a distance $k$ away from its final p...

makhdoom ghaya

3.5k views

makhdoom ghaya asked Nov 2, 2015

22 votes

3 answers

3188

TIFR CSE 2012 | Part B | Question: 11
Consider the following three version of the binary search program. Assume that the elements of type $T$ can be compared with each other; also assume that the array is sorted. i, j, k : integer; a : array [1....N] of T; x : T; Program 1 : ... $1$ and $2$ are correct. Both Program $2$ and $3$ are correct All the three programs are wrong

Consider the following three version of the binary search program. Assume that the elements of type $T$ can be compared with each other; also assume that the array is sor...

makhdoom ghaya

2.6k views

makhdoom ghaya asked Nov 1, 2015

25 votes

4 answers

3189

TIFR CSE 2012 | Part B | Question: 6
Let $n$ be a large integer. Which of the following statements is TRUE? $2^{\sqrt{2\log n}}< \frac{n}{\log n}< n^{1/3}$ $\frac{n}{\log n}< n^{1/3}< 2^{\sqrt{2\log n}}$ $2^\sqrt{{2\log n}}< n^{1/3}< \frac{n}{\log n}$ $n^{1/3}< 2^\sqrt{{2\log n}}<\frac{n}{\log n}$ $\frac{n}{\log n}< 2^\sqrt{{2\log n}}<n^{1/3}$

Let $n$ be a large integer. Which of the following statements is TRUE?$2^{\sqrt{2\log n}}< \frac{n}{\log n}< n^{1/3}$$\frac{n}{\log n}< n^{1/3}< 2^{\sqrt{2\log n}}$$2^\sq...

makhdoom ghaya

4.3k views

makhdoom ghaya asked Oct 31, 2015

17 votes

3 answers

3190

TIFR CSE 2011 | Part B | Question: 39
The first $n$ cells of an array $L$ contain positive integers sorted in decreasing order, and the remaining $m - n$ cells all contain 0. Then, given an integer $x$, in how many comparisons can one find the position of $x$ in $L$? At least $n$ ... $O (\log n)$ comparisons suffice. $O (\log (m / n))$ comparisons suffice.

The first $n$ cells of an array $L$ contain positive integers sorted in decreasing order, and the remaining $m - n$ cells all contain 0. Then, given an integer $x$, in ho...

makhdoom ghaya

4.1k views

makhdoom ghaya asked Oct 25, 2015

7 votes

1 answer

3191

TIFR CSE 2011 | Part B | Question: 37
Given an integer $n\geq 3$, consider the problem of determining if there exist integers $a,b\geq 2$ such that $n=a^{b}$. Call this the forward problem. The reverse problem is: given $a$ and $b$, compute $a^{b}$ (mod b). Note ... in polynomial time, however the forward problem is $NP$-hard. Both the forward and reverse problem are $NP$-hard. None of the above.

Given an integer $n\geq 3$, consider the problem of determining if there exist integers $a,b\geq 2$ such that $n=a^{b}$. Call this the forward problem. The reverse proble...

makhdoom ghaya

1.9k views

makhdoom ghaya asked Oct 25, 2015

15 votes

3 answers

3192

TIFR CSE 2011 | Part B | Question: 35
Let $G$ be a connected simple graph (no self-loops or parallel edges) on $n\geq 3$ vertices, with distinct edge weights. Let $e_{1}, e_{2},...,e_{m}$ be an ordering of the edges in decreasing order of weight. Which of the ... spanning tree. The edge $e_{m}$ is never present in any maximum weight spanning tree. $G$ has a unique maximum weight spanning tree.

Let $G$ be a connected simple graph (no self-loops or parallel edges) on $n\geq 3$ vertices, with distinct edge weights. Let $e_{1}, e_{2},...,e_{m}$ be an ordering of th...

makhdoom ghaya

2.8k views

makhdoom ghaya asked Oct 24, 2015

39 votes

4 answers

3193

TIFR CSE 2011 | Part B | Question: 31
Given a set of $n=2^{k}$ distinct numbers, we would like to determine the smallest and the second smallest using comparisons. Which of the following statements is TRUE? Both these elements can be determined using $2k$ comparisons. ... $nk$ comparisons are necessary to determine these two elements.

Given a set of $n=2^{k}$ distinct numbers, we would like to determine the smallest and the second smallest using comparisons. Which of the following statements is TRUE?Bo...

makhdoom ghaya

7.8k views

makhdoom ghaya asked Oct 22, 2015

17 votes

2 answers

3194

TIFR CSE 2011 | Part B | Question: 21
Let $S=\left \{ x_{1},....,x_{n} \right \}$ be a set of $n$ numbers. Consider the problem of storing the elements of $S$ in an array $A\left [ 1...n \right ]$ ... time. This problem can be solved in $O \left ( n^{2} \right )$ time but not in $O(n\log n)$ time. None of the above.

Let $S=\left \{ x_{1},....,x_{n} \right \}$ be a set of $n$ numbers. Consider the problem of storing the elements of $S$ in an array $A\left [ 1...n \right ]$ such that t...

makhdoom ghaya

2.1k views

makhdoom ghaya asked Oct 20, 2015

1 votes

1 answer

3195

m-way merge sort
Assume 5 buffer pages are available to sort a file of 105 pages.The cost of sorting using m-way merge sort is- a)206 b)618 c)840 d)926

Assume 5 buffer pages are available to sort a file of 105 pages.The cost of sorting using m-way merge sort is- a)206b)618c)840d)926

sampad

1.3k views

sampad asked Oct 19, 2015

3 votes

1 answer

3196

Cormen Edition 3 Exercise 23.2 Question 6 (Page No. 637)
Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?

Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?

Pooja Palod

3.0k views

Pooja Palod asked Oct 15, 2015

8 votes

3 answers

3197

TIFR CSE 2010 | Part B | Question: 39
Suppose a language $L$ is $\mathbf{NP}$ complete. Then which of the following is FALSE? $L \in \mathbf{NP}$ Every problem in $\mathbf{P}$ is polynomial time reducible to $L$. Every problem in $\mathbf{NP}$ is polynomial time reducible to $L$. The Hamilton cycle problem is polynomial time reducible to $L$. $\mathbf{P} \neq \mathbf{NP}$ and $L \in \mathbf{P}$.

Suppose a language $L$ is $\mathbf{NP}$ complete. Then which of the following is FALSE?$L \in \mathbf{NP}$Every problem in $\mathbf{P}$ is polynomial time reducible to $L...

makhdoom ghaya

1.6k views

makhdoom ghaya asked Oct 11, 2015

2 votes

3 answers

3198

What is the time complexity of the following C code?
int Test(int n) { if (n<=0) return 0; else { int i = random(n-1); return Test(i) + Test(n-1-i); } } Suppose the function $\text{random}()$ takes constant time, then what is the time complexity of $T(n)$?

int Test(int n) { if (n<=0) return 0; else { int i = random(n-1); return Test(i) + Test(n-1-i); } }Suppose the function $\text{random}()$ takes constant time, then what ...

admin

1.2k views

admin asked Oct 8, 2015

4 votes

5 answers

3199

The running time of an algorithm is given by T(n) = T(n-1) + T(n-2) - T(n-3) , if n>3

worst_engineer

18.3k views

worst_engineer asked Oct 7, 2015

1 votes

1 answer

3200

Consider the following three claims for time complexity
In my opinion , Option a is correct . Am i right ?

In my opinion , Option a is correct . Am i right ?

worst_engineer

555 views

worst_engineer asked Oct 7, 2015

4 votes

2 answers

3201

In quick sort , for sorting n elements , the (n/4)th smallest element
In quick sort , for sorting n elements , the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What will be the time complexity? it is $\Theta (n^{2})$ , right ?

In quick sort , for sorting n elements , the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What will be the time complexity?it is $\Theta (...

worst_engineer

6.1k views

worst_engineer asked Oct 7, 2015

2 votes

1 answer

3202

Which of the following sorting methods will be the best if number of swapping
Which of the following sorting methods will be the best if number of swapping done is the only measure of efficiency I am getting Bubble sort , is it right ?

Which of the following sorting methods will be the best if number of swapping done is the only measure of efficiencyI am getting Bubble sort , is it right ?

worst_engineer

5.6k views

worst_engineer asked Oct 7, 2015

26 votes

1 answer

3203

TIFR CSE 2010 | Part B | Question: 29
Suppose you are given an array $A$ with $2n$ numbers. The numbers in odd positions are sorted in ascending order, that is, $A[1] \leq A[3] \leq \ldots \leq A[2n - 1]$. The numbers in even positions are sorted in ... on the entire array. Perform separate binary searches on the odd positions and the even positions. Search sequentially from the end of the array.

Suppose you are given an array $A$ with $2n$ numbers.The numbers in odd positions are sorted in ascending order, that is, $A \leq A[3] \leq \ldots \leq A[2n - 1]$.The nu...

makhdoom ghaya

4.4k views

makhdoom ghaya asked Oct 6, 2015

22 votes

4 answers

3204

TIFR CSE 2010 | Part B | Question: 27
Consider the Insertion Sort procedure given below, which sorts an array $L$ of size $n\left ( \geq 2 \right )$ in ascending order: begin for xindex:= 2 to n do x := L [xindex]; j:= xindex - 1; while j > 0 and L[j] > x do L[j + ... $n (n - 1) / 2$ comparisons whenever all the elements of $L$ are not distinct.

Consider the Insertion Sort procedure given below, which sorts an array $L$ of size $n\left ( \geq 2 \right )$ in ascending order:begin for xindex:= 2 to n do x := L [xin...

makhdoom ghaya

3.8k views

makhdoom ghaya asked Oct 6, 2015

12 votes

2 answers

3205

TIFR CSE 2010 | Part B | Question: 24
Consider the following program operating on four variables $u, v, x, y$, and two constants $X$ and $Y$. x, y, u, v:= X, Y, Y, X; While (x ≠ y) do if (x > y) then x, v := x - y, v + u; else if (y > x) then y, u:= y ... . The program prints $\frac1 2 \times \text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$. The program does none of the above.

Consider the following program operating on four variables $u, v, x, y$, and two constants $X$ and $Y$.x, y, u, v:= X, Y, Y, X; While (x ≠ y) do if (x y) then x, v := ...

makhdoom ghaya

1.8k views

makhdoom ghaya asked Oct 6, 2015

2 votes

1 answer

3206

the minimum no of comparisons required to find Majority Element in a sorted array (note that key is not given).

for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)

yes

1.4k views

yes asked Oct 6, 2015

15 votes

3 answers

3207

TIFR CSE 2010 | Part B | Question: 23
Suppose you are given $n$ numbers and you sort them in descending order as follows: First find the maximum. Remove this element from the list and find the maximum of the remaining elements, remove this element, and so on, until all elements are exhausted. How many comparisons ... $O\left ( n^{1.5} \right )$ but not better.

Suppose you are given $n$ numbers and you sort them in descending order as follows:First find the maximum. Remove this element from the list and find the maximum of the r...

makhdoom ghaya

4.9k views

makhdoom ghaya asked Oct 5, 2015

3 votes

2 answers

3208

ISRO2011-70
Number of comparisons required for an unsuccessful search of an element in a sequential search organized, fixed length, symbol table of length L is L L/2 (L+1)/2 2L

Number of comparisons required for an unsuccessful search of an element in a sequential search organized, fixed length, symbol table of length L isLL/2(L+1)/22L

ajit

6.9k views

ajit asked Oct 1, 2015

0 votes

1 answer

3209

which of the following are true?
which is true please explain.. .f(n)=O(f.(n)2) .if f(n)=Og(n) then 2f(n)=O(2g(n)) .2n≄O(nk) where k is constant .lognlogn>2logn>nlogn

which is true please explain...f(n)=O(f.(n)2).if f(n)=Og(n) then 2f(n)=O(2g(n)).2n≄O(nk) where k is constant.lognlogn>2logn>nlogn

Nishikant kumar

779 views

Nishikant kumar asked Sep 29, 2015

–1 votes

3 answers

3210

Time complexity!
void find (int n) { if (n < 2) return; else { sum = 0; for (i = 1; i <= 4; i++) find(n / 2); for (i = 1; i <= n*n; i++) sum = sum +1; } } assume that the division operation takes constant time and sum is global variable. what is the time complexity of find(n)?

void find (int n) { if (n < 2) return; else { sum = 0; for (i = 1; i <= 4; i++) find(n / 2); for (i = 1; i <= n*n; i++) sum = sum +1; } }assume that the division operatio...

Umang Raman

877 views

Umang Raman asked Sep 25, 2015

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true