Recent questions tagged algorithms - GATE CSE Doubts

0 votes

0 answers

Self Doubt Algorithms
what is time complexity to insert a node based on key in a priority queue? O(nlogn) O(logn) O(n) (n2) i am unable to get the meaning of the question . is it a simple insertion in the priority queue?? . what is the meaning of “based on key”.Please explain this….

asked Oct 20 in Programming by manal jain (5 points) | 15 views

0 votes

0 answers

Unacademy Free Test Algo Quesn
Assume that the enqueuing and dequeuing of elements in BFS takes O(V) time. then what will be the time complexity of the BFS algorithm? (Assume adjacency list representation) O(V^3) O(V^2) O(V^2 . E) O(V + E) Anyone please clarify.

asked Oct 17 in Algorithms by Shivateja MST (39 points) | 37 views

+1 vote

2 answers

Self Doubt Algorithms
I was having a doubt that should we consider = or I am finding different answers on the internet.

asked Oct 17 in Algorithms by satvik (11 points) | 41 views

0 votes

1 answer

Deletion in heap
How to delete the last node in a max-heap or min-heap? Do we delete it directly or like in normal case- replace it with itself then call max heapify on it and then finally decrease heap size?

asked Oct 11 in Algorithms by RasMalai (27 points) | 34 views

0 votes

0 answers

Self Doubt in Sorting Algorithm
If there is a question on bubble sort and nothing about the type (with a boolean flag which terminates if there is no swap in a pass or without flag) of bubble sort is mentioned. which one should we use?

asked Oct 9 in Algorithms by badman (5 points) | 11 views

0 votes

1 answer

Unacademy Free Test Question
Consider the following and choose the correct answer by order of growth 1. n! 2. a^n , a is constant 3. e^n 4. n^n 5. n^k , where k is constant Anyone please clarify. 5<2<3<1<4 b.2<5<3<1<4 c.5<3<2<1<4 d.5<2<3<4<1

asked Oct 7 in Algorithms by Shivateja MST (39 points) | 23 views

0 votes

1 answer

How to solve this recurrence relation using back substitution?

asked Oct 2 in Algorithms by neel19 (7 points) | 55 views

0 votes

0 answers

Cormen Page 44 , Para 2
Statement : It is not contradictory, however, to say that the worst-case running time of insertion sort is Ω(n^2 ), since there exists an input that causes the algorithm to take Ω(n^2 ) time . What does this statement mean as they are talking about worst case but are using Big Omega notation?

asked Sep 25 in Algorithms by Ankit Raina 7 (5 points) | 22 views

0 votes

1 answer

Self Doubt (PYQ)
https://gateoverflow.in/549/gate1992-01-ix In this question the time complexity is given as O((n+m)$\alpha$(n)). In Horowitz it is said that on average it is O(1) for find, then shouldn’t it be O(n+m).

asked Sep 22 in Algorithms by Mellophi (333 points) | 17 views

0 votes

0 answers

ISI-2020-ALGORITHMS-C2
An $n*n$ binary matrix M is called a NICE matrix, if each row of M has exactly one non-zero element and each column also has exactly one non-zero element. (i) Suggest a method of storing a NICE matrix in an $O(n)$ size array. (ii) Design an $O(n)$ ... (in pseudocode) for computing R=PQ, where P and Q are both NICE matrices each stored in an array of size $O(n)$ as in (i).

asked Sep 21 in Algorithms by souveekp (5 points) | 29 views

0 votes

0 answers

Made Easy Workbook for Algorithm
Find the running time for Dijkstra's algorithm on the complete graph of n-vertices.

asked Sep 19 in Algorithms by Vishal_kumar98 (7 points) | 25 views

0 votes

0 answers

Algo Book doubt-Goodrich
Given an unordered sequences S of n compatible elements. Describe an efficient method for finding the $\left \lceil \sqrt{n} \right \rceil$ items whose rank in an ordered version of closest to that of median. What is running time of your method?

asked Sep 18 in Algorithms by srestha (1k points) | 10 views

