Recent questions and answers in Algorithms - GATE CSE Doubts

0 votes

0 answers

Self Doubt:Time Complexity
What is time complexity to find median of medians?

asked 1 day ago in Algorithms by srestha (749 points) | 13 views

0 votes

0 answers

Algorithms Master Theorem
T(n) = 2T(n/4) + 2^n How to solve these kind of questions?

asked 5 days ago in Algorithms by Vishal_Malo (6 points) | 8 views

0 votes

0 answers

Analysis of algorithms and space and time complexity

asked 6 days ago in Algorithms by sameer9949 (6 points) | 14 views

0 votes

0 answers

Binary search
Q. Find time complexity Input: A sorted array of n elements output : Find any two elements A and B such that A + B = 1000

asked Jun 16 in Algorithms by abhijnr (6 points) | 4 views

0 votes

0 answers

Time Complexity - Self Doubt Question

asked Jun 13 in Algorithms by 2207akash (6 points) | 8 views

0 votes

0 answers

Self-Doubt CLRS
How does the partition algorithm has O(1) space complexity instead of O(N) if it modifies the input array itself even if it doesn't use any extra space?

asked Jun 10 in Algorithms by nvs16 (6 points) | 4 views

0 votes

0 answers

MADE EASY: CHAPTER: DIVIDE AND CONQUER
Find the average number of comparisons in a binary search on a sorted array of 10 consecutive integers starting from 1. (a) 2.6 (c) 2.8 (b) 2.7 (d) 2.9 [closed]

asked Jun 6 in Algorithms by Debanil (11 points) | 7 views

0 votes

0 answers

Geeks for Geeks Topic Test
Which of the following is not true about comparison-based sorting algorithms. The minimum possible time complexity of a comparison-based sorting algorithm is O(N log N) for a random input array. Any comparison-based sorting algorithm can be made stable by using ... . Heap Sort is not a comparison-based sorting algorithm. Choose the correct option. 1,2. 2,4. 4. 2.

asked May 16 in Algorithms by ramcharantej_24 (22 points) | 10 views

0 votes

0 answers

Geeks For Geeks Topic Question
Consider the problem of computing min-max in an unsorted array where min and max are minimum and maximum elements of an array. Algorithm A1 can compute min-max in a1 comparisons using divide and conquer. Algorithm A2 can compute min-max in a2 comparisons by ... and a2 considering the worst-case scenarios? a1 < a2. a2 > a1. a1 = a2. Depends on the input.

asked May 16 in Algorithms by ramcharantej_24 (22 points) | 3 views

0 votes

0 answers

Depth First Search algorithms
Why can't DFS be used to find shortest paths in unweighted graphs?

asked May 14 in Algorithms by shourya srivastava01 (6 points) | 4 views

0 votes

0 answers

can anyone explain travelling salesman problem implementation using Java in simpler way?

asked May 9 in Algorithms by suhit (6 points) | 6 views

0 votes

0 answers

Tower of Hanoi
There are n disks of different sizes and three pegs. Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top. The object is to transfer all the disks to the third peg. Only one disk can be moved ... a disk on the middle peg or move a disk from that peg. Write an algorithm that solves the problem in the minimum number of moves.

asked May 8 in Algorithms by sumitsehgal (8 points) | 9 views

0 votes

0 answers

Tower of hanoi
There are n disks of different sizes and three pegs. Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest on top. The object is to transfer all the disks to the third peg. Only one disk can be moved ... a disk on the middle peg or move a disk from that peg. Write an algorithm that solves the problem in the minimum number of moves.

asked May 8 in Algorithms by sumitsehgal (8 points) | 6 views

0 votes

0 answers

https://www.youtube.com/watch?time_continue=1&v=mZjkxOknmhU&feature=emb_logo

asked May 7 in Algorithms by Deb Prakash (7 points) | 21 views

0 votes

0 answers

Clrs book,mit Assignment
$T(n) =2^{n}T(n/2) +n^{n}$

asked May 6 in Algorithms by Palash yadav (16 points) | 11 views

0 votes

1 answer

Cormen Excersice 4, Question 4.4-1
Solve the Given Recurrence using the Substitution method (in book it was Recursion Tree method) T(n) = 3T(n/2) + n

answered May 4 in Algorithms by Kushagra गुप्ता (415 points) | 31 views

0 votes

0 answers

Find minimum weight cycle in an undirected graph please explain time complexity by other than dijkstra’s shortest path

asked Apr 30 in Algorithms by abhishek tiwary (18 points) | 13 views

+1 vote

1 answer

GATE2020-CS-49 Video Solution
Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j \mid$. The weight of minimum spanning tree of $G$ is _________

answered Apr 30 in Algorithms by amitkhurana512 (187 points) | 7 views

+1 vote

1 answer

GATE2020-CS-47 Video Solution
Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is ___________.

answered Apr 27 in Algorithms by amitkhurana512 (187 points) | 8 views

0 votes

0 answers

(GATE CS 2003) Explain your answer with relevent logic as well

asked Apr 26 in Algorithms by ABHIMANYUSINGH (6 points) | 10 views

