search
Log In

Recent questions tagged algorithms

0 votes
2 answers
1
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
asked Mar 30 in Algorithms Lakshman Patel RJIT 176 views
0 votes
2 answers
2
Binary search tree is an example of : Divide and conquer technique Greedy algorithm Back tracking Dynamic Programming
asked Mar 27 in Algorithms jothee 115 views
0 votes
2 answers
3
The asymptotic upper bound solution of the recurrence relation given by $T(n)=2T \left ( \frac{n}{2} \right)+\frac{n}{\lg n} $ is: $O(n^{2})$ $O(n \lg n)$ $O(n \lg \lg n)$ $O(\lg \lg n)$
asked Mar 24 in Algorithms jothee 112 views
0 votes
4 answers
4
Any decision tree that sorts $n$ elements has height $\Omega (\lg n)$ $\Omega ( n)$ $\Omega (n \lg n)$ $\Omega ( n^{2})$
asked Mar 24 in Algorithms jothee 94 views
0 votes
2 answers
5
Red-black trees are one of many search tree schemes that are “balanced” in order to guarantee that basic dynamic–set operations take____ time in the worst case. $O(1)$ $O(\lg n)$ $O( n)$ $O(n \lg n)$
asked Mar 24 in Algorithms jothee 60 views
0 votes
2 answers
6
The minimum number of scalar multiplication required, for parenthesization of a matrix-chain product whose sequence of dimensions for four matrices is $< 5,10,3,12,5> $ is $630$ $580$ $480$ $405$
asked Mar 24 in Algorithms jothee 84 views
0 votes
2 answers
7
Dijkstra’s algorithm is based on Divide and conquer paradigm Dynamic programming Greedy approach Backtracking paradigm
asked Mar 24 in Algorithms jothee 66 views
0 votes
2 answers
8
Match the following with respect to algorithm paradigms: ...
asked Mar 24 in Algorithms jothee 102 views
0 votes
5 answers
9
Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array ? Insertion - $0(1)$, Deletion - $0(1)$, Maximum - $0(1)$, Minimum - $0(1)$ Insertion - $0(1)$, Deletion - $0(1)$, Maximum - $0(n)$, Minimum - $0(n)$ ... , Maximum - $0(1)$, Minimum - $0(1)$ Insertion - $0(n)$, Deletion - $0(n)$, Maximum - $0(n)$, Minimum - $0(n)$
asked Mar 24 in Algorithms jothee 99 views
0 votes
3 answers
10
Which of the following statements is false? Optimal binary search tree construction can be performed efficiently using dynamic programming. Breadth-first search cannot be used to find connected components of a graph. Given the prefix and postfix walks of a binary tree, the tree cannot be reconstructed uniquely. Depth-first-search can be used to find the connected components of a graph. a b c d
asked Mar 24 in Algorithms jothee 99 views
6 votes
4 answers
11
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$)
asked Feb 12 in Algorithms Arjun 3.3k views
1 vote
3 answers
12
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially? $\Theta (n^{4})$ $\Theta (n^{2})$ $\Theta (n^{2}\log n)$ $\Theta (n^{3})$
asked Feb 12 in Algorithms Arjun 1.6k views
6 votes
3 answers
13
Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ is_____________.
asked Feb 12 in Algorithms Arjun 2.2k views
5 votes
3 answers
14
Let $G = (V, G)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST of the resultant graph ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$
asked Feb 12 in Algorithms Arjun 2.5k views
11 votes
4 answers
15
Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the options completes the ... distance from $s$ to $u$ in the graph obtained by adding a new vertex $s$ to $G$ and edges of zero weight from $s$ to every vertex of $G$
asked Feb 12 in Algorithms Arjun 2.5k views
5 votes
4 answers
16
Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is ___________.
asked Feb 12 in Algorithms Arjun 1.7k views
2 votes
4 answers
17
Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j \mid$. The weight of minimum spanning tree of $G$ is _________
asked Feb 12 in Algorithms Arjun 928 views
3 votes
4 answers
18
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
asked Feb 11 in Algorithms Lakshman Patel RJIT 382 views
1 vote
2 answers
19
Consider product of three matrices $M_1,M_2$ and $M_3$ having $w$ rows and $x$ columns, $x$ rows and $y$ columns, and $y$ rows and $z$ columns. Under what condition will it take less time to compute the product as $(M_1M_2)M_3$ than to compute $M_1(M_2M_3)$ ? Always take the same time $(1/x +1/z)<(1/w+1/y)$ $x>y$ $(w+x)>(y+z)$
asked Jan 13 in Algorithms Satbir 297 views
5 votes
2 answers
20
What is the complexity of the following code? sum=0; for(i=1;i<=n;i*=2) for(j=1;j<=n;j++) sum++; Which of the following is not a valid string? $O(n^2)$ $O(n\log\ n)$ $O(n)$ $O(n\log\ n\log\ n)$
asked Jan 13 in Algorithms Satbir 705 views
3 votes
2 answers
21
Huffman tree is constructed for the following data :$\{A,B,C,D,E\}$ with frequency $\{0.17,0.11,0.24,0.33\ \text{and} \ 0.15 \}$ respectively. $100\ 00\ 01101$ is decoded as $BACE$ $CADE$ $BAD$ $CADD$
asked Jan 13 in Algorithms Satbir 488 views
3 votes
4 answers
22
If an array $A$ contains the items $10,4,7,23,67,12$ and $5$ in that order, what will be the resultant array $A$ after third pass of insertion sort? $67,12,10,5,4,7,23$ $4,7,10,23,67,12,5$ $4,5,7,67,10,12,23$ $10,7,4,67,23,12,5$
asked Jan 13 in Algorithms Satbir 538 views
2 votes
2 answers
23
The master theorem assumes the subproblems are unequal sizes can be used if the subproblems are of equal size cannot be used for divide and conquer algorithms cannot be used for asymptotic complexity analysis
asked Jan 13 in Algorithms Satbir 356 views
1 vote
3 answers
24
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
asked Jan 13 in Algorithms Satbir 315 views
1 vote
1 answer
25
Argue that since sorting $n$ elements takes $\Omega (n\ lgn)$ time in the worst case in the comparison model, any comparison-based algorithm for constructing a $BST$ from an arbitrary list of n elements takes $\Omega (n\ lgn)$ time in the worst case.
asked Nov 20, 2019 in Algorithms Kushagra गुप्ता 284 views
0 votes
2 answers
26
I am having difficulty in understanding np and np-hard topic in algorithms. If someone can provide some good source to learn about it in easy manner it would be a real help. Thank you!
asked Sep 22, 2019 in Algorithms luc_Bloodstone 156 views
1 vote
1 answer
27
Let $A$ be an $n\times n $ matrix of integers such that each row and each column is arranged in ascending order. We want to check whether a number $k$ appears in $A.$ If $k$ is present, we should report its position - that is, the row $i$ and column $j$ ... $2n$ values in $A.$ Justify the complexity of your algorithm. For both algorithms, describe a worst-case input where $k$ is present in $A.$
asked Sep 13, 2019 in Algorithms gatecse 85 views
1 vote
0 answers
28
A college professor gives several quizzes during the semester, with negative marking. He has become bored of the usual "Best $M$ out of $N$ quizzes" formula to award marks for internal assessment. Instead, each student will be evaluated based on the ... programming, the score the professor needs to award each student. Describe the space and time complexity of your dynamic programming algorithm.
asked Sep 13, 2019 in Algorithms gatecse 157 views
0 votes
3 answers
29
In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexity of quick sort. O($n^2$) O($n^3$) O(nlogn) O(n)
asked Sep 2, 2019 in Algorithms ajaysoni1924 841 views
0 votes
1 answer
30
A 3 way (ternary) min heap is a 3 way ( ternary - each node as atmost three children nodes, left, mid, right ) complete tree with min heap property ( value of the parent is less than the value of the children ) satisfied at every node. Given a ternary ... function. (c) In Heapsort, binary heap is preferred over ternary heap. State if this statement is true or false, you must justify your answer.
asked Aug 27, 2019 in Algorithms Shaik Masthan 170 views
...