Recent questions tagged algorithms / GATE Overflow for GATE CSE

1 votes

2 answers

241

GO Classes 2023 | IIITH Mock Test 1 | Question: 11
Suppose that a MST of the following edge-weighted graph contains the edges with weights $x, y$, and $z$. What will be the maximum value of $x+y+z?$ $200$ $250$ $300$ $350$

Suppose that a MST of the following edge-weighted graph contains the edges with weights $x, y$, and $z$.What will be the maximum value of $x+y+z?$$200$$250$$300$$350$

GO Classes

1.2k views

GO Classes asked Mar 26, 2023

7 votes

1 answer

242

GO Classes 2023 | IIITH Mock Test 1 | Question: 12
A list of $n$ arrays, each of length $n$, is passed to an algorithm like merge-sort. The algorithm recursively divides a set of arrays into two parts until there are only two arrays. If there are two arrays, then, as a base case, the algorithm combines or merges both in cost of ... $T(n)=2 T(n / 2)+n$ $T(n)=2 T(n / 2)+n^ 3$ None of these

A list of $n$ arrays, each of length $n$, is passed to an algorithm like merge-sort. The algorithm recursively divides a set of arrays into two parts until there are only...

GO Classes

1.4k views

GO Classes asked Mar 26, 2023

3 votes

0 answers

243

GO Classes 2023 | IIITH Mock Test 1 | Question: 13
Arrange the following functions in their increasing order of growth. In options $\log ^{2} n$ means $(\log n)^{2}$ $\log (n !), \log ^{2} n, (\lg n) !, e^{n}$ $\log (n !), \log ^{2} n, e^{n}, (\lg n) !$ $\log ^{2} n, \log (n !), (\lg n) !, e^{n}$ $\log ^{2} n, (\lg n) !, \log (n !), e^{n}$

Arrange the following functions in their increasing order of growth. In options $\log ^{2} n$ means $(\log n)^{2}$$\log (n !), \log ^{2} n, (\lg n) !, e^{n}$$\log (n !)...

GO Classes

840 views

GO Classes asked Mar 26, 2023

3 votes

4 answers

244

GO Classes 2023 | IIITH Mock Test 1 | Question: 16
Consider a hash table of $9$ slots implemented with linear probing. Suppose we insert $2$ elements in a sequence to a hash table with a simple uniform hashing assumption. What is the probability that we end up with $2$ consecutive slots of the hash table filled? ... $1/2$ $1/3$ $1/4$ $2/3$

Consider a hash table of $9$ slots implemented with linear probing. Suppose we insert $2$ elements in a sequence to a hash table with a simple uniform hashing assumption....

GO Classes

1.2k views

GO Classes asked Mar 26, 2023

1 votes

1 answer

245

GO Classes 2023 | IIITH Mock Test 1 | Question: 43
Recall the Partition subroutine that we used in QuickSort. Suppose that the following array has just been partitioned around some pivot element $: 3,1,2,4,5,8,7,6,9.$ Which of these element(s) could have been the pivot element? $4$ $5$ $2$ $9$

Recall the Partition subroutine that we used in QuickSort. Suppose that the following array has just been partitioned around some pivot element $: 3,1,2,4,5,8,7,6,9.$Whic...

GO Classes

1.0k views

GO Classes asked Mar 26, 2023

2 votes

1 answer

246

GO Classes 2023 | IIITH Mock Test 1 | Question: 45
Assume you have two positive functions $f$ and $g$ such that $f(n)$ is in $O(g(n))$. For each of the following statements, decide which one(s) is/are always TRUE. $2^{f(n)}$ is $O\left(2^{g(n)}\right)$ $f(n)^{2}$ is $O\left(g(n)^{2}\right)$ $f(n)=O\left((f(n))^{2}\right)$ $g(n)=\Omega(g(n))$

