Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Algorithms
Recent questions tagged algorithms
3
votes
1
answer
2611
GATE Overflow | Algorithms | Test 1 | Question: 26
Maximum element in a min-heap represented by an array, can be computed in _____ time $O(n)$ $O(\log n)$ $O(n \log n)$ but not $O(n)$ $O(1)$
Maximum element in a min-heap represented by an array, can be computed in _____ time$O(n)$$O(\log n)$$O(n \log n)$ but not $O(n)$$O(1)$
Bikram
502
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
binary-heap
algorithms
+
–
2
votes
1
answer
2612
GATE Overflow | Algorithms | Test 1 | Question: 24
Let you have an array $S[1 \dots n]$ and a function $reverse(s,i,j)$ which reverse the order of elements in $s$ between $i,j$-th positions. What does the following sequence do where $1\leq k\leq n$ ; reverse(s,1,k) reverse (s,1,n) reverse(s,k+1,n) rotate s by k position to left leaves s unchanged rotate s by k position to right none
Let you have an array $S[1 \dots n]$ and a function $reverse(s,i,j)$ which reverse the order of elements in $s$ between $i,j$-th positions. What does the following seque...
Bikram
474
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
+
–
2
votes
2
answers
2613
GATE Overflow | Algorithms | Test 1 | Question: 23
About how many compares will Quicksort() make when sorting an array of N items that are all equal? $\Theta(\lg N)$ $\Theta(N\lg N)$ $\Theta(\lg \lg N)$ $\Theta(N/\lg N)$
About how many compares will Quicksort() make when sorting an array of N items that are all equal?$\Theta(\lg N)$$\Theta(N\lg N)$$\Theta(\lg \lg N)$$\Theta(N/\lg N)$
Bikram
767
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
sorting
quick-sort
+
–
3
votes
2
answers
2614
GATE Overflow | Algorithms | Test 1 | Question: 22
Consider the below statements: Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Adding a constant to every edge weight does not change the solution to the minimum spanning tree problem. 1 is FALSE 2 is TRUE 1 is TRUE 2 is FALSE Both 1 and 2 are TRUE Both 1 and 2 are FALSE
Consider the below statements:Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.Adding a constant to every e...
Bikram
737
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
minimum-spanning-tree
shortest-path
+
–
3
votes
2
answers
2615
GATE Overflow | Algorithms | Test 1 | Question: 21
A spell-checker software reads an input file and prints out all words not in some online dictionary. Suppose the dictionary contains 10,000 words and the file has one million entries, so that the algorithm can make only one pass through the input file. ... the hash table is an array of pointers to words). 80,000 B 160,000 B 320,000 B 150,000 B
A spell-checker software reads an input file and prints out all words not in some online dictionary. Suppose the dictionary contains 10,000 words and the file has one mil...
Bikram
646
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
hashing
+
–
4
votes
1
answer
2616
GATE Overflow | Algorithms | Test 1 | Question: 20
Let $T(n)$ denote the number of times the for loop in below code is executed on any input $n$. What can be said about $T(n)$? int iscompute(int n) { for (int i=2;i<=sqrt(n); i++) if(n%i) == 0) { printf("not computed"); return 0; } return 1; } ... $T(n)= O(\sqrt n)$ and $T(n)= \Omega(1)$ $T(n)= O( n)$ and $T(n)= \Omega (\sqrt n)$ None
Let $T(n)$ denote the number of times the for loop in below code is executed on any input $n$. What can be said about $T(n)$?int iscompute(int n) { for (int i=2;i<=sqrt(n...
Bikram
369
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
asymptotic-notation
time-complexity
+
–
2
votes
4
answers
2617
GATE Overflow | Algorithms | Test 1 | Question: 19
Is an array that is sorted in decreasing order a max-heap? always yes always no sometimes only yes but not in presence of duplicates
Is an array that is sorted in decreasing order a max-heap?always yesalways nosometimes onlyyes but not in presence of duplicates
Bikram
601
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
sorting
heap-sort
+
–
3
votes
2
answers
2618
GATE Overflow | Algorithms | Test 1 | Question: 18
Time complexity of the optimal algorithm to interchange the $m^{th}$ and $n^{th}$ elements of a singly Linked List is $\Theta(m+n)$ $\Theta(m)$ when $m\geq n$ otherwise $\Theta(n)$ $\Theta(m)$ if $m \leq n$ otherwise $\Theta(n)$ $\Theta(m+ \min (m,n))$
Time complexity of the optimal algorithm to interchange the $m^{th}$ and $n^{th}$ elements of a singly Linked List is $\Theta(m+n)$$\Theta(m)$ when $m\geq n$ otherwise $...
Bikram
569
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
linked-list
+
–
2
votes
1
answer
2619
GATE Overflow | Algorithms | Test 1 | Question: 16
The Matrix Chain-Product dynamic programming Algorithm runs in _______ linear time exponential time quadratic time cubic time
The Matrix Chain-Product dynamic programming Algorithm runs in _______linear timeexponential timequadratic timecubic time
Bikram
329
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
dynamic-programming
time-complexity
+
–
1
votes
1
answer
2620
GATE Overflow | Algorithms | Test 1 | Question: 12
Match the following two columns given in a table: 1. Randomized quick sort a. $\Theta(n+k)$ 2. Insertion sort b. $\Theta\left(n^2\right)$ 3. selection sort c. $\Theta(n)$ 4. Bucket sort d. $\Theta(n\log n)$ 1- a; 2- c; 3 -b; 4- d; 1- c; 2- a; 3 -d; 4- b; 1- b; 2- d; 3 -a; 4- c; 1- d; 2- c; 3 -b; 4- a;
Match the following two columns given in a table:1. Randomized quick sorta. $\Theta(n+k)$2. Insertion sortb. $\Theta\left(n^2\right)$3. selection sortc. $\Theta(n)$4. Buc...
Bikram
350
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
sorting
time-complexity
match-the-following
easy
+
–
3
votes
1
answer
2621
GATE Overflow | Algorithms | Test 1 | Question: 9
Let we have 3 steps of an arbitrary program fragment whose running times are $O(n^2), \: O(n^3)$ and $O(n\log n)$, then the running time of whole program is $O(n^3)$ $\Omega(n^3)$ $\Omega(n \log n)$ $\Theta(n^6 \log n)$
Let we have 3 steps of an arbitrary program fragment whose running times are $O(n^2), \: O(n^3)$ and $O(n\log n)$, then the running time of whole program is$O(n^3)$$\Omeg...
Bikram
502
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
asymptotic-notation
time-complexity
+
–
3
votes
2
answers
2622
GATE Overflow | Algorithms | Test 1 | Question: 8
Is the following implementation of hashCode() legal assming a hashtable of size 20? public int hashCode(x) { return 17; } yes no because it fills only one slot no because it does not ensure uniform filling no because the hashcode is independent of the key
Is the following implementation of hashCode() legal assming a hashtable of size 20?public int hashCode(x) { return 17; }yesno because it fills only one slotno because it ...
Bikram
678
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
hashing
+
–
2
votes
1
answer
2623
GATE Overflow | Algorithms | Test 1 | Question: 7
Order the following functions by growth rate : $\log n$ $n/\log n$ $(3/2)^n$ $n\log^2 n$ a. $\log n$ $\quad$ b. $n/\log n$ $\quad$ d. $n\log^2 n$ $\quad$ c. $(3/2)^n$ d. $n\log^2 n$ $\quad$ c. (3/2)$^n$ $\quad$ a. $\log n$\quad$ b. $n/log n ... $\quad$ c. (3/2)$^n$ a. $\log n$ $\quad$ c. (3/2)$^n$ $\quad$ b. $n/\log n$ $\quad$ d. $n\log^2 n$
Order the following functions by growth rate :$\log n$$n/\log n$$(3/2)^n$$n\log^2 n$a. $\log n$ $\quad$ b. $n/\log n$ $\quad$ d. $n\log^2 n$ $\quad$ c. $(3/2)^n$ d. $n\...
Bikram
368
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
asymptotic-notation
+
–
2
votes
1
answer
2624
GATE Overflow | Algorithms | Test 1 | Question: 6
The time complexity of calculating $2^{100}$ is Polynomial Exponential Constant Linear
The time complexity of calculating $2^{100}$ isPolynomialExponentialConstantLinear
Bikram
401
views
Bikram
asked
Oct 4, 2016
Algorithms
go-alogrithms-1
algorithms
time-complexity
+
–
4
votes
5
answers
2625
GATE Overflow | Algorithms | Test 1 | Question: 5
If k is a non-negative constant, then the solution to the recurrence $T(n) = \begin{cases} 1 & \quad n=1 \\ 3T(n/2) + n & \quad n>1 \end{cases} $ for $n$, a power of 2 is $T(n) = 3^{\log_2 n} - 2n$ $T(n) = 2 \times 3^{\log_2 n} - 2n$ $T(n) = 3 \times 3^{\log_2 n} - 2n$ $T(n) = 3 \times 3^{\log_2 n} - 3n$
If k is a non-negative constant, then the solution to the recurrence$T(n) = \begin{cases} 1 & \quad n=1 \\ 3T(n/2) + n & \quad n>1 \end{cases} $for $n$, a power of 2 is ...
Bikram
871
views
Bikram
asked
Oct 3, 2016
Algorithms
go-alogrithms-1
algorithms
recurrence-relation
+
–
5
votes
2
answers
2626
GATE Overflow | Algorithms | Test 1 | Question: 4
Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1...n]$ having $n$ values : Sequentially choose $i$ from 1 to n if A[i] = x then Stop else Goto 1 Let $x$ be present in A two times, what is the expected no of comparisons made by the algorithm before it terminates for $n=5$?
Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1...n]$ having $n$ values : Sequentially choose $i$ from 1 to n if A[i] = x ...
Bikram
1.5k
views
Bikram
asked
Oct 3, 2016
Algorithms
go-alogrithms-1
algorithms
expectation
numerical-answers
+
–
8
votes
2
answers
2627
GATE Overflow | Algorithms | Test 1 | Question: 3
For the following program fragment, the running time is given by sum = 0; for(i = 1; i< n ; i++) for(j = 1; j<i; j++) if(i < j == 0) for(k = 0; k<j; k++) sum++; $\Theta(1)$ $\Theta(n)$ $\Theta \left(n^2\right)$ $\Theta\left(n^3\right)$
For the following program fragment, the running time is given bysum = 0; for(i = 1; i< n ; i++) for(j = 1; j<i; j++) if(i < j == 0) for(k = 0; k<j; k++) sum++;$\Theta(1)$...
Bikram
869
views
Bikram
asked
Oct 3, 2016
Algorithms
go-alogrithms-1
algorithms
time-complexity
programming-in-c
+
–
3
votes
2
answers
2628
GATE Overflow | Algorithms | Test 1 | Question: 2
The best known algorithm for binary to decimal conversion runs in $(n$ is the number of bits in the input number, assume MUL and ADD operations to take constant time) $\Theta(n)$ $\Theta(\log n)$ $\Theta(1)$ $\Theta\left(n^2\right)$
The best known algorithm for binary to decimal conversion runs in $(n$ is the number of bits in the input number, assume MUL and ADD operations to take constant time)$\Th...
Bikram
733
views
Bikram
asked
Oct 3, 2016
Algorithms
go-alogrithms-1
algorithms
time-complexity
+
–
4
votes
2
answers
2629
GATE Overflow | Algorithms | Test 1 | Question: 1
For the following program fragment, the running time is given by Procedure A(n) { if(n <= 2) return 1; else return A(log (n)); } $\Theta(\log \log n)$ $\Theta(\log \sqrt n)$ $\Theta(\log^* n)$ $\Theta(\sqrt n)$
For the following program fragment, the running time is given byProcedure A(n) { if(n <= 2) return 1; else return A(log (n)); }$\Theta(\log \log n)$$\Theta(\log \sqrt n)$...
Bikram
1.1k
views
Bikram
asked
Oct 3, 2016
Algorithms
go-alogrithms-1
algorithms
time-complexity
+
–
1
votes
1
answer
2630
UGC NET CSE | August 2016 | Part 3 | Question: 36
Match the following : ... $\text{a-iii, b-i, c-iv, d-ii}$ $\text{a-iii, b-i, c-ii, d-iv}$
Match the following :$\begin{array}{clcl} \text{a.} & \text{Prim’s algorithm} & \text{i.} & \text{$O(V^2E)$} \\ \text{b.} & \text{Bellman-Ford algorithm} & \text{ii.} ...
makhdoom ghaya
1.3k
views
makhdoom ghaya
asked
Oct 1, 2016
Algorithms
ugcnetcse-aug2016-paper3
algorithms
+
–
3
votes
2
answers
2631
UGC NET CSE | August 2016 | Part 3 | Question: 31
Consider the problem of a chain <$A_{1} , A_{2} , A_{3},A_{4}$> of four matrices. Suppose that the dimensions of the matrices $A_{1} , A_{2} , A_{3}$ and $A_{4}$ are $30 \times 35, 35 \times 15, 15 \times 5$ ... minimum number of scalar multiplications needed to compute the product $A_{1}A_{2}A_{3}A_{4}$ is ____. $14875$ $21000$ $9375$ $11875$
Consider the problem of a chain <$A_{1} , A_{2} , A_{3},A_{4}$ of four matrices. Suppose that the dimensions of the matrices $A_{1} , A_{2} , A_{3}$ and $A_{4}$ are $30 \...
makhdoom ghaya
2.3k
views
makhdoom ghaya
asked
Oct 1, 2016
Algorithms
ugcnetcse-aug2016-paper3
algorithms
dynamic-programming
numerical-answers
matrix
+
–
2
votes
1
answer
2632
Virtual Gate Test Series: Algorithms - Hashing With Chaining
Let $| U | = m^{2}$ and consider hashing with chaining. For any hash function $h : U\rightarrow{ 1, 2, ......., m-1}, $ there exists a sequence of $m$ insertions that leads to a chain of length $:$ $(A) m-1$ $(B) m$ ($C) m+1$ $(D)$ None. i got (m-2) max length .....option D
Let $| U | = m^{2}$ and consider hashing with chaining. For any hash function $h : U\rightarrow{ 1, 2, ......., m-1}, $ there exists a sequence of $m$ insertions that lea...
Hradesh patel
1.3k
views
Hradesh patel
asked
Oct 1, 2016
Algorithms
algorithms
hashing
virtual-gate-test-series
+
–
3
votes
1
answer
2633
Average complexity of a code segment
//example program setup #include <stdio.h> #define n 9 int main() { // arr[n] is initialized with same random values int arr[n] = {2,3,-4,1,0,6,2,3,4}; int j,m; j = n-1; //last index m = arr[n-1]; // last value int k ... ); return 0; } O/P : 6 5 what is the no of times the else block executes when the n can be large enough with randomly initialized value ?
//example program setup #include <stdio.h #define n 9 int main() { // arr[n] is initialized with same random values int arr[n] = {2,3,-4,1,0,6,2,3,4}; int j,m; j = n-1; /...
dd
489
views
dd
asked
Sep 26, 2016
Algorithms
algorithms
time-complexity
programming-in-c
+
–
0
votes
1
answer
2634
Virtual Test series
Jhunjhunuwala
358
views
Jhunjhunuwala
asked
Sep 25, 2016
Algorithms
algorithms
huffman-code
virtual-gate-test-series
match-the-following
+
–
2
votes
2
answers
2635
Complexity finding of c program
#include <stdio.h> int main() { int x,y = 0; //assume a[] as any array. for(x = 0; x < n; ++x) { while(y < n && arr[x] < arr[y]) y++; } return 0; }
#include <stdio.h int main() { int x,y = 0; //assume a[] as any array. for(x = 0; x < n; ++x) { while(y < n && arr[x] < arr[y]) y++; } return 0; }
dd
496
views
dd
asked
Sep 25, 2016
Algorithms
programming-in-c
algorithms
time-complexity
+
–
1
votes
1
answer
2636
Virtual Test series
Jhunjhunuwala
317
views
Jhunjhunuwala
asked
Sep 25, 2016
Algorithms
virtual-gate-test-series
huffman-code
algorithms
+
–
3
votes
3
answers
2637
time complexity
Find the time complexity of the following snippets 1. for$\left ( i=1;i\leqslant n;i++ \right )$ for$\left ( j=n/3;j\leqslant 2n;j=j+n/3 \right )$ $x=x+1;$ 2. for$\left ( i=1;i\leqslant n;i++ \right )$ for$\left ( j=1;j\leqslant n;j=j+i \right )$ $x=x+1;$
Find the time complexity of the following snippets1.for$\left ( i=1;i\leqslant n;i++ \right )$ for$\left ( j=n/3;j\leqslant 2n;j=j+n/3 \right )$ $x=x...
Vishal Goyal
784
views
Vishal Goyal
asked
Sep 24, 2016
DS
data-structures
time-complexity
algorithms
expression
+
–
17
votes
1
answer
2638
MadeEasy Test Series: Algorithms - Graph Algorithms
For the graph given below Dijkstra's algorithm does not provide correct shortest path tree. Suppose a new graph that is different only in weight between Q to S is created. The number of values of edge [Q to S] that ensures that Dijkstra's provide the ... tree where the values of edge (Q to S) ∈ [-20, 20] and P' is the source vertex are ______.
For the graph given below Dijkstra’s algorithm does not provide correct shortest path tree.Suppose a new graph that is different only in weight between Q to S is create...
User007
2.4k
views
User007
asked
Sep 24, 2016
Algorithms
made-easy-test-series
algorithms
graph-algorithms
shortest-path
dijkstras-algorithm
+
–
4
votes
1
answer
2639
MadeEasy Test Series: Algorithms - Sorting
Consider the following code executed on an n-element array A such that each element i an A satisfies the condition 0 ≤ A[i] < 1. The code also uses an auxiliary array, B[0 to n - 1]. Random-Sort (A) { 1. n ← Length ... order. } Which algorithm will be placed in the blank at line 5 for sorting (stable) so that the code will give minimum time complexity?
Consider the following code executed on an n-element array A such that each element i an A satisfies thecondition 0 ≤ A[i] < 1. The code also uses an auxiliary array, B...
User007
3.4k
views
User007
asked
Sep 24, 2016
Algorithms
made-easy-test-series
algorithms
sorting
+
–
0
votes
1
answer
2640
Modified Insertion sort
Insertion Sorts complexity is O(n+d) where d is no. of inversions. (There are some questions in gate where no. of inversions are given in terms of n.) I am unable to Understand this complexity Derivation. Plz make me understand. Thank U.
Insertion Sorts complexity is O(n+d) where d is no. of inversions.(There are some questions in gate where no. of inversions are given in terms of n.)I am unable to Under...
Rajesh Pradhan
861
views
Rajesh Pradhan
asked
Sep 24, 2016
Algorithms
algorithms
sorting
+
–
Page:
« prev
1
...
83
84
85
86
87
88
89
90
91
92
93
...
118
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register