# Recent questions and answers in Algorithms 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$
1 vote
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.
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$
1 vote
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?
1 vote
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!
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??
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
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$
9
The Knapsack problem belongs to which domain of problems? Optimization NP complete Linear Solution Sorting
10
Which of the following algorithm solve the all-pair shortest path problem? Dijakstra’s algorithm Floyd’s algorithm Prim’s algorithm Warshall’s algorithm
11
The minimum number of comparisons required to sort 5 elements is - a) 4 b) 5 c) 6 d) 7
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})$
1 vote
13
Please show the ideal way to deal with such comparisons as I am getting g>=f IN genral what logic shall be followed to analyse such complex comparions?
14
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
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 ____.
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=$ ______.
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$
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;
1 vote
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)
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$
22
T(n) = T$(\frac{n}{3})$ + T$(\frac{2n}{3})$ + O(n)
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$
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: ___________
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.
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)$
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?
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$?
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
1 vote
30
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
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)$
1 vote
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"); } } } }
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)
1 vote
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.
35
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
1 vote
36
Deleting any random element in heap would take n+logn or n+n?
37
Consider a procedure $find()$ which take array of $n$ ... Here we need to sort first and then need to compare adjacent element right?? Then what will be complexity??
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)$
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