Recent questions in Algorithms - GATE Overflow

GATE CSE

For all GATE CSE Questions

First time here? Checkout the FAQ!

x

0 votes

0 answers

1

Sorting
Recommend sorts for the following scenario: i) A file of 15 records where each record is of a large size but the keys are simple. ii) A large file of about 100 records. iii) A file of 30 records where the records and keys are comparable in size. X: insertion sort Y: quick ... : Z C) i): Y, ii): Y , iii): X D) i): Z, ii): Y , iii): X Please provide explanation.

asked 6 hours ago in Algorithms by MiNiPanda Junior (567 points) | 6 views

+1 vote

1 answer

2

doubt
https://gateoverflow.in/30720/tifr2016-b-7 the above question is already discussed but still am not clear enuf can someone help

asked 7 hours ago in Algorithms by A_i_$_h Boss (8.4k points) | 17 views

0 votes

0 answers

3

union find
Is time complexity of union find algo on an undirected graph G with V vertices and E edges O(E) ?

asked 13 hours ago in Algorithms by A_i_$_h Boss (8.4k points) | 3 views

+1 vote

1 answer

4

CLR 3rd Edition page no. 42 Q.n. c

asked 1 day ago in Algorithms by ashwina Active (1.2k points) | 18 views

+2 votes

0 answers

5

DFS: certain nodes not pushed to the stack.

asked 2 days ago in Algorithms by Shubhanshu Boss (9.1k points) | 25 views

0 votes

2 answers

6

Self Doubt
What will be the time complexity of A() { int i,j,k,n; for(i=1;i<=n;i++) { for(j=1;j<=(i^2);j++) { for(k=1;k<=(n/2);k++) { printf("ABCD"); } } } }

asked 2 days ago in Algorithms by Manish Chetwani (209 points) | 27 views

0 votes

1 answer

7

Self Doubt
What will be the time complexity of the following code? A() { int i,j,k,n; for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { for(k=1;k<=100;k++) { printf("ABCD"); } } } }

asked 2 days ago in Algorithms by Manish Chetwani (209 points) | 12 views

+2 votes

1 answer

8

analysis-of-algorithms
If f(n) = O(g(n)) then is it always true g(n) = (f(n)) ??? please explain.

asked 3 days ago in Algorithms by mohit kumar 5 (269 points) | 24 views

+1 vote

0 answers

9

Algo:- Nuts and bolts

asked 3 days ago in Algorithms by rahul sharma 5 Veteran (15k points) | 62 views

+3 votes

1 answer

10

Algo: Time complexity
T(n) = 4T(n/2) + n2.$\sqrt{2}$ In thetha notation?

asked 4 days ago in Algorithms by rahul sharma 5 Veteran (15k points) | 48 views

+1 vote

1 answer

11

Modified form of GATE1996_2.15
Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot i) 1,2,3,…n ii) n,n−1,n−2,…,2,1 Let S1 and S2 be the number of swaps made for the inputs (i) and (ii) respectively. Then, i) How is S1 and S2 related ? ii) How will the answer change if the pivot is changed to middle element ?

asked 4 days ago in Algorithms by rishi71662data4 Active (1.3k points) | 23 views

0 votes

1 answer

12

complexity
1.(n + a)b = $\Omega$(nb) for all real numbers a , b >0 2.na+1=theta(nb) iff a=b for all real numbers a , b>0 which is true? Acyclic graph directory structure is more flexible than simple tree structure - true or false

asked 5 days ago in Algorithms by A_i_$_h Boss (8.4k points) | 23 views

+2 votes

2 answers

13

time complexity
A) T(n) = 2T(root(n)) + 1 ; n>2 T(n) =1 ; 0 < n <= 2 B) f(n) =n g(n) = n(1+sin n) where n is positive integer which is true? 1.f(n) = O(g(n)) 2.f(n) = $\Omega$(g(n))

asked 6 days ago in Algorithms by A_i_$_h Boss (8.4k points) | 59 views

0 votes

0 answers

14

Time complexity
[closed]

asked Oct 15 in Algorithms by ashwina Active (1.2k points) | 45 views

0 votes

1 answer

15

asked Oct 15 in Algorithms by ashwina Active (1.2k points) | 55 views

0 votes

0 answers

16

Self Doubt ( Decrease key operation )

asked Oct 15 in Algorithms by Hitoshi (15 points) | 30 views

+1 vote

2 answers

17

Aymptotic notation
Consider $\sum_{i=0}^n{}$ i3 =x.what can be X 1.theta(n4) 2.theta(n5) 3.O(n5) 4.$\Omega$(n3)

asked Oct 15 in Algorithms by A_i_$_h Boss (8.4k points) | 42 views

+2 votes

1 answer

18

Asymptotic time order

asked Oct 15 in Algorithms by ashwina Active (1.2k points) | 43 views

0 votes

