Recent questions tagged algorithms / GATE Overflow for GATE CSE

0 votes

1 answer

1411

Sorting:
You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate? 1)QuickSort 2)MergeSort 3)HeapSort 4)Selection Sort Explain? How

You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?1)QuickSort2)MergeSort3)HeapSort4)Selection Sort...

pradeepchaudhary

3.3k views

pradeepchaudhary asked Jul 8, 2018

0 votes

1 answer

1412

GeeksForGeeks Quiz
Q) Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general? (A) Heap Sort (B) Selection Sort (C) Insertion Sort (D) Merge Sort The Answer ... is (B). But My question is Why not (D) Since There is not a Single Swap operation is performed in Merge Sort.

Q) Consider a situation where swap operation is very costly.Which of the following sorting algorithms should be preferred so that the number of swap operations are minimi...

pradeepchaudhary

8.3k views

pradeepchaudhary asked Jul 8, 2018

0 votes

2 answers

1413

what is the time complexity of below code ?
foo(int n) { for(int i=0 ; i<n ;i++) for(int j=i ; j<=i*i ;j++) if(j%i==0) { for(int k=0;k<j;k++) printf("hii"); } } How to proceed here for analyzing the time complexity ?

foo(int n) { for(int i=0 ; i<n ;i++) for(int j=i ; j<=i*i ;j++) if(j%i==0) { for(int k=0;k<j;k++) printf("hii"); } } How to proceed here for analyzing the time complexity...

radha gogia

1.6k views

radha gogia asked Jul 7, 2018

0 votes

1 answer

1414

#algorithm
15.4-1 is it right ??? ans is 6 ?? is there any other method to determine the lcs coz it requires time to compute till the whole traversal of matrix

15.4-1 is it right ???ans is 6 ??is there any other method to determine the lcs coz it requires time to compute till the whole traversal of matrix

vijju532

339 views

vijju532 asked Jul 7, 2018

0 votes

1 answer

1415

self doubt
i could not remember the strassen matrix multiplication equation is it necessary to remember the equation which is given by https://www.geeksforgeeks.org/easy-way-remember-strassens-matrix-equation/??

i could not remember the strassen matrix multiplication equation is it necessary to remember the equationwhich is given by https://www.geeksforgeeks.org/easy-way-remember...

vijju532

468 views

vijju532 asked Jul 7, 2018

2 votes

1 answer

1416

Time Complexity
Given a 0-indexed array A of integers of size N >= 3 where every element is one more or one less than the previous element. If there is exactly one element, A[i] where 0 < i < N-1, which is either greater or less than both its adjacent elements, which of the following is ... in the array? Pick one of the choices a) O(1) b) O(n) c) O(logn) d) O(sqrt(n)) e) None of the above

Given a 0-indexed array A of integers of size N >= 3 where every element is one more or one less than the previous element. If there is exactly one element, A[i] where 0 ...

Naveen Kumar 3

686 views

Naveen Kumar 3 asked Jul 5, 2018

2 votes

1 answer

1417

Space Complexity of Dijkastra's algorithm
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????

I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity)But how ????

Hardik Maheshwari

3.1k views

Hardik Maheshwari asked Jul 5, 2018

0 votes

2 answers

1418

self doubt
i am getting 4,3,4,3,8,2 is it right?????

i am getting 4,3,4,3,8,2 is it right?????

vijju532

734 views

vijju532 asked Jul 5, 2018

0 votes

1 answer

1419

