Recent questions tagged algorithms / GATE Overflow for GATE CSE

0 votes

1 answer

3271

How could you find first occurence in Logn time using a variant of BS?
I mean i guess it should be in O(n/2) i.e. O(n) time. Because one must check for every element starting from the first one till n/2 th element & for each of which one must whether A[i]==A[n/2 +i]. Please explain.

I mean i guess it should be in O(n/2) i.e. O(n) time. Because one must check for every element starting from the first one till n/2 th element & for each of which one mus...

Mohit Mishra

1.1k views

Mohit Mishra asked Apr 3, 2015

0 votes

1 answer

3272

How to build the decision tree??

Gate Sanyasi

466 views

Gate Sanyasi asked Apr 2, 2015

35 votes

7 answers

3273

GATE CSE 2015 Set 3 | Question: 49
Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n$, consider the following pseudocode. DOSOMETHING (c, a, n) $z \leftarrow 1$ ... , then the output of DOSOMETHING(c, a, n) is _______.

Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n...

go_editor

7.4k views

go_editor asked Feb 16, 2015

67 votes

11 answers

3274

GATE CSE 2015 Set 3 | Question: 42
Let $f(n) = n$ and $g(n) = n^{(1 + \sin \: n)}$, where $n$ is a positive integer. Which of the following statements is/are correct? $f(n) = O(g(n))$ $f(n) = \Omega(g(n))$ Only I Only II Both I and II Neither I nor II

Let $f(n) = n$ and $g(n) = n^{(1 + \sin \: n)}$, where $n$ is a positive integer. Which of the following statements is/are correct?$f(n) = O(g(n))$$f(n) = \Omega(g(n))$On...

go_editor

17.5k views

go_editor asked Feb 15, 2015

44 votes

5 answers

3275

GATE CSE 2015 Set 3 | Question: 40
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is increased by five, the weight of a minimum spanning tree becomes ______.

Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is i...

go_editor

10.8k views

go_editor asked Feb 15, 2015

60 votes

5 answers

3276

GATE CSE 2015 Set 3 | Question: 39
Consider the following recursive C function. void get(int n) { if (n<1) return; get (n-1); get (n-3); printf("%d", n); } If $get(6)$ function is being called in $main()$ then how many times will the $get()$ function be invoked before returning to the $main()$? $15$ $25$ $35$ $45$

Consider the following recursive C function.void get(int n) { if (n<1) return; get (n-1); get (n-3); printf("%d", n); }If $get(6)$ function is being called in $main()$ th...

go_editor

18.1k views

go_editor asked Feb 15, 2015

59 votes

5 answers

3277

GATE CSE 2015 Set 3 | Question: 27
Assume that a mergesort algorithm in the worst case takes $30$ seconds for an input of size $64$. Which of the following most closely approximates the maximum input size of a problem that can be solved in $6$ minutes? $256$ $512$ $1024$ $2018$

Assume that a mergesort algorithm in the worst case takes $30$ seconds for an input of size $64$. Which of the following most closely approximates the maximum input size ...

go_editor

20.1k views

go_editor asked Feb 15, 2015

57 votes

5 answers

3278

GATE CSE 2015 Set 3 | Question: 4
Consider the equality $\displaystyle{\sum_{i=0}^n} i^3 = X$ and the following choices for $X$: $\Theta(n^4)$ $\Theta(n^5)$ $O(n^5)$ $\Omega(n^3)$ The equality above remains correct if $X$ is replaced by Only I Only II I or III or IV but not II II or III or IV but not I

Consider the equality $\displaystyle{\sum_{i=0}^n} i^3 = X$ and the following choices for $X$:$\Theta(n^4)$$\Theta(n^5)$$O(n^5)$$\Omega(n^3)$The equality above remains co...

go_editor

16.6k views

go_editor asked Feb 14, 2015

58 votes

4 answers

3279

GATE CSE 2015 Set 1 | Question: 49
Let a$_{n}$ represent the number of bit strings of length n containing two consecutive $1$s. What is the recurrence relation for $a_{n}$? $a_{n - 2} + a_{n - 1} + 2^{n - 2}$ $a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$ $2a_{n - 2} + a_{n - 1} + 2^{n - 2}$ $2a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$

