# Recent questions and answers in Algorithms

1 vote
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
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)$
3
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
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$
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)$
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$
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}$
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}$
9
Solve the recurrence equations: $T(n) = T(n - 1)+ n$ $T(1) = 1$
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?
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
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=$ ___.
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)$.
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.
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)$
16
Algorithm design technique used in quicksort algorithm is? Dynamic programming Backtracking Divide and conquer Greedy method
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.
18
Quicksort is ________ efficient than heapsort in the worst case.
1 vote
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.
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})$
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.
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!
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.
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})$
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)$
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$
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.
1 vote
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 .
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.
30
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)$
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
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.
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$
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/
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.
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$
38
What is the weight of a minimum spanning tree of the following graph? $29$ $31$ $38$ $41$
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)$
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 ________