ACE Algorithms volume 2 Divede and Conquer Q 11
Given two sorted double linked list L1 and L2 of n elements each, which of the following are true? (A) L1 and L2 can be merged into single sorted list in Θ(n) time. (B) L1 and L2 can be merged into single sorted list in Θ(1) time. ( ... merged into single sorted list in Θ(nlogn) time. (D) L1 and L2 can be merged into single sorted list in Θ(n2) time.

Given two sorted double linked list L1 and L2 of n elements each, which of the following are true?(A) L1 and L2 can be merged into single sorted list in Θ(n) time.(B) L1...

JAYKISHAN

843 views

JAYKISHAN asked Jul 5, 2018

1 votes

1 answer

1420

Cormen 3rd edition chapter 22 question: 22.4.4
Prove or disprove: If a directed graph G contains cycles, then TOPOLOGICAL SORT $(G)$ produces a vertex ordering that minimizes the number of “bad” edges that are inconsistent with the ordering produced.

Prove or disprove: If a directed graph G contains cycles, then TOPOLOGICAL SORT $(G)$ produces a vertex ordering that minimizes the number of “bad” edges that are inc...

Abhilash Mishra

731 views

Abhilash Mishra asked Jul 4, 2018

0 votes

1 answer

1421

self doubt
all NP problems have the complexity exponential ???

all NP problems have the complexity exponential ???

vijju532

227 views

vijju532 asked Jul 2, 2018

0 votes

0 answers

1422

Recurrence Equation
To prove that the time complexity of equation T(n) = T(α n) + T((1 – α)n) + βn is Θ(n logn).

To prove that the time complexity of equationT(n) = T(α n) + T((1 – α)n) + βnisΘ(n logn).

pk14697

337 views

pk14697 asked Jul 2, 2018

0 votes

2 answers

1423

Complexity!!!
Hello anyone can help me to find big O for this algorithm please.... f=1; x=3; for (int i = 1; i <= n; i*=2) for (int j = 1; j <= i * i; j++) if (i % j == 0) for (int k = 1; k <= j; k++) f=f*x;

Hello anyone can help me to find big O for this algorithm please.... f=1;x=3;for (int i = 1; i <= n; i*=2) for (int j = 1; j <= i * i; j++) if (i % j == 0) ...

sweet heart

308 views

sweet heart asked Jul 1, 2018

2 votes

1 answer

1424

Time Complexity in
What is the time Complexity of 2T(n/2) + nlogn? Can we apply Master's Theorem?

What is the time Complexity of 2T(n/2) + nlogn? Can we apply Master's Theorem?

nishant279

2.3k views

nishant279 asked Jul 1, 2018

0 votes

0 answers

1425

How to calculate below sum series ?

radha gogia

423 views

radha gogia asked Jul 1, 2018

0 votes

2 answers

1426

BFS Traversal
How through a BFS we can find graph is connected or disconnected? Plz give some example and explain

How through a BFS we can find graph is connected or disconnected? Plz give some example and explain

srestha

936 views

srestha asked Jun 30, 2018

0 votes

1 answer

1427

graph_doubt
"edge disjoint spanning tree" means ?

"edge disjoint spanning tree" means ?

air1ankit

303 views

air1ankit asked Jun 30, 2018

1 votes

0 answers

1428

Kenneth Rosen Edition 6th Exercise 7.6 Question 60 b (Page No. 511)
Let R be the relation on the set of functions from $Z^+$ to itself such that (f,g) belongs to R iff f is $\Theta(g)$ The equivalence class of f(n)=$n^2$ is set of all functions who are in $\Theta(n^2)$ is it correct?

Let R be the relation on the set of functions from $Z^+$ to itself such that (f,g) belongs to R iff f is $\Theta(g)$The equivalence class of f(n)=$n^2$ is set of all func...

Ayush Upadhyaya

272 views

Ayush Upadhyaya asked Jun 30, 2018

1 votes

1 answer

1429

Kruskal Algorithm
Complexity of Kruskal's algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are unsorted is _______ ______________________________________________________________________________ If elements are sorted we do with Union Find algo with ... is $log^{*}V$ Now from here can we derive it for unsorted edges? for ref: here

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are unsorted is __________...

srestha

1.6k views

srestha asked Jun 30, 2018

0 votes

2 answers

1430

self doubt
i am getting 100+35+50=185 is it correct ???

i am getting 100+35+50=185 is it correct ???

vijju532

464 views

vijju532 asked Jun 29, 2018

0 votes

1 answer

1431

matrics multiplication

shruti gupta1

879 views

shruti gupta1 asked Jun 29, 2018

–1 votes

1 answer

1432

Ace Test Series: Algorithms - Minimum Spanning Trees

Na462

724 views

Na462 asked Jun 29, 2018

1 votes

1 answer

1433

Ace Test Series: Algorithms - Dynamic Programming OBST

Na462

1.5k views

Na462 asked Jun 29, 2018

0 votes

1 answer

1434

Dynamic programming
Consider the following C functions: int fun ( int n) { if (n<6) return 1; else return( fun(n-1)+fun(n-3)+fun (n-5)); } Q) Suppose we modify the above function fun( ) and store the values of fun (i), 0<=i<n, as and when they are computed . With this ... ( ) is significantly reduced. What is the time complexity of modified fun( ) would be: a)O(1) b)O(n) c)O(n^2) d)O(n!)

Consider the following C functions:int fun ( int n){ if (n<6) return 1; else return( fun(n-1)+fun(n-3)+fun (n-5));}Q) Suppose we modify the above function ...

Rohit Pandey

353 views

Rohit Pandey asked Jun 28, 2018

0 votes

1 answer

1435

#IdentifyFunctions #Algorithms User Gate 2014 Self Doubt
Original Question - here Consider the following C function in which size is the number of elements in the array E: int MyX(int *E, unsigned int size) { int Y = 0; int Z; int i, j, k; for(i = 0; i< size; i++) Y = Y + ... ============= Can someone trace the code by taking some arbitrary values in the array and show how to do this? Thank you!

Original Question - here Consider the following C function in which size is the number of elements in the array E: int MyX(int *E, unsigned int size) { int Y = 0; int Z;...

iarnav

530 views

iarnav asked Jun 28, 2018

2 votes

2 answers

1436

what is the time complexity for the below question ?
For the below code : foo() { for(i=1;i<=n;i++) { for(j=0;j<i;j++) { for(k=0;k<j;k++) c++; } } } Here k is executing j-1 times j is executing i times and i is executing n^2 times, so first I am ... I am getting order of n^8 . But this is getting too large, I checked with an example, it is not matching,So please correct where I went wrong.

For the below code : foo() { for(i=1;i<=n;i++) { for(j=0;j<i;j++) { for(k=0;k<j;k++) c++; } } } Here k is executing j-1 times j is executing i times and i is executing n^...

radha gogia

816 views

radha gogia asked Jun 28, 2018

1 votes

1 answer

1437

Gate 2018
This is another form of gate 2018 matrix-chain question

This is another form of gate 2018 matrix-chain question

kunal goswami

480 views

kunal goswami asked Jun 28, 2018

0 votes

1 answer

1438

Asymtotic notation
How to prove these type of questions???

How to prove these type of questions???

saumya mishra

352 views

saumya mishra asked Jun 26, 2018

0 votes

2 answers

1439

Big O
Explain b and c part???

Explain b and c part???

saumya mishra

372 views

saumya mishra asked Jun 26, 2018

2 votes

1 answer

1440

Merge sort
Given "log n" sorted lists each of size "n/log n",what is the total time required to merge them into one single list.

Given "log n" sorted lists each of size "n/log n",what is the total time required to merge them into one single list.

Naveen Parihar

2.1k views

Naveen Parihar asked Jun 26, 2018

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