Recent questions tagged algorithms / GATE Overflow for GATE CSE

32 votes

4 answers

3151

TIFR CSE 2014 | Part B | Question: 11
Consider the following recurrence relation: $T\left(n\right)= \begin{cases} T\left(\frac{n}{k}\right)+ T\left(\frac{3n}{4}\right)+ n & \text{if } n \geq 2 \\ 1& \text{if } n=1 \end{cases}$ Which of the following statements is FALSE? $T(n)$ is $O(n^{3/2})$ ... $k=4$. $T(n)$ is $O(n \log n)$ when $k=5$. $T(n)$ is $O(n)$ when $k=5$.

Consider the following recurrence relation:$T\left(n\right)=\begin{cases}T\left(\frac{n}{k}\right)+ T\left(\frac{3n}{4}\right)+ n & \text{if } n \geq 2 \\ 1& \text{if }...

makhdoom ghaya

5.6k views

makhdoom ghaya asked Nov 20, 2015

23 votes

2 answers

3152

TIFR CSE 2014 | Part B | Question: 10
Given a set of $n$ distinct numbers, we would like to determine both the smallest and the largest number. Which of the following statements is TRUE? These two elements can be determined using $O\left(\log^{100}n\right)$ ... comparisons do not suffice, however these two elements can be determined using $2(n - 1)$ comparisons. None of the above.

Given a set of $n$ distinct numbers, we would like to determine both the smallest and the largest number. Which of the following statements is TRUE?These two elements can...

makhdoom ghaya

5.4k views

makhdoom ghaya asked Nov 19, 2015

49 votes

7 answers

3153

TIFR CSE 2014 | Part B | Question: 9
Given a set of $n$ distinct numbers, we would like to determine the smallest three numbers in this set using comparisons. Which of the following statements is TRUE? These three elements can be determined using $O\left(\log^{2}n\right)$ ... $O(n)$ comparisons. None of the above.

Given a set of $n$ distinct numbers, we would like to determine the smallest three numbers in this set using comparisons. Which of the following statements is TRUE?These ...

makhdoom ghaya

10.0k views

makhdoom ghaya asked Nov 19, 2015

28 votes

3 answers

3154

TIFR CSE 2014 | Part B | Question: 8
Which of these functions grows fastest with $n$? $e^{n}/n$. $e^{n-0.9 \log n}$. $2^{n}$. $\left(\log n\right)^{n-1}$. None of the above.

Which of these functions grows fastest with $n$?$e^{n}/n$.$e^{n-0.9 \log n}$.$2^{n}$.$\left(\log n\right)^{n-1}$.None of the above.

makhdoom ghaya

4.6k views

makhdoom ghaya asked Nov 19, 2015

19 votes

5 answers

3155

TIFR CSE 2014 | Part B | Question: 7
Which of the following statements is TRUE for all sufficiently large $n$? $\displaystyle \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}} < n^{1/4}$ $\displaystyle 2^{\sqrt{\log n}} < n^{1/4} < \left(\log n\right)^{\log\log n}$ ... $\displaystyle 2^{\sqrt{\log n}} < \left(\log n\right)^{\log\log n} < n^{1/4}$

