search
Log In

Recent questions and answers in Algorithms

1 vote
2 answers
1
which of the following cannot be solved using masters theorem? a) T(n) = 2T(n/2) + n/logn b) T(n) = 2T(n/2) + logn c)T(n)=T(n/2)+logn d) non of these
answered 2 days ago in Algorithms Abhilash Behera 380 views
29 votes
5 answers
2
Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i <= n; i++){ X ... $f1(n)$ and $f2(n)$ are $\Theta(n)$ and $\Theta(n)$ $\Theta(2^n)$ and $\Theta(n)$ $\Theta(n)$ and $\Theta(2^n)$ $\Theta(2^n)$ and $\Theta(2^n)$
answered 2 days ago in Algorithms Vivek Raj 8.6k views
60 votes
15 answers
3
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
answered 5 days ago in Algorithms tusharSingh 25.6k views
22 votes
4 answers
4
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is: $MNOPQR$ $NQMPOR$ $QMNPRO$ $QMNPOR$
answered 6 days ago in Algorithms Surya_Dev Chaturvedi 8.4k views
22 votes
5 answers
5
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta(n)$ $\Theta(m)$ $\Theta(m+n)$ $\Theta(mn)$
answered 6 days ago in Algorithms Surya_Dev Chaturvedi 5.8k views
22 votes
7 answers
6
Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanning tree of $G$ is: $n-1$ $2n-2$ $\begin{pmatrix} n \\ 2 \end{pmatrix}$ $n^2$
answered 6 days ago in Algorithms vermavijay1986 5.7k views
11 votes
6 answers
7
Consider a hash table with $m$ slots that uses chaining for collision resolution. The table is initially empty. What is the probability that after 4 keys are inserted that at least a chain of size 3 is created? (Assume simple uniform hashing is used) $m^{&ndash;2}$ $m^{&ndash;4}$ $m^{&ndash;3} (m &ndash; 1)$ $3m^{&ndash;1}$
answered 6 days ago in Algorithms Subhajit Panday 3.1k views
31 votes
8 answers
8
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. Which of the following recurrences does $x_n$ satisfy? $x_n = 2x_{n-1}$ $x_n = x_{\lfloor n/2 \rfloor} + 1$ $x_n = x_{\lfloor n/2 \rfloor} + n$ $x_n = x_{n-1} + x_{n-2}$
answered Jan 14 in Algorithms eshita1997 4k views
20 votes
4 answers
9
Solve the recurrence equations: $T(n) = T(n - 1)+ n$ $T(1) = 1$
answered Jan 14 in Algorithms StoneHeart 2.4k views
3 votes
2 answers
10
Consider an array containing ‘n’ elements. The elements present in an array are in arithmetic progression, but one element is missing in that order. What is the time complexity to find the position of the missing element using divide and conquer?
answered Jan 14 in Algorithms reboot 350 views
22 votes
6 answers
11
Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is first visited, and finish time $f(u)$ represent the time instant when the vertex $u$ ... connected There are two connected components, and $Q$ and $R$ are connected There are two connected components, and $P$ and $Q$ are connected
answered Jan 12 in Algorithms vermavijay1986 4.8k views
35 votes
6 answers
12
Consider two strings $A$="qpqrr" and $B$="pqprqrp". Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ and let $y$ be the number of such longest common subsequences between $A$ and $B$. Then $x +10y=$ ___.
answered Jan 11 in Algorithms Rohitburke 6.9k views
22 votes
3 answers
13
Consider the following recurrence relation: $T(n) = \begin{cases} 2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$ Which of the following statements is TRUE? $T(n)$ is $O(\log n)$. $T(n)$ is $O(\log n. \log \log n)$ but not $O(\log n)$. $T(n)$ is ... $O(\log^{2} n)$ but not $O(\log^{3/2} n)$. $T(n)$ is $O(\log^{2} n. \log \log n)$ but not $O(\log^{2} n)$.
answered Jan 9 in Algorithms shashankpal 1.3k views
14 votes
3 answers
14
Consider the following sequence of numbers:$92, 37, 52, 12, 11, 25$ Use Bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.
answered Jan 8 in Algorithms ankit3009 1.5k views
23 votes
6 answers
15
For merging two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, we require comparisons of $O(m)$ $O(n)$ $O(m+n)$ $O(\log m + \log n)$
answered Jan 8 in Algorithms ankit3009 14.4k views
16 votes
7 answers
16
Algorithm design technique used in quicksort algorithm is? Dynamic programming Backtracking Divide and conquer Greedy method
answered Jan 8 in Algorithms ankit3009 6.9k views
16 votes
3 answers
17
Assume that the last element of the set is used as partition element in Quicksort. If $n$ distinct elements from the set $\left[1\dots n\right]$ are to be sorted, give an input for which Quicksort takes maximum time.
answered Jan 8 in Algorithms ankit3009 2.3k views
9 votes
4 answers
18
Quicksort is ________ efficient than heapsort in the worst case.
answered Jan 8 in Algorithms ankit3009 1.3k views
1 vote
2 answers
19
Can pls someome. Tell.number of comparisons in. Merge sort in best case as well as worst case. Acc to. Me, at. Each level we need O(n) comaprisons and number of levels are log n in merge sort(whether it. Is a best case or worst case).hence mumber o comparisons should be nlogn in worst case as well as best case. Pls guide me.
answered Jan 6 in Algorithms sachin486 1.4k views
0 votes
2 answers
20
An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it in linear time using a left to right pass of the array solves in linear time using a right to left pass of the array solves it using divide and conquer in time $\theta (n\log n)$ solves it in time $\theta (n^{2})$
answered Jan 5 in Algorithms Joey 179 views
0 votes
1 answer
21
What is the average case time complexity of the best sorting algorithm for an array having 2^n^2 elements . I know that the best sorting algorithm is no better than O(n log n).Please answer in terms of the asymptotic notation.
answered Jan 5 in Algorithms reboot 170 views
0 votes
2 answers
22
In Merge sort Algorithm when I took input array of size 2 and I got 4 function calls as including original function call with which I call MS algorithm i.e. MS (1,2) and which in turn calls two recursive function calls to merge sort as MS (1,1) and MS (2,2) and ... of size 6 I got 16 function calls. So, how can I analyze the total number of function calls when input array size is n? thank you!
answered Jan 5 in Algorithms reboot 494 views
0 votes
2 answers
23
Describe an algorithm that, given $n$ integers in the range $0$ to $k$ preprocesses its input and then answers any query about how many of the $n$ integers fall into the range $[a..b]$ in $O(1)$ time.Your algorithm should use $\Theta(n+k)$ preprocessing time.
answered Jan 5 in Algorithms reboot 176 views
44 votes
11 answers
24
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}) $
answered Jan 4 in Algorithms reboot 14.3k views
54 votes
9 answers
25
In a permutation \(a_1 ... a_n\), of $n$ distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\). What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of \(1. . . n\) with at most $n$ inversions? \(\Theta(n^2)\) \(\Theta(n\log n)\) \(\Theta(n^{1.5})\) \(\Theta(n)\)
answered Jan 4 in Algorithms reboot 10.4k views
20 votes
6 answers
26
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. The value of $x_5$ is $5$ $7$ $8$ $16$
answered Jan 3 in Algorithms reboot 1.9k views
0 votes
2 answers
27
Which of the following statements is not true? 1.For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n2). 2.If we randomly choose a pivot element each time, quicksort will always terminate in time ... , quicksort would have worst case complexity O(n log n). 4.Quicksort and merge sort are both examples of divide and conquer algorithms.
answered Jan 3 in Algorithms aryavart 1.5k views
1 vote
2 answers
28
what is the time-complexity in kruskal algorithm for the overall step 2 where for each vertex Make-set function is called ? How come overall time for this step is O(v log v) ? We are performing this Operation for all the vertices in the Initial phase only so for ... Make-set operation only once right because after we come out of loop we have v sets of 1 vertex each . Please explain this clearly .
answered Jan 1 in Algorithms StoneHeart 358 views
0 votes
5 answers
29
I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. There is no mention to it in CLRS book. Please help. Thanks in advance.
answered Dec 31, 2020 in Algorithms vaibhavkedia968 3.6k views
2 votes
1 answer
30
29 votes
4 answers
31
You have $n$ lists, each consisting of $m$ integers sorted in ascending order. Merging these lists into a single sorted list will take time: $O(nm \log m)$ $O(mn \log n)$ $O(m + n)$ $O(mn)$
answered Dec 31, 2020 in Algorithms StoneHeart 2.4k views
49 votes
7 answers
32
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
answered Dec 20, 2020 in Algorithms reboot 14.3k views
0 votes
1 answer
33
Make a 3-by-3 chart with row and column labels WHITE, GRAY, and BLACK. In each cell ( , ) ij , indicate whether, at any point during a depth-first search of a directed graph, there can be an edge from a vertex of color i to a vertex of color j . For each possible edge, indicate what types it can be.
answered Dec 18, 2020 in Algorithms reboot 452 views
0 votes
1 answer
34
PARTITION(A,p,r) 1 x = A[r] 2 i = p – 1 3 for j = p to r – 1 4 if A[j] <= x 5 i = i + 1 6 exchange A[i] with A[j] 7 exchange A[i+1] with A[r] 8 return i + 1 illustrate the operation of PARTITION on the array $A=\langle 13,19,9,5,12,8,7,4,21,2,6,11\rangle$
answered Dec 16, 2020 in Algorithms ghostman23111 216 views
2 votes
3 answers
35
Consider the array A[]= {6,4,8,1,3} apply the insertion sort to sort the array . Consider the cost associated with each sort is 25 rupees , what is the total cost of the insertion sort when element 1 reaches the first position of the array ? (A) 50 (B) 25 (C) 75 (D) 100 Source: http://quiz.geeksforgeeks.org/algorithms-insertionsort-question-4/
answered Dec 15, 2020 in Algorithms omzzz 2.2k views
0 votes
3 answers
36
Merging k sorted lists of size n/k into one sorted list of n-elements using heap sort will take how much time ? My doubt First approach:- here it is mentioned heap sort so, heap sort will always take nlogn.and here also we have n elements and it will take nlogn. But ... it will give o(k)+(logk)*(n/k) I think answer should be nlogn only because the second approach is not heap sort. Please check.
answered Dec 14, 2020 in Algorithms omzzz 650 views
35 votes
4 answers
37
Consider the following game. There is a list of distinct numbers. At any round, a player arbitrarily chooses two numbers $a, b$ from the list and generates a new number $c$ by subtracting the smaller number from the larger one. The numbers $a$ and $b$ are put back in the list. If the number ... $273$. What is the score of the best player for this game? $40$ $16$ $33$ $91$ $123$
answered Dec 13, 2020 in Algorithms Mohnish 1.4k views
18 votes
3 answers
38
What is the weight of a minimum spanning tree of the following graph? $29$ $31$ $38$ $41$
answered Dec 10, 2020 in Algorithms StoneHeart 3.3k views
14 votes
4 answers
39
A set $X$ can be represented by an array $x[n]$ as follows: $x\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & \text{otherwise} \end{cases}$ Consider the following algorithm in which $x$, $y$, and $z$ are Boolean arrays of size $n$: algorithm zzz(x[], y[], z[]) { int i; ... y[i]); } The set $Z$ computed by the algorithm is: $(X\cup Y)$ $(X\cap Y)$ $(X-Y)\cap (Y-X)$ $(X-Y)\cup (Y-X)$
answered Dec 10, 2020 in Algorithms StoneHeart 2.3k views
20 votes
6 answers
40
Consider the function func shown below: int func(int num) { int count = 0; while (num) { count++; num>>= 1; } return (count); } The value returned by func($435$) is ________
answered Dec 10, 2020 in Algorithms StoneHeart 5.4k views
To see more, click for all the questions in this category.
...