Dark Mode

Recent questions tagged go-alogrithms-1

2 votes

2 answers

1

GATE Overflow | Algorithms | Test 1 | Question: 30
Match the following: i. BFS a. $O(\mid E \mid + \mid V \mid \log \mid V \mid)$ ii. DFS b. $O(E)$ iii. Kruskal's algorithm c. Stack iv. Dijikstra's Algorithm d. $O(E \log V)$ i - b, ii - c, iii - a, iv - d i - c, ii - b, iii - d, iv - a i - b, ii - c, iii - d, iv - a i - c, ii - d, iii - a, iv - b

Bikram asked in Algorithms Oct 4, 2016

by Bikram

458 views

2 votes

2 answers

2

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 ___

Bikram asked in Algorithms Oct 4, 2016

by Bikram

352 views

2 votes

1 answer

3

GATE Overflow | Algorithms | Test 1 | Question: 28
Match the following i. Dijkstra's Algorithm a. All pairs shortest path ii. Bellman Ford Algorithm b. Greedy iii. Floyd-Warshall Algorithm c. Reweighting iv. Johnson Algorithm d. Single source shortest path i - c, ii - d, iii - a, iv - b i - d, ii - a, iii - c, iv - b i - b, ii - d, iii - a, iv - c i - d, ii - b, iii - a, iv - c

Bikram asked in Algorithms Oct 4, 2016

by Bikram

444 views

1 vote

2 answers

4

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 (starting from 1) to which the key 65 is mapped if the current contents of hashtable is $4 \;8 \;\_ \;\_ \;7 \;8 \;6 \;\_\; 0\; \_$ is _______

Bikram asked in Algorithms Oct 4, 2016

by Bikram

736 views

3 votes

1 answer

5

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)$

Bikram asked in Algorithms Oct 4, 2016

by Bikram

509 views

3 votes

2 answers

6

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 key. How might we take advantage of the hash value when ... precompute the hash value of each string in the list calculate hash value of the single string only none of the above

Bikram asked in Algorithms Oct 4, 2016

by Bikram

502 views

2 votes

1 answer

7

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

Bikram asked in Algorithms Oct 4, 2016

by Bikram

487 views

2 votes

2 answers

8

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)$

Bikram asked in Algorithms Oct 4, 2016

by Bikram

782 views

3 votes

2 answers

9

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

Bikram asked in Algorithms Oct 4, 2016

by Bikram

750 views

3 votes

2 answers

10

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

Bikram asked in Algorithms Oct 4, 2016

by Bikram

667 views

4 votes

1 answer

11

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

Bikram asked in Algorithms Oct 4, 2016

by Bikram

373 views

2 votes

4 answers

12

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

Bikram asked in Algorithms Oct 4, 2016

by Bikram

620 views

3 votes

2 answers

13

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))$

Bikram asked in Algorithms Oct 4, 2016

by Bikram

574 views

2 votes

1 answer

14

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 is _________ (On collision no insertion takes place)

Bikram asked in Algorithms Oct 4, 2016

by Bikram

558 views

2 votes

1 answer

15

GATE Overflow | Algorithms | Test 1 | Question: 16
The Matrix Chain-Product dynamic programming Algorithm runs in _______ linear time exponential time quadratic time cubic time

Bikram asked in Algorithms Oct 4, 2016

by Bikram

333 views

2 votes

1 answer

16

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 cost of compares is very low (just look at the ... of the crates, but not two. Which sorting method should the boy use? heap sort quick sort selection sort randomized quick sort

Bikram asked in Algorithms Oct 4, 2016

by Bikram

662 views

2 votes

1 answer

17

GATE Overflow | Algorithms | Test 1 | Question: 14
The result of performing an inorder search on the given tree is s y x z v u t y s x z v u t s y v u t z x v u t z x y s

Bikram asked in DS Oct 4, 2016

by Bikram

248 views

3 votes

1 answer

18

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,000 512 300 65536

Bikram asked in Algorithms Oct 4, 2016

by Bikram

851 views

1 vote

1 answer

19

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;

Bikram asked in Algorithms Oct 4, 2016

by Bikram

352 views

3 votes

1 answer

20

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)$

Bikram asked in Algorithms Oct 4, 2016

by Bikram

334 views

2 votes

2 answers

21

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)$?

Bikram asked in Algorithms Oct 4, 2016

by Bikram

561 views

3 votes

1 answer

22

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)$

Bikram asked in Algorithms Oct 4, 2016

by Bikram

523 views

3 votes

2 answers

23

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

Bikram asked in Algorithms Oct 4, 2016

by Bikram

696 views

2 votes

1 answer

24

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$

Bikram asked in Algorithms Oct 4, 2016

by Bikram

386 views

2 votes

1 answer

25

GATE Overflow | Algorithms | Test 1 | Question: 6
The time complexity of calculating $2^{100}$ is Polynomial Exponential Constant Linear

Bikram asked in Algorithms Oct 4, 2016

by Bikram

406 views

4 votes

5 answers

26

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$

Bikram asked in Algorithms Oct 3, 2016

by Bikram

898 views

5 votes

2 answers

27

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$?

Bikram asked in Algorithms Oct 3, 2016

by Bikram

1.5k views

8 votes

2 answers

28

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)$

Bikram asked in Algorithms Oct 3, 2016

by Bikram

903 views

3 votes

2 answers

29

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)$

Bikram asked in Algorithms Oct 3, 2016

by Bikram

747 views

4 votes

2 answers

30

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)$

Bikram asked in Algorithms Oct 3, 2016

by Bikram

1.1k views

To see more, click for the full list of questions or popular tags.

Recent questions tagged go-alogrithms-1