Recent questions tagged algorithms / GATE Overflow for GATE CSE

0 votes

0 answers

1

Divide and conquer
In quick sort, n numbers the (n/10)th element is selected as pivot using n^2 sortimng time complexity what will be the time complexity of quick sort is..... a)O(nlogn) b)O(n^2) c)O(n^3) d)O(n)

In quick sort, n numbers the (n/10)th element is selected as pivot using n^2 sortimng time complexity what will be the time complexity of quick sort is.....a)O(nlogn)b)O(...

Emankashyap

57 views

Emankashyap asked 6 days ago

2 votes

1 answer

2

algorithms
for (i = 1; i <= N; i++){ for （j= 1;j <= i^2;j=j+i） { //some code} } how is this O(n^2)? explain in detail and simple terms

for (i = 1; i <= N; i++){ for （j= 1;j <= i^2;j=j+i）{ //some code}} how is this O(n^2)? explain in detail and simple terms

SSR17

65 views

SSR17 asked Apr 25

0 votes

1 answer

3

Apriori Algorithm
Consider a Big Bazar scenario where the product set is P = {Rice, Pulse, Oil, Milk, Apple}. The database comprises six transactions where 1 represents the presence of the product and 0 represents the absence of the product. Transaction ID Rice Pulse Oil MIlk Apple t1 1 1 1 0 0 ... t4 1 1 0 1 0 t5 1 1 1 0 1 t6 1 1 1 1 1 Apply Apriori Algorithm and find support, confidence and lift.

Consider a Big Bazar scenario where the product set is P = {Rice, Pulse, Oil, Milk, Apple}. The database comprises six transactions where 1 represents the presence of the...

rahulkarmakar2002

174 views

rahulkarmakar2002 asked Mar 19

1 votes

1 answer

4

Recurrence relation
What is the returned value by the given function below. Algo fun(n) { If(x<=2) return 1; Else { Return fun(n1/2) + n; } } Note : Assume that all the syntax and data type constraints are valid and just check algorithm.

What is the returned value by the given function below.Algo fun(n){ If(x<=2) return 1; Else { Return fun(n1/2) + n; }}Note : Assume that all...

jenilS7

153 views

jenilS7 asked Mar 18

0 votes

0 answers

5

Merge Sort
Calculate the minimum and maximum number of element comparisons involved in 2 way merge sort assuming n is power of 2.

Calculate the minimum and maximum number of element comparisons involved in 2 way merge sort assuming n is power of 2.

Ujjal Das

163 views

Ujjal Das asked Mar 17

0 votes

1 answer

6

Prove that n! = Ω(n^100)

wtquevb123

102 views

wtquevb123 asked Mar 14

0 votes

1 answer

7

Sorting Algorithm
For flag based approach in Bubble sort we can check first by a flag if the list is sorted or not in O(n), and if it is sorted, then no need to sort and the operation ends in Best case = O(n). Why isn't the same concept applicable to selection sort? Why it never comes down from O(n$^2$)?

For flag based approach in Bubble sort we can check first by a flag if the list is sorted or not in O(n), and if it is sorted, then no need to sort and the operation ends...

Mrityudoot

229 views

Mrityudoot asked Mar 7

0 votes

1 answer

8

#algorithm
how many spanning trees are possible for complete graph of 4 vertices

how many spanning trees are possible for complete graph of 4 vertices

Amoljadhav

146 views

Amoljadhav asked Mar 1

0 votes

1 answer

9

Linked List
How can we find the highest element in a singly linked list in O(1)? We are free to use any extra space.

How can we find the highest element in a singly linked list in O(1)? We are free to use any extra space.

Mrityudoot

195 views

Mrityudoot asked Feb 25

0 votes

0 answers

10

In rural Ireland, a century ago, the students had to form a line. The student at the front of the line would be asked to spell a word. If he spelled it correctly, he was allowed to sit down. If not, he received a whack on the hand with a switch and was sent to the end of the line. Suppose that a student could spell correctly 70% of the words in the lesson. What is the probability that the student would be able to sit down before receiving four whacks on the hand? Assume that the master chose the words to be spelled randomly and independently.

tim20

107 views

tim20 asked Feb 22

0 votes

1 answer

11

GATE DS&AI 2024 | Question: 4
Consider performing depth-first search (DFS) on an undirected and unweighted graph $G$ starting at vertex $s$. For any vertex $u$ in $G, d[u]$ is the length of the shortest path from $s$ to $u$. Let $(u, v)$ be an edge in $G$ such that $d[u]<d[v]$ ... from $u$ to $v$ during the above DFS, then $(u, v)$ becomes a $\_\_\_\_\_\_\_\_$ edge. tree cross back gray

Consider performing depth-first search (DFS) on an undirected and unweighted graph $G$ starting at vertex $s$. For any vertex $u$ in $G, d[u]$ is the length o...

Arjun

846 views

Arjun asked Feb 16

0 votes

3 answers

12

GATE DS&AI 2024 | Question: 20
Consider sorting the following array of integers in ascending order using an inplace Quicksort algorithm that uses the last element as the pivot. \begin{array}{|l|l|l|l|l|} \hline 60 & 70 & 80 & 90 & 100 \\ \hline \end{array} The minimum number of swaps performed during this Quicksort is $\_\_\_\_\_\_\_\_$.

Consider sorting the following array of integers in ascending order using an inplace Quicksort algorithm that uses the last element as the pivot.\begin{array}{|l|l|l|l|l|...

Arjun

1.3k views

Arjun asked Feb 16

0 votes

1 answer

13

GATE DS&AI 2024 | Question: 30
Let $F(n)$ denote the maximum number of comparisons made while searching for an entry in a sorted array of size $n$ using binary search. Which ONE of the following options is TRUE? $F(n)=F(\lfloor n / 2\rfloor)+1$ $F(n)=F(\lfloor n / 2\rfloor)+F(\lceil n / 2\rceil)$ $F(n)=F(\lfloor n / 2\rfloor)$ $F(n)=F(n-1)+1$

Let $F(n)$ denote the maximum number of comparisons made while searching for an entry in a sorted array of size $n$ using binary search.Which ONE of the fo...

Arjun

918 views

Arjun asked Feb 16

0 votes

1 answer

14

GATE DS&AI 2024 | Question: 35
Consider the following sorting algorithms: Bubble sort Insertion sort Selection sort Which ONE among the following choices of sorting algorithms sorts the numbers in the array $[4,3,2,1,5]$ in increasing order after exactly two passes over the array? $\text{(i)}$ only $\text{(iii)}$ only $\text{(i)}$ and $\text{(iii)}$ only $\text{(ii)}$ and $\text{(iii)}$ only

Consider the following sorting algorithms:Bubble sortInsertion sortSelection sortWhich ONE among the following choices of sorting algorithms sorts the numbers in the arra...

Arjun

911 views

Arjun asked Feb 16

0 votes

1 answer

15

GATE DS&AI 2024 | Question: 41
Consider the directed acyclic graph (DAG) below: Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG? $\text{P Q R S T U V}$ $\text{P R Q V SUT}$ $\text{P Q R S V U T}$ $\text{P R Q S V T U}$

Consider the directed acyclic graph (DAG) below:Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the...

Arjun

759 views

Arjun asked Feb 16

3 votes

4 answers

16

GATE CSE 2024 | Set 2 | Question: 5
Let $\text{T(n)}$ be the recurrence relation defined as follows: \[ \begin{array}{l} T(0)=1, \\ T(1)=2, \text { and } \\ T(n)=5 T(n-1)-6 T(n-2) \text { for } n \geq 2 \end{array} \] Which one of the following statements is TRUE? $T(n)=\Theta\left(2^{n}\right)$ $T(n)=\Theta\left(n 2^{n}\right)$ $T(n)=\Theta\left(3^{n}\right)$ $T(n)=\Theta\left(n 3^{n}\right)$

Let $\text{T(n)}$ be the recurrence relation defined as follows:\[\begin{array}{l}T(0)=1, \\T(1)=2, \text { and } \\T(n)=5 T(n-1)-6 T(n-2) \text { for } n ...

Arjun

2.7k views

Arjun asked Feb 16

1 votes

2 answers

17

GATE CSE 2024 | Set 2 | Question: 25
Let $\text{A}$ be an array containing integer values. The distance of $\text{A}$ is defined as the minimum number of elements in $\text{A}$ that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array $[2,5,3,1,4,2,6]$ is ___________.

Let $\text{A}$ be an array containing integer values. The distance of $\text{A}$ is defined as the minimum number of elements in $\text{A}$ that must be replaced with ano...

Arjun

2.6k views

Arjun asked Feb 16

3 votes

2 answers

18

GATE CSE 2024 | Set 2 | Question: 32
Consider an array $\mathrm{X}$ that contains $\mathrm{n}$ positive integers. A subarray of $\mathrm{X}$ is defined to be a sequence of array locations with consecutive indices. The $\mathrm{C}$ code snippet given below has been written to compute the length of the longest ... $\text{(P) } \text{len} 2+1$ $\text{(Q) } \text{len} 1+1$

Consider an array $\mathrm{X}$ that contains $\mathrm{n}$ positive integers. A subarray of $\mathrm{X}$ is defined to be a sequence of array locations with co...

Arjun

2.1k views

Arjun asked Feb 16

1 votes

1 answer

19

GATE CSE 2024 | Set 2 | Question: 49
The number of distinct minimum-weight spanning trees of the following graph is

The number of distinct minimum-weight spanning trees of the following graph is

Arjun

2.1k views

Arjun asked Feb 16

3 votes

1 answer

20

GATE CSE 2024 | Set 1 | Question: 7
Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The ... $\Omega(N)$ but not $\mathrm{O}(N)$ neither $\mathrm{O}(N)$ nor $\Omega(N)$

Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single...

Arjun

3.5k views

Arjun asked Feb 16

1 votes

1 answer

21

GATE CSE 2024 | Set 1 | Question: 31
An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array? $82,90,101$ $82,11,93$ $131,11,93$ $131,111,90$

An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array?$...

Arjun

2.5k views

Arjun asked Feb 16

3 votes

3 answers

22

GATE CSE 2024 | Set 1 | Question: 32
Consider the following recurrence relation: $T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$ Which one of the following options is CORRECT? $T(n)=\Theta(n \log \log n)$ $T(n)=\Theta(n \log n)$ $T(n)=\Theta\left(n^2 \log n\right)$ $T(n)=\Theta\left(n^2 \log \log n\right)$

Consider the following recurrence relation:$T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$Whic...

Arjun

2.2k views

Arjun asked Feb 16

4 votes

2 answers

23

GATE CSE 2024 | Set 1 | Question: 35
Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first search $\text{(BFS)}$ tree in $G$, rooted at $v$. Which of the following ... the tree $T$ There are no forward-edge in $G$ with respect to the tree $T$ The only edges in $G$ are the edges in $T$

Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth fir...

Arjun

3.5k views

Arjun asked Feb 16

0 votes

0 answers

24

GATE 2024
Consider an n element array which is to be sorted either in ascending or descending order. The given restriction is only one pass will be used for completely sorting the array and an element can compare with only it's adjacent pair. What will be the worst time complexity? Is this related to bubble sort algorithm or not?

Consider an n element array which is to be sorted either in ascending or descending order. The given restriction is only one pass will be used for completely sorting the ...

TusharRana

419 views

TusharRana asked Feb 11

5 votes

1 answer

25

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 17
Consider the following function. If $n$ and $\mathrm{k}$ are positive integers, then the least value of $\mathrm{k}$ such that $\mathrm{f}(\mathrm{k})>n$ is approximately $\log _2\left(\log _2 n\right)$ $\log _2 n$ $n \log _2 n$ $2^n$

Consider the following function.If $n$ and $\mathrm{k}$ are positive integers, then the least value of $\mathrm{k}$ such that $\mathrm{f}(\mathrm{k})>n$ is approximately$...

GO Classes

513 views

GO Classes asked Feb 5

4 votes

2 answers

26

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 18
Bob writes down a number between 1 and 1,000. Mary must identify that number by asking "yes/no" questions of Bob. Mary knows that Bob always tells the truth. If Mary uses an optimal strategy then she will determine that answer at the end of exactly how many questions on the worst case? 999 500 32 10

Bob writes down a number between 1 and 1,000. Mary must identify that number by asking "yes/no" questions of Bob. Mary knows that Bob always tells the truth. If Mary uses...

GO Classes

529 views

GO Classes asked Feb 5

4 votes

1 answer

27

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 19
Which of the following frequencies for A,B,C and D can generate the following Huffman tree? (Select all that apply.) $p_A=0.4, p_B=0.3, p_C=0.2, p_D=0.1$ $p_A=0.35, p_B=0.25, p_C=0.2, p_D=0.2$ $p_A=0.25, p_B=0.25, p_C=0.25, p_D=0.25$ $p_A=0.2, p_B=0.35, p_C=0.2, p_D=0.25$

Which of the following frequencies for A,B,C and D can generate the following Huffman tree? (Select all that apply.)$p_A=0.4, p_B=0.3, p_C=0.2, p_D=0.1$$p_A=0.35, p_B=0.2...

GO Classes

486 views

GO Classes asked Feb 5

2 votes

2 answers

28

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 20
Consider the following array$: [32, 33, 5, 2, 14, -4, 22, 39, 34, -9].$ ... sorting algorithms could we possibly have applied? Merge sort (top-down approach) Bubble sort Quicksort (Using First element as pivot) Insertion sort

Consider the following array$: [32, 33, 5, 2, 14, -4, 22, 39, 34, -9].$ We apply a certain sorting algorithm and observe that the array has been modified to $[2, 5, 14, 3...

GO Classes

605 views

GO Classes asked Feb 5

5 votes

1 answer

29

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 46
We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in $n$. Unfortunately, a significant flaw was discovered in $Q(m)$, and it had to be replaced by $R(m)$, which runs in exponential ... $P(n)$ runs in polynomial time in $n$ if, for each call $Q(m),m \underline<\log \;n.$

We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in $n$. Unfortunately, a significant flaw was discovered in $Q(m)$...

GO Classes

450 views

GO Classes asked Feb 5

3 votes

0 answers

30

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 47
A $\text{stable sort}$ preserves the order of values that are equal with respect to the comparison function. We have a list of three-dimensional points $[(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)].$ We sort these in ascending order by the ... $[(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$

A $\text{stable sort}$ preserves the order of values that are equal with respect to the comparison function. We have a list of three-dimensional points$[(7, 1, 8),(3, 5, ...

GO Classes

217 views

GO Classes asked Feb 5

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