Let a$_{n}$ represent the number of bit strings of length n containing two consecutive $1$s. What is the recurrence relation for $a_{n}$?$a_{n - 2} + a_{n - 1} + 2^{n - 2...

makhdoom ghaya

10.4k views

makhdoom ghaya asked Feb 13, 2015

51 votes

10 answers

3280

GATE CSE 2015 Set 1 | Question: 45
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ be the ... that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$

Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from ...

makhdoom ghaya

18.2k views

makhdoom ghaya asked Feb 13, 2015

70 votes

5 answers

3281

GATE CSE 2015 Set 1 | Question: 43
The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only ... which are in the MST are given in the figure shown below. The minimum possible sum of weights of all $8$ edges of this graph is_______________.

The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E...

makhdoom ghaya

17.7k views

makhdoom ghaya asked Feb 13, 2015

94 votes

5 answers

3282

GATE CSE 2015 Set 1 | Question: 40
An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{1}{2}}$ decrease-key operations on a set of data ... if the goal is to achieve the best total asymptotic complexity considering all the operations? Unsorted array Min - heap Sorted array Sorted doubly linked list

An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{1}{2}}$ decrease-...

makhdoom ghaya

23.8k views

makhdoom ghaya asked Feb 13, 2015

57 votes

7 answers

3283

GATE CSE 2015 Set 1 | Question: 31
Consider the following C function. int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for (j = n; j > 1; j = j/2) ++p; for (k = 1; k < p; k = k * 2) ++q; } return q; } Which one of the following most closely approximates the return value of the function $\text{fun1}$? $n^3$ $n(\log n)^2$ $n \log n$ $n \log(\log n)$

Consider the following C function.int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for (j = n; j 1; j = j/2) ++p; for (k = 1; k < p; k = k * 2)...

makhdoom ghaya

20.8k views

makhdoom ghaya asked Feb 13, 2015

55 votes

7 answers

3284

GATE CSE 2015 Set 2 | Question: 45
Suppose you are provided with the following function declaration in the C programming language. int partition(int a[], int n); The function treats the first element of $a[\:]$ as a pivot and rearranges the array so that all elements less than or equal to the pivot is in the ... $(a, $ left_end$, k)$ $(a, n-$left_end$-1, k-$left_end$-1)$ and $(a, $left_end$, k)$