0 answers

19

Spanning Tree
[closed]

asked Oct 15 in Algorithms by ashwina Active (1.2k points) | 10 views

0 votes

0 answers

20

Algo doubt
Assume f(n) and g(n) are two functions such that f (n)=O(g(n)) which of the following always hold F(n) = O (f(n)2) F(n) = Ω (f(n)2) G(n) = O (f(n)2) G(n) = Ω (g(n))

asked Oct 15 in Algorithms by Surya Dhanraj Loyal (2.7k points) | 32 views

0 votes

1 answer

21

Algo doubt
iterated logarithmic function is defined as Log*n = 0. If n<=0 1 +log*(logn) if n >1 Which of the following is true? 1) log*n = O(log(logn )) 2)(log*n)!= O(logn) 3)(log*n)^n= O((logn)!) A)1&2 B)1&3 C)2& 3 D)1,2,3

asked Oct 15 in Algorithms by Surya Dhanraj Loyal (2.7k points) | 28 views

+1 vote

2 answers

22

Alo doubt
Complexity of equation - T(n)=. 2T(n-1)-1 if n>0 1. Otherwise

asked Oct 15 in Algorithms by Surya Dhanraj Loyal (2.7k points) | 47 views

0 votes

0 answers

23

Recursion Tree
Is this code running fine ?if yes what is the output I am getting 2 here.

asked Oct 14 in Algorithms by junaid ahmad Boss (7.5k points) | 47 views

0 votes

1 answer

24

time complexity
time taken to delete a node from min heap if you know the value but not position To find the position of the number in min heap should not be log(n) why is it so O(n)

asked Oct 14 in Algorithms by Kaluti Loyal (3.2k points) | 36 views

0 votes

0 answers

25

coreman
As stated, in dynamic programming we first solve the subproblems and then choose which of them to use in an optimal solution to the problem. Professor Capulet claims that it is not always necessary to solve all the ... chain multiplication problem for which this greedy approach yields a suboptimal solution. i dont understand this question please explain.

asked Oct 14 in Algorithms by arch Active (1.5k points) | 19 views

0 votes

0 answers

26

self doubt
is there any problem which can be solved by top down approach of dynamic programming but can not solve by bottom up approach or vice versa?

asked Oct 14 in Algorithms by arch Active (1.5k points) | 10 views

0 votes

0 answers

27

time complexity

asked Oct 14 in Algorithms by Kaluti Loyal (3.2k points) | 31 views

+1 vote

0 answers

28

merge sort
Consider the following variation on merge sort for the large values of 'n 'instead of recursing until 'n' is sufficiently small recur atmost a constant 'r' times and then use insertion sort to solve the 2r resulting sub problems.What is the running time of this variation a)theta(n) b)theta(n log n) c)theta(n2) d)theta(log n)

asked Oct 13 in Algorithms by A_i_$_h Boss (8.4k points) | 35 views

+2 votes

0 answers

29

Dijkstra's
I know that Dijkstra's Doesn't work for Negative weight cycle because it form a loop, Does it also true that it may or may not work for negative weight edge(without cycle) ? If it is not working for a negative weight edge(without cycle) give some example to prove it.

asked Oct 12 in Algorithms by junaid ahmad Boss (7.5k points) | 39 views

+3 votes

2 answers

30

Time complexity
Given a 2D array X[m][n] which has m rows and n columns. The array X is row wise and column wise sorted (i.e) each individula row and column is sorted. What is the complexity to search an element in this array a)O(m*n) b)O(m2) or O(n2) c)O(log2(m*n)) d)O(m+n)

asked Oct 12 in Algorithms by A_i_$_h Boss (8.4k points) | 31 views

Page:

1
2
3
4
5
6
...
80
next »

Experts in Algorithms

Member Since: August 2014
Net Votes: 4055 Best Ans: 111

Arjun

16990 Points

Member Since: September 2016
Net Votes: 910 Best Ans: 46

5500 Points

Member Since: March 2015
Net Votes: 955 Best Ans: 34

Digvijay Pandey

4630 Points

Member Since: March 2016
Net Votes: 1000 Best Ans: 32

rude

4560 Points

Member Since: February 2016
Net Votes: 950 Best Ans: 32

4460 Points

Member Since: November 2014
Net Votes: 804 Best Ans: 22

3368 Points

Member Since: September 2014
Net Votes: 925 Best Ans: 17

3210 Points

Member Since: July 2015
Net Votes: 848 Best Ans: 14

srestha

2816 Points

Member Since: December 2015
Net Votes: 949 Best Ans: 11

2778 Points

Member Since: January 2015
Net Votes: 823 Best Ans: 13

Rajarshi Sarkar

2686 Points

Quick search syntax

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

Follow @csegate

Gatecse

Recent questions in Algorithms

27,406 questions

35,255 answers

84,501 comments

33,454 users