0 votes

0 answers

Self Doubt- Algo book-Goodrich
To implement deterministic and randomized version of quick sort algorithm, which one will be faster? [Your test should include sequences that are very random looking as well as that one which is almost sorted.]

asked Sep 18 in Algorithms by srestha (1k points) | 9 views

0 votes

0 answers

Algorithm :Tardos
Suppose you are consulting for a bank, that is concerned about fraud detection and they came to you with the following problem. They have the collection of n bank cards they have confiscated, suspecting them of being used in fraud. Each bank card is a ... are to pick two of them and plug them into the equivalent tester. What is Time Complexity to find answer of this question?

asked Sep 18 in Algorithms by srestha (1k points) | 22 views

0 votes

1 answer

Self doubt:Algorithm Book-Tardos
Can we measure , number of inversion in $O\left ( nlogn \right )$ time?Give some hint.

asked Sep 18 in Algorithms by srestha (1k points) | 21 views

0 votes

0 answers

ACE PRACTISE BOOK
Single source shortest path problems can be implemented by the Greedy Method using (a) Red-Black trees (b) Min Heap (c ) AVL Trees (d) None of these

asked Sep 16 in Algorithms by Vishal_kumar98 (7 points) | 9 views

0 votes

0 answers

Self Doubt (PYQs)
https://gateoverflow.in/978/gate2006-17 If this question was MSQ type then will C and D be possible solutions also?

asked Sep 9 in Algorithms by Mellophi (333 points) | 45 views

0 votes

0 answers

Self Doubt (PYQs)
https://gateoverflow.in/2503/gate1994-7 In this question can someone explain how the condition j!= n+i-K is obtained?

asked Sep 9 in Algorithms by Mellophi (333 points) | 13 views

+1 vote

1 answer

Self Doubt - Classification of Edges in DFS
Source: Cormen. Back edges are those edges (u,v) connecting a vertex u to an ancestor v in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges. Forward edges are those non-tree edges (u, ... doubt: Why there is a difference in the definition of the highlighted part? Back edges are also non-tree edges, isn't it?

asked Sep 8 in DS by KUSHAGRA गुप्ता (1.4k points) | 79 views

0 votes

1 answer

Self doubt - Kruskal's Algorithm for MST
One approach for Kruskal's algorithm is to make use of a Disjoint-set data structure. With this the running time of Kruskal's algorithm as $O(ElgV)$ My doubt is whether I can implement Kruskal's this way too: Creating Min heap using edge ... to check for cycles$\Rightarrow O(V+E)$ Time complexity worst case: $E+ElgE\Rightarrow O(ElgE)\Rightarrow O(ElgV)$

asked Sep 8 in Algorithms by KUSHAGRA गुप्ता (1.4k points) | 40 views

0 votes

0 answers

Made easy online test series, Algorithms
I think that the Emax’s last addition will be +6 instead of +5. Am I correct please let me know. If I am wrong then please correct me. Below is the question.

asked Sep 7 in Algorithms by sarthakdarji (9 points) | 67 views

0 votes

1 answer

Made easy Workbook, Self doubt in Minimum Spanning Tree

asked Sep 5 in Algorithms by sarthakdarji (9 points) | 53 views

0 votes

0 answers

Made easy Work book, Self doubt in Graph Based Algorithms

asked Sep 3 in Algorithms by sarthakdarji (9 points) | 8 views

0 votes

1 answer

Made easy workbook, Graph Based Algorithms
Which of the following is not a cross edge during given BFS traversal on G? a) d,c b) d,b c) e,b d) e,f

asked Sep 2 in Algorithms by sarthakdarji (9 points) | 24 views

0 votes

1 answer

Made Easy theory book, Matrix Chain Multiplication

asked Sep 2 in Algorithms by sarthakdarji (9 points) | 44 views

0 votes

1 answer

Self doubt Made easy theory book Graph Based Algorithms

asked Sep 1 in Algorithms by sarthakdarji (9 points) | 23 views

0 votes

1 answer