Suppose you are provided with the following function declaration in the C programming language.int partition(int a[], int n);The function treats the first element of $a[\...

go_editor

16.6k views

go_editor asked Feb 13, 2015

25 votes

3 answers

3285

GATE CSE 2015 Set 2 | Question: 36
Given below are some algorithms, and some algorithm design paradigms. ... $\text{1-iii, 2-ii, 3-i, 4-iv}$ $\text{1-iii, 2-ii, 3-i, 4-v}$

Given below are some algorithms, and some algorithm design paradigms.$$\begin{array}{ll|ll}\hline \text{1.} & \text{Dijkstra's Shortest Path} & \text{i.} & \text{Divide a...

go_editor

7.1k views

go_editor asked Feb 12, 2015

61 votes

6 answers

3286

GATE CSE 2015 Set 2 | Question: 22
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is $\Theta(n \log n)$ $\Theta(n)$ $\Theta(\log n)$ $\Theta(1)$

An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is$\Theta(n \log n)$$\Thet...

go_editor

17.6k views

go_editor asked Feb 12, 2015

26 votes

4 answers

3287

GATE CSE 2015 Set 1 | Question: 6
Match the following: ... $\text{P-ii, Q-iii, R-iv, S-i}$ $\text{P-ii, Q-i, R-iii, S-iv}$

Match the following:$$\begin{array}{|ll|ll|}\hline \text{P.} & \text{Prim's algorithm for minimum spanning tree} & \text{i.} & \text{Backtracking} \\\hline \text{Q.}...

makhdoom ghaya

5.6k views

makhdoom ghaya asked Feb 12, 2015

62 votes

12 answers

3288

GATE CSE 2015 Set 2 | Question: 11
Consider the following C function. int fun(int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun (n-k); return x; } The return value of $fun(5)$ is ______.

Consider the following C function.int fun(int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun (n-k); return x; }The return value of $fun(5)$...

go_editor

21.2k views

go_editor asked Feb 12, 2015

16 votes

2 answers

3289

GATE CSE 2015 Set 2 | Question: 2
Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the following is consistent with the above statement? $Q_1$ is in NP, $Q_2$ is NP hard. $Q_2$ is in NP, $Q_1$ is NP hard. Both $Q_1$ and $Q_2$ are in NP. Both $Q_1$ and $Q_2$ are in NP hard.

Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the followi...

go_editor

6.5k views

go_editor asked Feb 12, 2015

33 votes

3 answers

3290

GATE CSE 2015 Set 1 | Question: 2
Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting $n\;( \geq 2)$ numbers? In the recurrence equations given in the options below, $c$ is a constant. $T(n) = 2 T (n/2) + cn$ $T(n) = T ( n - 1) + T(1) + cn$ $T(n) = 2T ( n - 1) + cn$ $T(n) = T (n/2) + cn$

Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting $n\;( \geq 2)$ numbers? In the recurrenc...

makhdoom ghaya

11.5k views

makhdoom ghaya asked Feb 11, 2015

2 votes

2 answers

3291

What is the worst case time complexity to find the gcd(m,n) using best algorithm known?
What is the worst case time complexity to find the gcd(m,n) using best algorithm known? A. O(log(min(m,n))) B, O(log(max(m,n)))

What is the worst case time complexity to find the gcd(m,n) using best algorithm known?A. O(log(min(m,n)))B, O(log(max(m,n)))

Vikrant Singh

1.7k views

Vikrant Singh asked Jan 31, 2015

0 votes

1 answer

3292

Let f(n) = O(n), g(n) = θ(n), and h(n) = Ω(n). Then f(n). h(n) + g(n) is_______________
let us consider f(n) is log(n) and g(n) = n and h(n) = n^2. since logn<= n n2 >= n for all values so given above equality holds true but when we substitute n+((logn)(n2) = O(n2) but ans is Ω(n) can somebody wxplain this plz

let us consider f(n) is log(n) and g(n) = n and h(n) = n^2.since logn<= n n2 >= n for all values so given above equality holds truebut when we substitute n+((logn)...

saurav04

2.8k views

saurav04 asked Jan 22, 2015

0 votes

3 answers

3293

Master Theorem
When do we say that 2 functions are polynomially comparable for applying master theorem...? We can apply the theorem for T(n)=3T(n/4)+nlgn but cant apply it for T(n)=2T(n/2)+nlgn ...please explain..?

When do we say that 2 functions are polynomially comparable for applying master theorem...? We can apply the theorem for T(n)=3T(n/4)+nlgn but cant apply it for T(n)=2T(n...

dhingrak

858 views

dhingrak asked Jan 18, 2015

0 votes

1 answer

3294

How can we found second smallest element with n+[lgn]-2 comparisons in worst case ??

Abhishek Kumar

3.5k views

Abhishek Kumar asked Jan 10, 2015

2 votes

1 answer

3295

Best algorithm in terms of time to sort numbers within range 1 to n^5

GateMaster Prime

1.3k views

GateMaster Prime asked Dec 28, 2014

1 votes

2 answers

3296

Which of the following statement is correct regarding DFS?
Which of the following statement is correct regarding DFS? 1) All the vertices are pushed in the stack during DFS Traversal. 2) No vertex is pushed more than once in the stack during traversal.

Which of the following statement is correct regarding DFS? 1) All the vertices are pushed in the stack during DFS Traversal. 2) No vertex is pushed more than once in the ...

Gate Aspirant 2

2.5k views

Gate Aspirant 2 asked Dec 19, 2014

0 votes

1 answer

3297

question

Sahil Gupta

293 views

Sahil Gupta asked Dec 17, 2014

0 votes

1 answer

3298

question:
answer is c. Can Any body suggest some analytical approach to solve it.

answer is c.Can Any body suggest some analytical approach to solve it.

Sahil Gupta

315 views

Sahil Gupta asked Dec 17, 2014

0 votes

2 answers

3299

Question:
Please answer both Question 9 and 10 both with approach. Also in Question 9th which algorithm they assume since I believe answer varies according to algorithm as well. In Question 10 answer given is 1. Question 9 answer is d

Please answer both Question 9 and 10 both with approach.Also in Question 9th which algorithm they assume since I believe answer varies according to algorithm as well.In Q...

Sahil Gupta

397 views

Sahil Gupta asked Dec 17, 2014

0 votes

2 answers

3300

based on asymptotics, which of the following is true?

Hcas Hgnis

449 views

Hcas Hgnis asked Dec 17, 2014

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