Recent questions tagged algorithms - GATE CSE Doubts

0 votes

1 answer

Time complexity of below program
what should be the time complexity of below program anyone can anyone please explain for(i=1;i<=n:++i) { for(i=1;i<=n^2:++i) { for(i=1;i<=n^3:++i) { x=y+z; } } }

asked May 23 in Programming by Sumit goyal 2 (7 points) | 11 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

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

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

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

asked Apr 29 in Algorithms by ramcharantej_24 (22 points) | 31 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

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

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

GATE2013-44 Video Solution
Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m – 1 } } What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty queue? $Θ(n)$ $Θ(n + k)$ $Θ(nk)$ $Θ(n^2)$

asked Apr 19 in DS 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

0 votes

0 answers

GATE2008-40 Video Solution
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is $\Theta(n)$ $\Theta(\log n)$ $\Theta(\log^*n)$ $\Theta(1)$

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

0 votes

0 answers

GATE2003-66 Video Solution
The cube root of a natural number $n$ is defined as the largest natural number $m$ such that $(m^3 \leq n)$ . The complexity of computing the cube root of $n$ ($n$ is represented by binary notation) is $O(n)$ but not $O(n^{0.5})$ $O(n^{0.5})$ ... constant $m>0$ $O( (\log \log n)^k )$ for some constant $k > 0.5$, but not $O( (\log \log n)^{0.5} )$

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

0 votes

0 answers

GATE2007-45 Video Solution
What is the $\text{time complexity}$ of the following recursive function? int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor (sqrt(n))) + n); } $\Theta(n^2)$ $\Theta(n \log_2n)$ $\Theta(\log_2n)$ $\Theta(\log_2\log_2n)$

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

0 votes

0 answers

GATE2012-39 Video Solution
A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is $O (n \log n) $ $ O(n^{2} \log n) $ $ O(n^{2} + \log n) $ $ O(n^{2}) $

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

0 votes

0 answers

GATE2015-1-40 Video Solution
An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{1}{2}}$ decrease-key operations on a set of data items ... if the goal is to achieve the best total asymptotic complexity considering all the operations? Unsorted array Min - heap Sorted array Sorted doubly linked list

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

0 votes

0 answers

GATE2005-39 Video Solution
Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure) $O(n \log \log n)$ $\Theta(n \log n)$ $\Omega(n \log n)$ $\Omega\left(n^{3/2}\right)$

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

0 votes

0 answers

GATE2006-12 Video Solution
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree

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

0 votes

0 answers

GATE2010-34 Video Solution
The weight of a sequence $a_0,a_1, \dots, a_{n-1}$ of real numbers is defined as $a_0+a_1/2+ \dots + a_{n-1}/2^{n-1}$. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let $X$ denote the ... $X$ is equal to $max(Y, a_0+Y)$ $max(Y, a_0+Y/2)$ $max(Y, a_0 +2Y)$ $a_0+Y/2$

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

0 votes

0 answers

GATE2000-2.17 Video Solution
Consider the following functions $f(n) = 3n^{\sqrt{n}}$ $g(n) = 2^{\sqrt{n}{\log_{2}n}}$ $h(n) = n!$ Which of the following is true? $h(n)$ is $O(f(n))$ $h(n)$ is $O(g(n))$ $g(n)$ is not $O(f(n))$ $f(n)$ is $O(g(n))$

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

0 votes

0 answers

GATE2007-44 Video Solution
In the following C function, let $n \geq m$. int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function? $\Theta(\log_2n)$ $\Omega(n)$ $\Theta(\log_2\log_2n)$ $\Theta(\sqrt{n})$

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

0 votes

0 answers

GATE2012-40 Video Solution
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$

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

0 votes

0 answers

GATE2004-82 Video Solution
Let $A[1,\ldots,n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(m)$. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if a[i ... The complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(n)$

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

0 votes

0 answers

GATE2006-54 Video Solution
Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ or ... time in the key comparison mode Takes $\Theta (n)$ time and space Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number

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

0 votes

0 answers

GATE1999-1.14, ISRO2015-42 Video Solution
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$ ... $4, \ 8, \ 9, \ 15, \ 20, \ 47, \ 12, \ 17, \ 30, \ 40$

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

0 votes

0 answers

GATE2014-2-38 Video Solution
Suppose $P, Q, R, S, T$ are sorted sequences having lengths $20, 24, 30, 35, 50$ respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

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

0 votes

0 answers

GATE2006-52 Video Solution
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot? $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$ $\Theta (n^{3})$

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

0 votes

0 answers

GATE2006-14, ISRO2011-14 Video Solution
Which one of the following in place sorting algorithms needs the minimum number of swaps? Quick sort Insertion sort Selection sort Heap sort

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

0 votes

0 answers

GATE2007-50 Video Solution
An array of $n$ numbers is given, where $n$ is an even number. The maximum as well as the minimum of these $n$ numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed? At least $2n-c$ comparisons, for some ... $c$ are needed. At most $1.5n-2$ comparisons are needed. At least $n\log_2 n$ comparisons are needed None of the above

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

0 votes

0 answers

GATE2008-45 Video Solution
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to only vertex $a$ only vertices $a, e, f, g, h$ only vertices $a, b, c, d$ all the vertices

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

Page:

1
2
3
4
...
12
next »

7,525 questions

1,776 answers

10,835 comments

90,464 users