Made Easy Theory Book, Graph Based Algorithms
How to find the number of cross edges in the below given question? (Selection of Adjacent vertex in DFS is decided by lexicographical order. )

asked Sep 1 in Algorithms by sarthakdarji (9 points) | 25 views

0 votes

0 answers

Made easy theory book, Graph Based Algorithms
How to find the number of cross edges in the below given question? (Selection of Adjacent vertex in DFS is decided by lexicographical order. )

asked Sep 1 in Algorithms by sarthakdarji (9 points) | 10 views

0 votes

1 answer

Self doubt in Graph Based Algorithms (Made easy theory book)

asked Sep 1 in Algorithms by sarthakdarji (9 points) | 17 views

0 votes

0 answers

Self_doubt, Code sample from Galvin:Implicit Threading (with few modifications)

asked Aug 31 in Algorithms by Nikhil_dhama (151 points) | 10 views

0 votes

1 answer

Made Easy Workbook

asked Aug 30 in Algorithms by sarthakdarji (9 points) | 40 views

0 votes

0 answers

#made-easy-test-series
Assume each item is a 8 digit octal number and the maximum number of comparisons needed to sort 10 items using radix sort is________? according to me answer should be zero bcz radix sort is non comparision base algorithm but they give this explanation The max. no ... number having→ 8 digits The octal number system base value is → 8 So, items*digits*base=10*8*8=640 answer=640

asked Aug 28 in Algorithms by 404 found (11 points) | 22 views

0 votes

0 answers

Cormen:Edition 3:Exercise 2.2:Page number-40
Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order. $BUBBLESORT(A)$ 1 for i=1 to A.length􏰐-1 2 for j=A.length downto i+1 3 if A[j]<A[j-1] ... allow you to prove in- equality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.

asked Aug 26 in DS by srestha (1k points) | 11 views

0 votes

2 answers

Self doubt in the Kruskal Algorithm
Why in Kruskal’s Algorithm we use $\textbf{O(V+E)}$ and not $\mathbf{V*E}$ Since, in order to check cycle we use union-find algorithm whic in worst case takes $\textbf{O(V)}$? Can someone please explain this?

asked Aug 25 in Algorithms by `JEET (187 points) | 30 views

0 votes

1 answer

CLRS Ed.2 Chapter 24 Ex-24.1-1
Change the weight of edge z-x to 4. Run the Bellman-Ford algorithm on the directed graph using vertex s as the source. In each pass, relax edges in the order ... of negative-weight cycle? And if for example there is no negative weight cycle present in the graph then does all different sequence of edges gives same value?

asked Aug 24 in Algorithms by KUSHAGRA गुप्ता (1.4k points) | 53 views

+1 vote

2 answers

find two numbers in the array that have the sum that we want

asked Aug 22 in Algorithms by Tara22 (11 points) | 49 views

+2 votes

1 answer

Made Easy Test Series - Algorithms
I understand that S1 is incorrect. But how is S2 correct? In BFS of an undirected graph, there are only cross edges and tree edges. There are neither back edges nor forward edges. Can anyone please clarify? Thanks.

asked Aug 22 in Algorithms by sankalpmittal (33 points) | 54 views

0 votes

1 answer

Self Doubt: Recurrence Relation - Time Complexity
How to solve for the asymptotic time complexity of this recurrence relation? $T(n) = 2nT(n/2) + n^2$ Any idea how to approach? Can we solve this using recurrence tree? Thanks!

asked Aug 22 in Algorithms by sankalpmittal (33 points) | 36 views

0 votes

1 answer

Discrete Mathematics and Its Applications (7th Edition) - Kenneth Rosen

asked Aug 19 in Algorithms by sankalpmittal (33 points) | 47 views

0 votes

0 answers

Algorithms Concept doubt
Can some one give examples of External Sorting Algorithms ?

asked Aug 17 in Algorithms by Shivateja MST (39 points) | 32 views

Page:

1
2
3
4
...
14
next »

8,430 questions

2,707 answers

13,232 comments

95,451 users