search
Log In

Recent questions and answers in Algorithms

44 votes
10 answers
1
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ cannot have a cut vertex must have a cycle must have a cut-edge (bridge) has chromatic number strictly greater than those of $G_1$ and $G_2$
answered 5 days ago in Algorithms rish1602 6.2k views
1 vote
6 answers
2
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 5 days ago in Algorithms rish1602 5.2k views
35 votes
10 answers
3
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ ... of $G$ that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$
answered Jul 17 in Algorithms lovegate 10.2k views
1 vote
4 answers
4
why not merge sort?we don’t swap in merge sort,we just create auxillary arrays and merge them by changing elements in the original array.should we consider that as a swap?
answered Jul 15 in Algorithms rish1602 932 views
1 vote
3 answers
5
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 Jul 15 in Algorithms rish1602 666 views
2 votes
2 answers
6
An array $A$ of size n is known to be sorted except for the first $k$ elements and the last $k$ elements, where $k$ is a constant. Which of the following algorithms will be the best choice for sorting the array $A?$ $a)$Insertion Sort $b)$Bubble sort $c)$Quicksort ... ? Quick Sort sorts part by part using pivot. So, why not will it be answer?? How do we know it is asking for almost sorted array??
answered Jul 15 in Algorithms rish1602 960 views
2 votes
4 answers
7
Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input? Insertion sort Quick sort Merge sort Selection sort
answered Jul 15 in Algorithms rish1602 857 views
3 votes
5 answers
8
Given two sorted list of size '$m$' and '$n$' respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be : $m^{*}n$ minimum of $m, n$ maximum of $m, n$ $m+n-1$
answered Jul 15 in Algorithms rish1602 635 views
0 votes
2 answers
10
17 votes
6 answers
11
The minimum number of comparisons required to sort 5 elements is - a) 4 b) 5 c) 6 d) 7
answered Jul 10 in Algorithms rish1602 13k views
0 votes
1 answer
12
The difference of time Complexity between given functions can be represented by: void fun1(int n) { for(int i=1;i<=n;i++) for(int j=1;j<=i*i;j++) if(j%i==0) for(int k=1;k<=j;k++) s++; return 0; } void fun2(int n) { for(int i=1;i<=n;i++) for(int j=1;j<=i*i;j++) for(int k=1;k<=j;k++) s++; return 0; } $i. O(n^2)$ $ii. O(n)$ $iii.O(1)$ $iv. O(n^{1.5})$
answered Jul 10 in Algorithms rish1602 375 views
1 vote
1 answer
13
37 votes
3 answers
15
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A[0:n-1]$ is given below. Let $L_i$, denote the length of the longest monotonically increasing sequence starting at index $i$ in the array. ... bound paradigm The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm The algorithm uses divide and conquer paradigm
answered Jul 4 in Algorithms raja11sep 9.3k views
27 votes
8 answers
16
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
answered Jul 2 in Algorithms rish1602 10k views
48 votes
5 answers
17
Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ ... $y$ denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z=$ ______.
answered Jul 2 in Algorithms rish1602 11.8k views
22 votes
3 answers
18
What value would the following function return for the input $x=95$? Function fun (x:integer):integer; Begin If x > 100 then fun = x – 10 Else fun = fun(fun (x+11)) End; $89$ $90$ $91$ $92$
answered Jul 1 in Algorithms raja11sep 7.2k views
15 votes
3 answers
19
What function of $x$, $n$ is computed by this program? Function what(x, n:integer): integer: Var value : integer begin value := 1 if n > 0 then begin if n mod 2 =1 then value := value * x; value := value * what(x*x, n div 2); end; what := value; end;
answered Jul 1 in Algorithms raja11sep 1.4k views
1 vote
2 answers
20
Brute force algorithm time complexity for subset sum problem a) O(N logN) b)O(N^2) c) O(N^2 logN) d) O(2^N)
answered Jun 30 in Algorithms princeit07 895 views
45 votes
6 answers
21
When $n = 2^{2k}$ for some $k \geqslant 0$, the recurrence relation $T(n) = √(2) T(n/2) + √n$, $T(1) = 1$ evaluates to : $√(n) (\log n + 1)$ $√(n) \log n$ $√(n) \log √(n)$ $n \log √n$
answered Jun 27 in Algorithms npx 7.8k views
54 votes
7 answers
23
Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? $P$: Minimum spanning tree of $G$ does not change. $Q$: Shortest path between any pair of vertices does not change. $P$ only $Q$ only Neither $P$ nor $Q$ Both $P$ and $Q$
answered Jun 26 in Algorithms raja11sep 11.7k views
14 votes
8 answers
24
Consider a sequence of $14$ elements: $A=[-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]$. The sequence sum $S(i,j) = \Sigma_{k=i}^j A[k]$. Determine the maximum of $S(i,j)$, where $0 \leq i \leq j <14$. (Divide and conquer approach may be used.) Answer: ___________
answered Jun 26 in Algorithms rish1602 9.2k views
63 votes
11 answers
25
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.
answered Jun 26 in Algorithms deCiFer598 18.7k views
25 votes
7 answers
26
There are $n$ unsorted arrays: $A_1, A_2, \dots, A_n$. Assume that $n$ is odd.Each of $A_1, A_2, \dots, A_n$ contains $n$ distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of $A_1, A_2, \dots , A_n$ is $O(n)$ $O(n \: \log \: n)$ $O(n^2)$ $\Omega (n^2 \log n)$
answered Jun 26 in Algorithms rish1602 13.3k views
23 votes
3 answers
27
Consider a weighted undirected graph with vertex set $V = \{n1, n2, n3, n4, n5, n6 \}$ and edge set $E = \{(n1,n2,2), (n1,n3,8), (n1,n6,3), (n2,n4,4), (n2,n5,12), (n3,n4,7), (n4,n5,9), (n4,n6,4)\}$. The ... tree unique over all possible minimum spanning trees of a graph? Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?
answered Jun 24 in Algorithms raja11sep 2.8k views
20 votes
6 answers
28
Let $G$ be the directed, weighted graph shown in below figure We are interested in the shortest paths from $A$. Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node $A$ Write down sequence of vertices in the shortest path from $A$ to $E$ What is the cost of the shortest path from $A$ to $E$?
answered Jun 20 in Algorithms npx 4.3k views
6 votes
4 answers
29
Let $G$ be a connected undirected weighted graph. Consider the following two statements. $S_1$: There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$. $S_2$: If every edge in $G$ has distinct weight, then $G$ has a unique minimum spanning ... $S_1$ is true and $S_2$ is false $S_1$ is false and $S_2$ is true Both $S_1$ and $S_2$ are false
answered Jun 17 in Algorithms rish1602 2k views
1 vote
3 answers
30
2 votes
1 answer
31
Consider the problem of construction of minimum cost binary search tree for a given set of ‘n’ identifiers with their respective probabilities. The time complexity of the most efficient algorithm of the same is (A) $O(n^2)$ (B) $O(n^3)$ © $O(nlogn)$ (D) $O(n^3logn)$
answered Jun 16 in Algorithms rish1602 111 views
1 vote
1 answer
32
What is the best case and worst case of the algorithm? And when will best case and worst case will happen?? int main() { for(i=1 ; i<=n ; i++) { if(n%i == 0) { for(j=1 ; j<=n ; j++) { printf("Hello"); } } } }
answered Jun 16 in Algorithms rish1602 541 views
4 votes
4 answers
33
The concept of order (Big O) is important because— (a) it can be used to decide the best algorithm that solves a given problem (b) it determines the maximum size of a problem that can be solved in a given system, in a given amount of time (c) it is the lower bound of the growth rate of the algorithm (d) Both (a) and (b)
answered Jun 15 in Algorithms rish1602 8.1k views
1 vote
2 answers
34
The least running time of creating spanning tree from connected graph in G(E, V) is O (V log V) O (E + V log V) O (E log V) O (V log V + E log V) Where E, V are respectively number of edges & vertices in the graph.
answered Jun 15 in Algorithms rish1602 123 views
2 votes
3 answers
35
1 vote
1 answer
36
Deleting any random element in heap would take n+logn or n+n?
answered Jun 15 in Algorithms rish1602 226 views
3 votes
3 answers
38
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$
answered Jun 12 in Algorithms rish1602 1.4k views
8 votes
2 answers
39
Construct the Max Heap assuming the following set of integers were inserted into it in given order 20, 32, 1, 3, 4, 5, 6, 7, 10, 23, 45 Postorder traversal of the resultant max heap was stored in a array A with an index variable inorder (Starting from 0). Similarly ... j location values from A and B were obtained and |i - j| is calculated. What could be the maximum possible value for |i - j|?
answered May 25 in Algorithms Ronak.e3 1.1k views
45 votes
5 answers
40
Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum spanning trees of $G$ and $G'$, respectively, with total weights $t$ and $t'$ ... $T' = T$ with total weight $t' < t^2$ $T' \neq T$ but total weight $t' = t^2$ None of the above
answered May 23 in Algorithms thewolf 9.6k views
To see more, click for all the questions in this category.
...