Assume you have two positive functions $f$ and $g$ such that $f(n)$ is in $O(g(n))$. For each of the following statements, decide which one(s) is/are always TRUE.$2^{f(n)...

GO Classes

1.0k views

GO Classes asked Mar 26, 2023

7 votes

1 answer

247

GO Classes 2023 | IIITH Mock Test 1 | Question: 50
For which of the following functions $f(n)$ and $g(n),$ it holds $:f(n)=O(g(n)).$ Every $\log$ below is base $2.$ $f(n)=2^{k \log n}\;, \quad g(n)=n^k$ $f(n)=2^n\;, \quad g(n)=2^{2 n}$ ... $f(n)=2^{\sqrt{\log n}}\;, \quad g(n)= (\log n)^{100}$

For which of the following functions $f(n)$ and $g(n),$ it holds $:f(n)=O(g(n)).$ Every $\log$ below is base $2.$$f(n)=2^{k \log n}\;, \quad g(n)=n^k$$f(n)=2^n\;, \quad g...

GO Classes

1.2k views

GO Classes asked Mar 26, 2023

3 votes

0 answers

248

TIFR CSE 2023 | Part B | Question: 3
Given a set $\mathcal{F}$ of intervals $\left(s_{i}, t_{i}\right)_{i=1}^{n}$ on the integer line (assume all $s_{i}, t_{i}$ are distinct), a subset $S$ of $\mathcal{F}$ is said to be independent if no two intervals in $S$ have a non-empty ... $\text{(C1)}$ Choices $\text{(C1)}$ and $\text{(C2)},$ but not choice $\text{(C3)}$

Given a set $\mathcal{F}$ of intervals $\left(s_{i}, t_{i}\right)_{i=1}^{n}$ on the integer line (assume all $s_{i}, t_{i}$ are distinct), a subset $S$ of $\mathcal{F}$ i...

admin

396 views

admin asked Mar 14, 2023

3 votes

1 answer

249

TIFR CSE 2023 | Part B | Question: 6
What is the solution to the following recurrence? \[ T(n)=\left\{\begin{array}{ll} 1 & \text { if } n \leq 10, \\ \sqrt{n} \cdot T(\sqrt{n})+n & \text { if } n>10. \end{array}\right. \] $T(n)=\Theta\left(n^{2}\right)$ $T(n)=\Theta(n \log n)$ $T(n)=\Theta(n \sqrt{\log n})$ $T(n)=\Theta(n \log \log n)$ None of the above

What is the solution to the following recurrence?\[T(n)=\left\{\begin{array}{ll}1 & \text { if } n \leq 10, \\\sqrt{n} \cdot T(\sqrt{n})+n & \text { if } n>10.\end{array}...

admin

586 views

admin asked Mar 14, 2023

0 votes

0 answers

250

self doubt
Determine the number of spanning tree in the following graph ?

Determine the number of spanning tree in the following graph ?

Çșȇ ʛấẗẻ

381 views

Çșȇ ʛấẗẻ asked Mar 10, 2023

0 votes

0 answers

251

Self Doubt
Determine the number of the spanning treess in the following graph ???

Determine the number of the spanning treess in the following graph ???

Çșȇ ʛấẗẻ

239 views

Çșȇ ʛấẗẻ asked Mar 10, 2023

0 votes

0 answers

252

Self doubt
Determine the number of the spanning treess in the following graph ???

Determine the number of the spanning treess in the following graph ???

Çșȇ ʛấẗẻ

333 views

Çșȇ ʛấẗẻ asked Mar 10, 2023

1 votes

1 answer

253

Spanning Tree
Determine the number of the spanning treess in the following graph ???

Determine the number of the spanning treess in the following graph ???

Çșȇ ʛấẗẻ

421 views

Çșȇ ʛấẗẻ asked Mar 10, 2023

1 votes

2 answers

254

Chose the correct big- Θ expression to describe: T(N) = T(N / 2) + Log(N/2); T(1) = 1
I

I

ahmed malik

462 views

ahmed malik asked Mar 4, 2023

11 votes

3 answers

255

GATE CSE 2023 | Question: 10
An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash ... a carefully chosen constant. Universal hashing method. If $k$ is a prime number, use Division method. Otherwise, use Multiplication method.

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be th...

admin

9.8k views

admin asked Feb 15, 2023

10 votes

4 answers

256

GATE CSE 2023 | Question: 19
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 $\text{TRUE}?$ $f \in O(g)$ $f \in \Omega(g)$ $f \in o(g)$ $f \in \Theta(g)$

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 $\text{TRUE}?$$f \in O(g)$$f \in \Omega(g)$$f...

admin

9.8k views

admin asked Feb 15, 2023

21 votes

4 answers

257

GATE CSE 2023 | Question: 44
Consider functions $\textsf{Function_1}$ and $\textsf{Function_2}$ ... $f_{1}(n) \in \omega\left(f_{2}(n)\right)$ $f_{1}(n) \in O(n)$

Consider functions $\textsf{Function_1}$ and $\textsf{Function_2}$ expressed in pseudocode as follows:Function_1 | Function_2 while n 1 do | for i = 1 to 100 * n do for ...

admin

11.8k views

admin asked Feb 15, 2023

10 votes

1 answer

258

GATE CSE 2023 | Question: 46
Let $U=\{1,2,3\}$. Let $2^{U}$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^{U}$. For any $A, B \in 2^{U},(A, B)$ is an edge in $G$ if and only if (i) $A \neq B$, and (ii) ... $A$ is denoted by $\mathcal{B}(A)$. If $\emptyset$ denotes the empty set, then the cardinality of $\mathcal{B}(\emptyset)$ is ______________.

Let $U=\{1,2,3\}$. Let $2^{U}$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^{U}$. For any $A, B \in 2^{U},(A, B)$ is an edge in $G$...

admin

6.5k views

admin asked Feb 15, 2023

0 votes

0 answers

259

GATE CSE 2023 | Memory Based Question: 37
Time complexity f( ) { while(n>1) { for (i = 1 to n) { } n = n/2 } } g ( ) { for (i = 1 to 100n) { } } $f(x)=O(g(x))$ $f(x)=\theta(g(x))$ $f(x)=o(g(x))$ $f(x)=\omega(g(x))$

Time complexity f( ) { while(n>1) { for (i = 1 to n) { } n = n/2 } } g ( ) { for (i = 1 to 100n) { } } $f(x)...

GO Classes

1.5k views

GO Classes asked Feb 5, 2023

3 votes

1 answer

260

Number of possible permutations that can be obtained using stack for input seq
Number of possible permutations that can be obtained using stack if the input sequence is 1, 2, 3, 4, 5 (in the order) is

Number of possible permutations that can be obtained using stack if the input sequence is 1, 2, 3, 4, 5 (in the order) is

h4kr

668 views

h4kr asked Jan 31, 2023

0 votes

1 answer

261

TestBook TestSeries Finding number of records under join of 2 tables
Assume a relation R' having 200 records. These records are stored in blocks having block factor as 20. Consider another relation S' having 120 records and all these records are stored in 30 blocks. These two tables have to be joined ... the total number of block access required to join R and S ? A. 2430 B. 6010 C. 6120 D. 1230

Assume a relation ‘R’ having 200 records. These records are stored in blocks having block factor as 20. Consider another relation ‘S’ having 120 records and all t...

Sahil_Lather

355 views

Sahil_Lather asked Jan 29, 2023

0 votes

0 answers

262

TestBook TestSeries Optimal Binary Search Tree Question
Construct OBST with the identifier set (a1, a2, a3) =(end , goto, print) with p(1..3) = (0.05, 0.2, 0.1) and q(0..3) = (0.2, 0.1,0.2, 0.05) What is the cost of a OBST ? What are the nodes present in the 2nd level of OBST if the root is present in level one ? 2.55 , print , goto 2.45 , goto , end 2.15, end, print 2.7, end, goto

Construct OBST with the identifier set (a1, a2, a3) =(end , goto, print) with p(1..3) = (0.05, 0.2, 0.1) and q(0..3) = (0.2, 0.1,0.2, 0.05)What is the cost of a OBST ? ...

Sahil_Lather

471 views

Sahil_Lather asked Jan 28, 2023

0 votes

1 answer

263

TestBook testseries question to find max weight of MST
A complete graph G with 5 nodes has positive weight edges, each node has a distinct weight with an integer value and maximum weight is equal to number of edges in G. What can be the maximum weight of minimum spanning tree for graph G?

A complete graph G with 5 nodes has positive weight edges, each node has a distinct weight with an integer value and maximum weight is equal to number of edges in G.What ...

Sahil_Lather

432 views

Sahil_Lather asked Jan 28, 2023

0 votes

0 answers

264

TestBook TestSeries question to find number of paths in directed graph
Consider the following directed graph and assume the number of paths to reach to itself i.e. N(A) = 1. Number of paths from A to K are __

Consider the following directed graph and assume the number of paths to reach to itself i.e. N(A) = 1.Number of paths from A to K are __

Sahil_Lather

237 views

Sahil_Lather asked Jan 28, 2023

0 votes

0 answers

265

TestBook testSeries dynamic programming and np problem question
Consider the following statements, which of the statement(s) is/are FALSE? The running time of dynamic programming algorithm is always θ (p) where p is number of subproblems When a recurrence relation has cyclic dependency, it is ... memorization If a problem X can be reduced to a known NP hard problem, then X must be NP-hard

Consider the following statements, which of the statement(s) is/are FALSE?The running time of dynamic programming algorithm is always θ (p) where p is number of subprobl...

Sahil_Lather

390 views

Sahil_Lather asked Jan 28, 2023

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