Register

Recent questions tagged go-alogrithms-1

2 2 votes
2 2 answers
1.0k
1.0k views
GATE Overflow | Algorithms | Test 1 | Question: 30
Match the following: i.BFSa.$O(\mid E \mid + \mid V \mid \log \mid V \mid)$ii.DFSb.$O(E)$iii.Kruskal's algorithmc.Stackiv.Dijikstra's Algorithmd.$O(E \log V)$i - b, ii - ...
User Avatar
2 2 votes
3 answers 3 answers
782
782 views
GATE Overflow | Algorithms | Test 1 | Question: 29
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___
User Avatar
2 2 votes
1 answers 1 answer
954
954 views
GATE Overflow | Algorithms | Test 1 | Question: 28
Match the following i.Dijkstra's Algorithma.All pairs shortest pathii.Bellman Ford Algorithmb.Greedyiii.Floyd-Warshall Algorithmc.Reweightingiv.Johnson Algorithmd.Single ...
User Avatar
1 1 vote
2 answers 2 answers
1.6k
1.6k views
GATE Overflow | Algorithms | Test 1 | Question: 27
Consider a hash table of size $m = 10$ and a corresponding hash function $h(k) = k A \mod m$ for $A = 5$ where collisions are resolved by quadratic probing. The location...
User Avatar
4 4 votes
1 answers 1 answer
966
966 views
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)$
User Avatar
3 3 votes
2 2 answers
1.0k
1.0k views
GATE Overflow | Algorithms | Test 1 | Question: 25
Which of the below options is TRUE for this statement :Suppose we wish to repeatedly search a linked list of length N elements, each of which contains a very long string ...
User Avatar
2 2 votes
1 1 answer
881
881 views
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 seque...
User Avatar
2 2 votes
2 answers 2 answers
1.4k
1.4k views
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)$
User Avatar
3 3 votes
2 answers 2 answers
2.5k
2.5k views
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 e...
User Avatar
4 4 votes
2 answers 2 answers
1.2k
1.2k views
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 mil...
User Avatar
4 4 votes
1 answers 1 answer
694
694 views
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...
User Avatar
2 2 votes
4 answers 4 answers
1.6k
1.6k views
GATE Overflow | Algorithms | Test 1 | Question: 19
Is an array that is sorted in decreasing order a max-heap?always yesalways nosometimes onlyyes but not in presence of duplicates
User Avatar
4 4 votes
2 answers 2 answers
1.3k
1.3k views
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 $...
User Avatar
2 2 votes
1 1 answer
1.2k
1.2k views
GATE Overflow | Algorithms | Test 1 | Question: 17
While inserting keys 12,44,13,88,23,94,11,39,20,16 and 5 in a 11 item hash table using the hash function $h(i) = (2i+5) \mod 11$, total number of collisions that occur ...
User Avatar
2 2 votes
1 answers 1 answer
686
686 views
GATE Overflow | Algorithms | Test 1 | Question: 16
The Matrix Chain-Product dynamic programming Algorithm runs in _______linear timeexponential timequadratic timecubic time
User Avatar
2 2 votes
1 answers 1 answer
1.4k
1.4k views
GATE Overflow | Algorithms | Test 1 | Question: 15
A delivery boy at an online e-commerce company is charged with the task of rearranging a number of large crates in order of the time they are to be shipped out. Thus, the...
User Avatar
2 2 votes
1 answers 1 answer
551
551 views
GATE Overflow | Algorithms | Test 1 | Question: 14
The result of performing an inorder search on the given tree iss y x z v u ty s x z v u ts y v u t z xv u t z x y s
User Avatar
4 4 votes
1 answers 1 answer
1.7k
1.7k views
GATE Overflow | Algorithms | Test 1 | Question: 13
You are given a 1 billion numbers. The time require in seconds to sort them provided sorting thousand numbers takes 100 microseconds will be _______10,00051230065536
User Avatar
1 1 vote
1 answers 1 answer
819
819 views
GATE Overflow | Algorithms | Test 1 | Question: 12
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...
User Avatar
3 3 votes
1 answers 1 answer
702
702 views
GATE Overflow | Algorithms | Test 1 | Question: 11
What is the running time of the following loop? Loop2(n) p < 1 for i < 1 to 2n do p < p*i$\Theta(n^2)$$\Theta(n)$$\Theta(n\lg n)$$\Theta(n^2\lg n)$
User Avatar
2 2 votes
2 answers 2 answers
1.2k
1.2k views
GATE Overflow | Algorithms | Test 1 | Question: 10
Consider the following recurrence relation.$$T(n) = \begin{cases}1 & \quad if \: n = 1 \\ T(n-1) + 2^n \quad & otherwise \end{cases}$$What will be the value of $T(10)$?
User Avatar
3 3 votes
1 answers 1 answer
1.2k
1.2k views
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)$$\Omeg...
User Avatar
3 3 votes
2 answers 2 answers
1.3k
1.3k views
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; }yesno because it fills only one slotno because it ...
User Avatar
2 2 votes
1 1 answer
828
828 views
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\...
User Avatar
2 2 votes
1 answers 1 answer
722
722 views
GATE Overflow | Algorithms | Test 1 | Question: 6
The time complexity of calculating $2^{100}$ isPolynomialExponentialConstantLinear
User Avatar
4 4 votes
5 answers 5 answers
1.8k
1.8k views
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 ...
User Avatar
7 7 votes
2 answers 2 answers
4.0k
4.0k views
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 ...
User Avatar
9 9 votes
2 answers 2 answers
2.0k
2.0k views
GATE Overflow | Algorithms | Test 1 | Question: 3
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)$...
User Avatar
3 3 votes
2 answers 2 answers
1.5k
1.5k views
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)$\Th...
User Avatar
8 8 votes
2 answers 2 answers
2.7k
2.7k views
GATE Overflow | Algorithms | Test 1 | Question: 1
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)$...
User Avatar
To see more, click for the full list of questions or popular tags.