search
Log In

Recent questions and answers in Algorithms

8 votes
4 answers
1
Consider the following function. Function F(n, m:integer):integer; begin If (n<=0 or (m<=0) then F:=1 else F:F(n-1, m) + F(n, m-1); end; Use the recurrence relation ... What is the value of $F(n, m)$? How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.
answered 9 minutes ago in Algorithms Jyotish Ranjan 1.6k views
25 votes
5 answers
2
What does the following algorithm approximate? (Assume $m > 1, \epsilon >0$). x = m; y = 1; While (x-y > ϵ) { x = (x+y)/2; y = m/x; } print(x); $\log \, m$ $m^2$ $m^{\frac{1}{2}}$ $m^{\frac{1}{3}}$
answered 2 days ago in Algorithms Jyotish Ranjan 7.2k views
2 votes
2 answers
3
Consider the following directed graph: Which of the following is/are correct about the graph? The graph does not have a topological order A depth-first traversal starting at vertex $S$ classifies three directed edges as back edges The graph does not have a strongly connected component For each pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$
answered 2 days ago in Algorithms Rish9799 558 views
42 votes
7 answers
4
In the following $C$ program fragment, $j$, $k$, $n$ and TwoLog_n are integer variables, and $A$ is an array of integers. The variable $n$ is initialized to an integer $\geqslant 3$, and TwoLog_n is initialized to the value of $2^*\lceil \log_2(n) \rceil$ for (k = 3; k <= n; k++) A[k] ... $\left\{m \mid m \leq n, \text{m is prime} \right\}$ { }
answered 2 days ago in Algorithms Jyotish Ranjan 6.5k views
65 votes
5 answers
5
In an adjacency list representation of an undirected simple graph $G=(V, E)$, each edge $(u, v)$ has two adjacency list entries: $[v]$ in the adjacency list of $u$, and $[u]$ in the adjacency list of $v$. These are called twins of each other. A twin pointer is a pointer from an ... list? $\Theta\left(n^{2}\right)$ $\Theta\left(n+m\right)$ $\Theta\left(m^{2}\right)$ $\Theta\left(n^{4}\right)$
answered 4 days ago in Algorithms Jyotish Ranjan 10.5k views
41 votes
6 answers
6
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one exists. Q: Finds whether any negative weighted cycle is reachable from the source. $P$ only $Q$ only Both $P$ and $Q$ Neither $P$ nor $Q$
answered 5 days ago in Algorithms Jyotish Ranjan 9.1k views
22 votes
4 answers
7
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 6 days ago in Algorithms himanshu dhawan 5k views
42 votes
9 answers
8
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is $O(n^2)$ $O(n \log n)$ $\Theta(n\log n)$ $O(n^3)$
answered 6 days ago in Algorithms himanshu dhawan 20.2k views
28 votes
4 answers
9
Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting $n$ ( $\geq $ 2) numbers? In the recurrence equations given in the options below, $c$ is a constant. $T(n) = 2 T (n/2) + cn$ $T(n) = T ( n - 1) + T(1) + cn$ $T(n) = 2T ( n - 1) + cn$ $T(n) = T (n/2) + cn$
answered 6 days ago in Algorithms himanshu dhawan 6k views
17 votes
6 answers
10
An array of $25$ distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to $2$ decimal places) is ________
answered 6 days ago in Algorithms himanshu dhawan 7.1k views
52 votes
11 answers
11
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 6 days ago in Algorithms soham04 13.1k views
42 votes
9 answers
12
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 Apr 7 in Algorithms Jyotish Ranjan 5.7k views
4 votes
3 answers
13
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$
answered Apr 6 in Algorithms heisenberggg 1.1k views
5 votes
3 answers
14
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)$
answered Apr 6 in Algorithms heisenberggg 1.8k views
0 votes
3 answers
15
Match the following with respect to algorithm paradigms: ... iii, b-i, c-ii, d-iv a-ii, b-i, c-iv, d-iii a-ii, b-i, c-iii, d-iv a-iii, b-ii, c-i, d-iv
answered Apr 6 in Algorithms heisenberggg 354 views
2 votes
3 answers
17
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 Apr 6 in Algorithms heisenberggg 447 views
3 votes
3 answers
18
For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers: $T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$ Which one of the following options is correct about the recurrence $T(n)$? If $f(n)$ is $n \log_2(n)$, then $T(n)$ ... $\Theta(n^{\log_b(a)})$ If $f(n)$ is $\Theta(n^{\log_b(a)})$, then $T(n)$ is $\Theta(n^{\log_b(a)})$
answered Apr 3 in Algorithms Nikhil_dhama 673 views
0 votes
2 answers
19
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 Apr 3 in Algorithms Nikhil_dhama 646 views
28 votes
7 answers
20
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ $\Theta(n^2)$
answered Apr 2 in Algorithms immanujs 11k views
4 votes
5 answers
21
Consider the following recurrence relation. $T\left ( n \right )=\left\{\begin{array} {lcl} T(n/2)+T(2n/5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$ Which one of the following options is correct? $T(n)=\Theta (n^{5/2})$ $T(n)=\Theta (n\log n)$ $T(n)=\Theta (n)$ $T(n)=\Theta ((\log n)^{5/2})$
answered Apr 1 in Algorithms Nikhil_dhama 1.2k views
19 votes
5 answers
22
Consider the program below: #include <stdio.h> int fun(int n, int *f_p) { int t, f; if (n <= 1) { *f_p = 1; return 1; } t = fun(n-1, f_p); f = t + *f_p; *f_p = t; return f; } int main() { int x = 15; printf("%d/n", fun(5, &x)); return 0; } The value printed is: $6$ $8$ $14$ $15$
answered Mar 31 in Algorithms Ashmita 6.1k views
1 vote
2 answers
23
Define $R_n$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i>0$, let $p[i]$ denote the selling price of a rod whose length is $i$ meters. Consider the array of prices: ... $R_7$? $R_7=18$ $R_7=19$ $R_7$ is achieved by three different solutions $R_7$ cannot be achieved by a solution consisting of three pieces
answered Mar 30 in Algorithms fenil_2022 874 views
1 vote
3 answers
25
Let $A$ be an array of $31$ numbers consisting of a sequence of $0$’s followed by a sequence of $1$’s. The problem is to find the smallest index $i$ such that $A[i]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is $2$ $4$ $3$ $5$
answered Mar 10 in Algorithms lovegate 366 views
0 votes
2 answers
26
Let $G$ be a graph with $n$ vertices and $m$ edges.What is the tightest upper bound on the running time of Depth First Search of $G$, when $G$ is represented using adjacency matrix? $O(n)$ $O(m+n)$ $O(n^2)$ $O(mn)$
answered Mar 10 in Algorithms lovegate 274 views
0 votes
3 answers
27
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 Mar 9 in Algorithms lovegate 673 views
0 votes
3 answers
28
A hash function $f$ defined as $f(\text{key})=\text{key mod }7$, with linear probing, insert the keys $37,38,72,48,98,11,56$ into a table indexed from $11$ will be stored in the location $3$ $4$ $5$ $6$
answered Mar 9 in Algorithms lovegate 391 views
0 votes
3 answers
29
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})$
answered Mar 9 in Algorithms lovegate 221 views
0 votes
2 answers
30
Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node $a$ ... $(a,b), (g,h), (g,f), (c,f), (c,i), (f,e), (b,c), (d,e)$
answered Mar 9 in Algorithms lovegate 121 views
0 votes
2 answers
31
Match $\text{list I}$ with $\text{List II}$ ... : $A-I, B-III, C-IV, D-II$ $A-III, B-I, C-IV, D-II$ $A-III, B-I, C-II, D-IV$ $A-I, B-III, C-II, D-IV$
answered Mar 9 in Algorithms lovegate 107 views
31 votes
7 answers
32
$\displaystyle \sum_{1\leq k\leq n} O(n)$, where $O(n)$ stands for order $n$ is: $O(n)$ $O(n^2)$ $O(n^3)$ $O(3n^2)$ $O(1.5n^2)$
answered Mar 8 in Algorithms jaffreyjoy 5k views
0 votes
3 answers
33
Consider the following C code segment: int Ls Prime(n) { int i,n; for(i=2;i<=sqrt(n);i++) if(n%i ==0) { printf( NOT Prime.\n ); return 0; } return 1; } Let $T(n)$ denote the number of times the for loop is executed by the program on input $n.$ ... $T(n) = O(\sqrt{n})$ and $T(n) = \Omega (1)$ $T(n) = O(n)$ and $T(n) = \Omega (\sqrt{n})$ None of these
answered Mar 1 in Algorithms lovegate 281 views
1 vote
2 answers
34
The most efficient algorithm for finding the number of connected components in a $n$ undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta (n)$ $\Theta (m)$ $\Theta (m+n)$ $\Theta (mn)$
answered Mar 1 in Algorithms lovegate 251 views
2 votes
1 answer
35
Let $A$ be array of $n$ integers that is not assumed to be sorted. You are given a number $x$. The aim is to find out if there are indices $k,\: l$ and $m$ such that $A[k] + A[l] + A[m] = x$. Design an algorithm for this problem that works in time $O(n^2)$.
answered Mar 1 in Algorithms s1lv3rj1nx 106 views
0 votes
3 answers
36
2 votes
3 answers
37
Consider the following three functions. $f_1=10^n\; f_2=n^{\log n}\;f_3=n^{\sqrt {n}}$ Which one of the following options arranges the functions in the increasing order of asymptotic growth rate? $f_3, f_2, f_1$ $f_2, f_1, f_3$ $f_1, f_2,f_3$ $f_2, f_3, f_1$
answered Feb 27 in Algorithms Harshq 467 views
4 votes
3 answers
38
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 Feb 25 in Algorithms harish3598 1k views
2 votes
2 answers
39
Consider the string $\textrm{abbccddeee}$. Each letter in the string must be assigned a binary code satisfying the following properties: For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. For any two letters ... assignments which satisfy the above two properties, what is the minimum length of the encoded string? $21$ $23$ $25$ $30$
answered Feb 19 in Algorithms Hira Thakur 514 views
0 votes
1 answer
40
Consider a $\textit{dynamic}$ hashing approach for $4$-bit integer keys: There is a main hash table of size $4$. The $2$ least significant bits of a key is used to index into the main hash table. Initially, the main hash table entries are empty. Thereafter, when more keys are hashed into it, to resolve ... in decimal notation)? $5,9,4,13,10,7$ $9,5,10,6,7,1$ $10,9,6,7,5,13$ $9,5,13,6,10,14$
answered Feb 18 in Algorithms Bhargav D Dave 6 388 views
To see more, click for all the questions in this category.
...