search
Log In

Recent questions and answers in Algorithms

46 votes
13 answers
1
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] == 1) counter++; ... 0;} } The complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(n)$
answered 1 day ago in Algorithms Madhab 8.8k views
69 votes
6 answers
2
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)$
answered 2 days ago in Algorithms varunrajarathnam 11.8k views
23 votes
2 answers
3
Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort? $O(\log n$) $O(n$) $O(n \log n$) $O(n^{2}$)
answered 2 days ago in Algorithms varunrajarathnam 3.3k views
18 votes
4 answers
4
Let $n$ be a large integer. Which of the following statements is TRUE? $2^{\sqrt{2\log n}}< \frac{n}{\log n}< n^{1/3}$ $\frac{n}{\log n}< n^{1/3}< 2^{\sqrt{2\log n}}$ $2^\sqrt{{2\log n}}< n^{1/3}< \frac{n}{\log n}$ $n^{1/3}< 2^\sqrt{{2\log n}}<\frac{n}{\log n}$ $\frac{n}{\log n}< 2^\sqrt{{2\log n}}<n^{1/3}$
answered 2 days ago in Algorithms ankitgupta.1729 1.5k views
0 votes
1 answer
5
How to analyze this problem For (I=1;I<n;I++) { For (j=1;j<n;j=j+I) { Print("℅d℅d", I,j); } } Please suggest I'm detail how do we unroll I & j.
answered 2 days ago in Algorithms arun yadav 101 views
0 votes
1 answer
6
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 2 days ago in Algorithms arun yadav 221 views
0 votes
1 answer
7
what is the time complexity of the $pow(m,n)$ ?
answered 2 days ago in Algorithms arun yadav 116 views
49 votes
7 answers
8
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 3 days ago in Algorithms Musa 8.5k views
26 votes
4 answers
9
An array $A$ contains $n$ integers. We wish to sort $A$ in ascending order. We are told that initially no element of $A$ is more than a distance $k$ away from its final position in the sorted list. Assume that $n$ and $k$ are large and $k$ is much smaller ... with constant $.n \log k$ comparisons but not with fewer comparisons. $A$ can be sorted with constant $.k^{2}n$ comparisons but not fewer.
answered 3 days ago in Algorithms Gaurav Chaudhari 1.1k views
0 votes
3 answers
10
Is it possible that a disconnected graph is an Euler graph ?
answered 4 days ago in Algorithms anbor777 293 views
58 votes
6 answers
11
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 ____.
answered 4 days ago in Algorithms varunrajarathnam 8.7k views
39 votes
5 answers
12
Assume that a mergesort algorithm in the worst case takes $30$ seconds for an input of size $64$. Which of the following most closely approximates the maximum input size of a problem that can be solved in $6$ minutes? $256$ $512$ $1024$ $2018$
answered 5 days ago in Algorithms varunrajarathnam 6.9k views
18 votes
3 answers
13
The worst case running times of Insertion sort , Merge sort and Quick sort, respectively are: $\Theta (n \log n)$, $\Theta (n \log n)$ and $\Theta(n^2)$ $\Theta (n^2)$, $\Theta (n^2)$ and $\Theta(n \log n)$ $\Theta (n^2)$, $\Theta (n \log n)$ and $\Theta (n \log n)$ $\Theta (n^2)$, $\Theta (n \log n)$ and $\Theta (n^2)$
answered 5 days ago in Algorithms varunrajarathnam 3k views
26 votes
5 answers
14
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE? Quicksort runs in $\Theta (n^2)$ time Bubblesort runs in $\Theta (n^2)$ time Mergesort runs in $\Theta (n)$ time Insertion sort runs in $\Theta (n)$ time I and II only I and III only II and IV only I and IV only
answered 5 days ago in Algorithms varunrajarathnam 5.1k views
47 votes
15 answers
15
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)$
answered 5 days ago in Algorithms Sree008 10.4k views
32 votes
5 answers
16
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if(Y[k] ... $x > 2$ $Y$ is $[2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20]$ and $ 2 < x < 20$ and $x$ is even
answered 6 days ago in Algorithms Musa 8.1k views
7 votes
5 answers
17
For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is $\Theta (\log_a \log _b n)$ $\Theta (\log_{ab} n$) $\Theta (\log_{b} \log_{a} \: n$) $\Theta (\log_{2} \log_{2} n$)
answered Sep 19 in Algorithms Musa 4.2k views
1 vote
1 answer
18
Consider a set of 156 elements to find minimum and maximum elements in the given set, the minimum number of comparisons required is___? You have given an array of 512 elements,minimum number of comparisons required to find out second largest element among all will be___? 230 & 517 229 & 516 231 & 518 232 & 519
answered Sep 19 in Algorithms debasish paramanik 199 views
0 votes
1 answer
19
A min heap having $1024$ distinct elements with keys ranging from $0$ to $1023$ is stored in array of $1024$ indices. The maximum difference between $(n/2)^{th}$ element present at maximum level and minimum level is ________. [Assume root is present at $level-1$] ? Please Tell me the Approach
answered Sep 19 in Algorithms arun yadav 119 views
1 vote
2 answers
20
17 votes
5 answers
21
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 Sep 18 in Algorithms gatecse 1.5k views
49 votes
6 answers
22
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 Sep 18 in Algorithms endurance1 7.9k views
29 votes
5 answers
23
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid i-j\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is $11$ $25$ $31$ $41$
answered Sep 17 in Algorithms endurance1 5.2k views
16 votes
5 answers
24
Give an optimal algorithm in pseudo-code for sorting a sequence of $n$ numbers which has only $k$ distinct numbers ($k$ is not known a Priori). Give a brief analysis for the time-complexity of your algorithm.
answered Sep 16 in Algorithms vaibhavkedia968 2.3k views
6 votes
3 answers
25
What is the time complexity of job sequencing with deadline using greedy algorithm? O(n) O(log n) O(n log n) O(n2) Made Easy Full Syllabus Test-6 : Basic Level : Practice Test-14 Q 19 Please give reference for this answer to this algorithm.
answered Sep 14 in Algorithms manikantsharma 7.6k views
42 votes
7 answers
26
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 it 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 Sep 13 in Algorithms Junaid khan290 5.6k views
3 votes
2 answers
28
An array $A$ contains $n$ integers in locations $A[0], A[1], \dots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $K$ places, where $1\leq K \leq n-1$. An incomplete algorithm for doing this in linear time, without using another array is given below. Complete ... A[j]:=____; j:=(j+K) mod n; if j<min then min:=j; end; A[(n+i-K)mod n]:=____; i:=______; end;
answered Sep 13 in Algorithms Junaid khan290 1.1k views
50 votes
10 answers
29
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 report that there is ... $\Theta (n)$ time and space Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number
answered Sep 12 in Algorithms varunrajarathnam 9.3k views
11 votes
5 answers
32
Let $T$ be a Depth First Tree of a undirected graph $G$. An array $P$ indexed by the vertices of $G$ is given. $P[V]$ is the parent of vertex $V$, in $T$. Parent of the root is the root itself. Give a method for finding and printing the ... be proportional to the length of the cycle. Describe the algorithm in a PASCAL $(C)$ - like language. Assume that the variables have been suitably declared.
answered Sep 11 in Algorithms Junaid khan290 1.8k views
18 votes
4 answers
33
Consider the following graph: Among the following sequences: abeghf abfehg abfhge afghbe Which are the depth-first traversals of the above graph? I, II and IV only I and IV only II, III and IV only I, III and IV only
answered Sep 11 in Algorithms KUSHAGRA गुप्ता 3.3k views
0 votes
2 answers
34
Which of the following standard algorithms is not Dynamic Programming based? Bellman-Ford Algorithm for single source shortest path Floyd Warshall Algorithm for all pairs shortest paths $0-1$ Knapsack problem Prim’s Minimum Spanning Tree
answered Sep 11 in Algorithms Sanandan 154 views
4 votes
3 answers
36
US portal Denominations are 1,10,21,34,70 , 100 and 350 . A) Make 140 Cents . Verify whether Greedy choice fails or not B) Make 182 Cents. Verify whether greedy choice fails or not. 1)Greedy fails in A 2) Greedy fails in B 3)Greedy does not fails in A 4)Greedy does not fails in B
answered Sep 11 in Algorithms Sanandan 847 views
0 votes
2 answers
37
Single source shortest path problems can be implemented by greedy algorithms using A. Singly linked list B. Min heap C. AVL tree D. All of the above
answered Sep 11 in Algorithms Sanandan 249 views
0 votes
2 answers
38
Consider the following code segment to find the $n^{th}$ Fibonacci number: Fib(n) { if(n==0) {return 0;} if(n==1) {return 1;} else { return(Fib(n-1) + Fib(n-2)); } } The time complexity of the above code and time complexity of the same problem solved using dynamic programming is______ $A)O(n^{2}),O(n)$ $B)O(2^{n}),O(n)$ $C)O(2^{n}),O(n^{2})$ $D)$None of the above
answered Sep 11 in Algorithms Sanandan 361 views
2 votes
3 answers
39
If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ? A O(m logn) B O(n) C O(m) D O(n logm)
answered Sep 11 in Algorithms Sanandan 364 views
3 votes
3 answers
40
Consider the following steps: $S_1$: Characterize the structure of an optimal solution $S_2$: Compute the value of an optimal solution in bottom-up fashion Which of the following step(s) is/are common to both dynamic programming and greedy algorithms? Only $S_1$ Only $S_2$ Both $S_1$ and $S_2$ Neither $S_1$ nor $S_2$
answered Sep 11 in Algorithms Sanandan 797 views
To see more, click for all the questions in this category.
...