Which of the following statements is TRUE for all sufficiently large $n$?$\displaystyle \left(\log n\right)^{\log\log n} < 2^{\sqrt{\log n}} < n^{1/4}$ $\displaystyle 2^{...

makhdoom ghaya

4.0k views

makhdoom ghaya asked Nov 19, 2015

31 votes

3 answers

3156

TIFR CSE 2014 | Part B | Question: 6
Consider the problem of computing the minimum of a set of $n$ distinct numbers. We choose a permutation uniformly at random (i.e., each of the n! permutations of $\left \langle 1,....,n \right \rangle$ is chosen with probability $(1/n!)$ and we inspect the numbers in the order ... of times MIN is updated? $O (1)$ $H_{n}=\sum ^{n}_{i=1} 1/i$ $\sqrt{n}$ $n/2$ $n$

Consider the problem of computing the minimum of a set of $n$ distinct numbers. We choose a permutation uniformly at random (i.e., each of the n! permutations of $\left \...

makhdoom ghaya

2.7k views

makhdoom ghaya asked Nov 19, 2015

31 votes

1 answer

3157

TIFR CSE 2014 | Part B | Question: 5
Let $G = (V,E)$ be an undirected connected simple (i.e., no parallel edges or self-loops) graph with the weight function $w: E \rightarrow \mathbb{R}$ on its edge set. Let $w(e_{1}) < w(e_{2}) < · · · < w(e_{m})$ ... $w_{i} = w(e_{i})$ by its square $w^{2}_{i}$ , then $T$ must still be a minimum spanning tree of this new instance.

Let $G = (V,E)$ be an undirected connected simple (i.e., no parallel edges or self-loops) graph with the weight function $w: E \rightarrow \mathbb{R}$ on its edge set. Le...

makhdoom ghaya

3.2k views

makhdoom ghaya asked Nov 19, 2015

35 votes

4 answers

3158

TIFR CSE 2014 | Part B | Question: 4
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? cost$(a, b) \geq 6$. cost$(b, e) \geq 5$. cost$(e, f) \geq 5$. cost$(a, d) \geq 4$. cost$(b, c) \geq 4$.

Consider the following undirected graph with some edge costs missing.Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequa...

makhdoom ghaya

5.1k views

makhdoom ghaya asked Nov 19, 2015

29 votes

2 answers

3159

TIFR CSE 2014 | Part B | Question: 3
Consider the following directed graph. Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree edges is $T$, the number of back edges is $B$ and the number of ... $B = 1$, $C = 2$, and $T = 3$. $B = 2$, $C = 2$, and $T = 1$.

Consider the following directed graph.Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alph...

makhdoom ghaya

5.3k views

makhdoom ghaya asked Nov 19, 2015

8 votes

3 answers

3160

TIFR CSE 2014 | Part B | Question: 2
Consider the following code. def brian(n): count = 0 while ( n ! = 0 ) n = n & ( n-1 ) count = count + 1 return count Here $n$ is meant to be an unsigned integer. The operator & considers its arguments in binary and ... $n$. The result depends on the number of bits used to store unsigned integers.

Consider the following code.def brian(n): count = 0 while ( n ! = 0 ) n = n & ( n-1 ) count = count + 1 return countHere $n$ is meant to be an unsigned integer. The opera...

makhdoom ghaya

2.2k views

makhdoom ghaya asked Nov 19, 2015

0 votes

2 answers

3161

Maximum depth of recursion tree
Given answer: C Please explain

Given answer: CPlease explain

shikharV

502 views

shikharV asked Nov 18, 2015

0 votes

3 answers

3162

Question on C programming lanuage
Why 'count' variable value doesn't set to 0 on every call to 'incr' function?

Why 'count' variable value doesn't set to 0 on every call to 'incr' function?

shikharV

2.0k views

shikharV asked Nov 18, 2015

0 votes

1 answer

3163

Output of following code
Given answer: 1990 Please explain

Given answer: 1990Please explain

shikharV

958 views

shikharV asked Nov 18, 2015

4 votes

1 answer

3164

Comparing Time complexities
Consider the following functions: $\begin{array}{rcl|rcl} F(n) &=& n^{\,4/3} & G(n) &=& 2^{\large \,2^{\,\LARGE n}}\\[1em] H(n) &=& 2^{\large \,n^{\,\LARGE 2}} & I(n) &=& n!\\[1em] J(n) &=& 2^{\,n} \end{array}$ Which of ... $F(n) < J(n) < I(n) < G(n) < H(n)$ $I(n) = O \Bigl ( H(n) \Bigr )$

Consider the following functions:$$\begin{array}{rcl|rcl}F(n) &=& n^{\,4/3} &G(n) &=& 2^{\large \,2^{\,\LARGE n}}\\[1em]H(n) &=& 2^{\large \,n^{\,\LARGE 2}} &I(n) &=& n!\...

shikharV

1.8k views

shikharV asked Nov 17, 2015

0 votes

3 answers

3165

Finding Time complexity
Given answer: B Please explain

Given answer: BPlease explain

shikharV

2.1k views

shikharV asked Nov 17, 2015

2 votes

3 answers

3166

Master theorem details?
There are different versions of master theorem available. I want to know whether the version given in Cormen book is sufficient for GATE?

There are different versions of master theorem available. I want to know whether the version given in Cormen book is sufficient for GATE?

shikharV

2.7k views

shikharV asked Nov 17, 2015

2 votes

0 answers

3167

Find the recurrence

Payal Rastogi

352 views

Payal Rastogi asked Nov 15, 2015

2 votes

1 answer

3168

The Number of Comparisons is :

Payal Rastogi

1.4k views

Payal Rastogi asked Nov 15, 2015

2 votes

2 answers

3169

The Solution to the recurrence is :

Payal Rastogi

566 views

Payal Rastogi asked Nov 15, 2015

0 votes

2 answers

3170

Problem on DFS
Answer given: C Please explain

Answer given: CPlease explain

shikharV

825 views

shikharV asked Nov 15, 2015

5 votes

5 answers

3171

Number of moves of smallest disc in tower of Hanoi
______ is the number of moves of the smallest disc in Tower of Hanoi implementation where the tower consisting of 17 discs (numbered from 0 to 16) Answer given: $2^{16}$ = 65536 Please explain

______ is the number of moves of the smallest disc in Tower of Hanoi implementation where the tower consisting of 17 discs (numbered from 0 to 16)Answer given: $2^{16}$ ...

shikharV

3.2k views

shikharV asked Nov 15, 2015

1 votes

1 answer

3172

Finding time complexity of Dynamic programming problem
The answer to the above problem is A but I am expecting it to be D as constant amount of work is required to solve each subproblem.

The answer to the above problem is A but I am expecting it to be D as constant amount of work is required to solve each subproblem.

shikharV

1.0k views

shikharV asked Nov 15, 2015

2 votes

2 answers

3173

What is an Inversion ??

Payal Rastogi

812 views

Payal Rastogi asked Nov 14, 2015

1 votes

1 answer

3174

Time and Space Complexity of the following function

Payal Rastogi

1.2k views

Payal Rastogi asked Nov 14, 2015

1 votes

1 answer

3175

Complexity of the following program segment

Payal Rastogi

732 views

Payal Rastogi asked Nov 13, 2015

2 votes

1 answer

3176

Determine the Time Complexity

Payal Rastogi

347 views

Payal Rastogi asked Nov 13, 2015

1 votes

1 answer

3177

Asymtotic Analysis

Payal Rastogi

430 views

Payal Rastogi asked Nov 13, 2015

1 votes

1 answer

3178

Solve for x :
I have an equation $X\log(X)=\log N$. Can anybody solve for $X$ from this equation?

I have an equation $X\log(X)=\log N$. Can anybody solve for $X$ from this equation?

Riya Roy(Arayana)

437 views

Riya Roy(Arayana) asked Nov 9, 2015

34 votes

4 answers

3179

TIFR CSE 2013 | Part B | Question: 20
Suppose $n$ processors are connected in a linear array as shown below. Each processor has a number. The processors need to exchange numbers so that the numbers eventually appear in ascending order (the processor $\rm P1$ should have the minimum value and the the ... $n^2$ steps $n$ steps $n^{1.5}$ steps The algorithm is not guaranteed to sort

Suppose $n$ processors are connected in a linear array as shown below. Each processor has a number. The processors need to exchange numbers so that the numbers eventually...

makhdoom ghaya

3.1k views

makhdoom ghaya asked Nov 8, 2015

18 votes

6 answers

3180

TIFR CSE 2013 | Part B | Question: 18
Let $S$ be a set of numbers. For $x \in S$, the rank of $x$ is the number of elements in $S$ that are less than or equal to $x$. The procedure $\textsf{Select}(S, r)$ takes a set $S$ of numbers and a rank $r\left(1 \leq r \leq |S|\right)$ and returns the ... $|S|$ constant · $|S||R|$ constant · $|R| \log |S|$ constant · $|S|(1 + \log |R|)$

Let $S$ be a set of numbers. For $x \in S$, the rank of $x$ is the number of elements in $S$ that are less than or equal to $x$. The procedure $\textsf{Select}(S, r)$ tak...

makhdoom ghaya

2.5k views

makhdoom ghaya asked Nov 8, 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