+1 vote

1 answer

GATE2020-CS-6 Video Solution
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially? $\Theta (n^{4})$ $\Theta (n^{2})$ $\Theta (n^{2}\log n)$ $\Theta (n^{3})$

answered Apr 26 in Algorithms by amitkhurana512 (187 points) | 22 views

0 votes

0 answers

Find time complexity of T(n) = 2*T(n-1) + 3*T(n-2)

asked Apr 23 in Algorithms by roh (17 points) | 13 views

+1 vote

1 answer

GATE2020-CS-31 Video Solution
Let $G = (V, G)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST ... $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$

answered Apr 22 in Algorithms by amitkhurana512 (187 points) | 17 views

+1 vote

1 answer

GATE2020-CS-23 Video Solution
Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ is_____________.

answered Apr 22 in Algorithms by amitkhurana512 (187 points) | 11 views

+1 vote

1 answer

GATE2020-CS-2 Video Solution
For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is $\Theta (\log_a \log _b n)$ $\Theta (\log_{ab} n$) $\Theta (\log_{b} \log_{a} \: n$) $\Theta (\log_{2} \log_{2} n$)

answered Apr 22 in Algorithms by amitkhurana512 (187 points) | 32 views

0 votes

0 answers

gate 1989 # Algorithm
how to do quicksort i am not gettng ? can you explain pass by pass in simple diagrammatical way having i j and p ? https://gateoverflow.in/89083/gate1989-9

asked Apr 21 in Algorithms by Çșȇ ʛấẗẻ (6 points) | 6 views

0 votes

1 answer

time complexity self doubt
FIND THE TIME COMPLEXITY OF THE FOLLOWING CODE. int p=2^n for(i=1;p>=n;i++) { p=p/i; }

answered Apr 21 in Algorithms by roh (17 points) | 25 views

0 votes

0 answers

Complexity analysis of algorithms
What is the time complexity of the below algorithm: sum = 0; for(i=0; i<=n; i++){ for(j=1; j<= i; j=j*2){ sum = sum + j } }

asked Apr 21 in Algorithms by roh (17 points) | 19 views

0 votes

0 answers

Applied course test series: Recurrence relation
When n=(2)^(2k) for some k>0, the recurrence relation : T(n)=(2)½ T(n/2)+ (n)½ , T(1)=1 evaluates to: (n)½(log n+1) (n)½ (log (n)½ ) (n)½ logn n log(n)½

asked Apr 19 in Algorithms by Suhail96 (6 points) | 14 views

0 votes

0 answers

GATE2014-1-39 Video Solution
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________

asked Apr 19 in Algorithms by admin (3.6k points) | 7 views

0 votes

0 answers

GATE2016-1-39 Video Solution
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________

asked Apr 19 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2007-15,ISRO2016-26 Video Solution
Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$

asked Apr 19 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2006-51, ISRO2016-34 Video Solution
Consider the following recurrence: $ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true? $ T(n)=\Theta (\log\log n)$ $ T(n)=\Theta (\log n)$ $ T(n)=\Theta (\sqrt{n})$ $ T(n)=\Theta (n)$

asked Apr 19 in Algorithms by admin (3.6k points) | 3 views

0 votes

0 answers

GATE2014-1-42 Video Solution
Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3 Half of the product of the $3$ consecutive integers. One-third of the product of the $3$ consecutive integers. One-sixth of the product of the $3$ consecutive integers. None of the above.

asked Apr 19 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2014-3-14 Video Solution
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is $O(n^2)$ $O(n \log n)$ $\Theta(n\log n)$ $O(n^3)$

asked Apr 19 in Algorithms by admin (3.6k points) | 3 views

0 votes

0 answers

GATE1996-2.13, ISRO2016-28 Video Solution
The average number of key comparisons required for a successful search for sequential search on $n$ items is $\frac{n}{2}$ $\frac{n-1}{2}$ $\frac{n+1}{2}$ None of the above

asked Apr 19 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2016-1-40 Video Solution
$G=(V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees $(MSTs)$ of $G$ is/are TRUE? If $e$ is the lightest edge of some cycle in ... of some cycle in $G$, then every MST of $G$ excludes $e$. I only. II only. Both I and II. Neither I nor II.

asked Apr 19 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2013-30 Video Solution
The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is $\Theta(1)$ $\Theta(\sqrt{\log} n)$ $\Theta(\frac{\log n}{\log \log n})$ $\Theta(\log n)$

asked Apr 19 in Algorithms by admin (3.6k points) | 2 views

0 votes

0 answers

GATE2004-29 Video Solution
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of $n$ $n^2$ $n \log n$ $n \log^2n$

asked Apr 19 in Algorithms by admin (3.6k points) | 1 view

0 votes

0 answers

GATE2016-1-11 Video Solution
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.

asked Apr 19 in Algorithms by admin (3.6k points) | 2 views

To see more, click for all the questions in this category.

Recent questions and answers in Algorithms

7,525 questions

1,776 answers

10,835 comments

90,464 users