Dark Mode

Recent questions and answers in Algorithms

0 votes

1 answer

1

self doubt
Solve the following recurrences using recursion tree method and write the asymptotic time complexity T(n)=T(n/2)+n^2

Bharat Bhushan answered in Algorithms Mar 15

by Bharat Bhushan

97 views

1 vote

1 answer

2

Spanning Tree
Determine the number of the spanning treess in the following graph ???

ImPranav answered in Algorithms Mar 11

71 views

0 votes

0 answers

3

self doubt
Determine the number of spanning tree in the following graph ?

Çșȇ ʛấẗẻ asked in Algorithms Mar 10

by Çșȇ ʛấẗẻ

67 views

0 votes

0 answers

4

Self Doubt
Determine the number of the spanning treess in the following graph ???

Çșȇ ʛấẗẻ asked in Algorithms Mar 10

by Çșȇ ʛấẗẻ

37 views

0 votes

0 answers

5

Self doubt
Determine the number of the spanning treess in the following graph ???

Çșȇ ʛấẗẻ asked in Algorithms Mar 10

by Çșȇ ʛấẗẻ

27 views

0 votes

1 answer

6

let T(n) a function of complexity satisfying T(0)=T(1)=Θ(1) and T(n)=Θ(n)+T(n−1)+T(n−2). what is the class of complexity of T(n) ?

ImPranav answered in Algorithms Mar 10

164 views

0 votes

3 answers

7

Self Doubt
A recursion program without a terminating condition will provide infinite output. True/False?

ImPranav answered in Algorithms Mar 7

139 views

0 votes

2 answers

8

Chose the correct big- Θ expression to describe: T(N) = T(N / 2) + Log(N/2); T(1) = 1
I

KG answered in Algorithms Mar 5

by KG

94 views

0 votes

3 answers

9

NPTEL Assignment Question
Suppose there are k sorted lists (decreasing order) with n/k elements in each list. What is the time complexity to merge them into one single sorted list. Hint: Maintain a heap of k elements. Think which k elements to choose. A. O(nlogk) B. O(n) C. O(nk) D. O(nlogn)

[ Jiren ] answered in Algorithms Feb 24

364 views

3 votes

1 answer

10

GATE CSE 2023 | Question: 44
Consider functions $\textsf{Function_1}$ and $\textsf{Function_2}$ ... $f_{1}(n) \in \omega\left(f_{2}(n)\right)$ $f_{1}(n) \in O(n)$

DevUt answered in Algorithms Feb 18

by DevUt

1.3k views

1 vote

1 answer

11

GATE CSE 2023 | Question: 46
Let $U=\{1,2,3\}$. Let $2^{U}$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^{U}$. For any $A, B \in 2^{U},(A, B)$ is an edge in $G$ if and only if (i) $A \neq B$, and (ii) ... $A$ is denoted by $\mathcal{B}(A)$. If $\emptyset$ denotes the empty set, then the cardinality of $\mathcal{B}(\emptyset)$ is ______________.

Shaik Masthan answered in Algorithms Feb 16

by Shaik Masthan

873 views

3 votes

1 answer

12

GATE CSE 2023 | Question: 10
An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash ... a carefully chosen constant. Universal hashing method. If $k$ is a prime number, use Division method. Otherwise, use Multiplication method.

admin asked in Algorithms Feb 15

by admin

1.3k views

3 votes

0 answers

13

GATE CSE 2023 | Question: 19
Let $f$ and $g$ be functions of natural numbers given by $f(n)=n$ and $g(n)=n^{2}.$ Which of the following statements is/are $\text{TRUE}?$ $f \in O(g)$ $f \in \Omega(g)$ $f \in o(g)$ $f \in \Theta(g)$

admin asked in Algorithms Feb 15

by admin

1.3k views

0 votes

0 answers

14

GATE CSE 2023 | Memory Based Question: 37
Time complexity f( ) { while(n>1) { for (i = 1 to n) { } n = n/2 } } g ( ) { for (i = 1 to 100n) { } } $f(x)=O(g(x))$ $f(x)=\theta(g(x))$ $f(x)=o(g(x))$ $f(x)=\omega(g(x))$ closed

GO Classes asked in Algorithms Feb 6

548 views

3 votes

0 answers

15

Number of possible permutations that can be obtained using stack for input seq
Number of possible permutations that can be obtained using stack if the input sequence is 1, 2, 3, 4, 5 (in the order) is

h4kr asked in Algorithms Jan 31

by h4kr

138 views

45 votes

11 answers

16

GATE IT 2007 | Question: 24
A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ? $d[u] < d[v]$ $d[u] < f[v]$ $f[u] < f[v]$ $f[u] > f[v]$

supreetshukla answered in Algorithms Jan 30

by supreetshukla

10.6k views

0 votes

1 answer

17

TestBook testseries question to find max weight of MST
A complete graph G with 5 nodes has positive weight edges, each node has a distinct weight with an integer value and maximum weight is equal to number of edges in G. What can be the maximum weight of minimum spanning tree for graph G?

Pranavpurkar answered in Algorithms Jan 30

by Pranavpurkar

131 views

83 votes

11 answers

18

GATE CSE 2006 | Question: 48
Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$ ... exist a cycle in $G$ containing $u$ and $ν$ There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$

sameer_hack answered in Algorithms Jan 30

17.2k views

0 votes

1 answer

19

Countable languages in TOC

amit166 answered in Algorithms Jan 28

864 views

0 votes

0 answers

20

TestBook TestSeries Optimal Binary Search Tree Question
Construct OBST with the identifier set (a1, a2, a3) =(end , goto, print) with p(1..3) = (0.05, 0.2, 0.1) and q(0..3) = (0.2, 0.1,0.2, 0.05) What is the cost of a OBST ? What are the nodes present in the 2nd level of OBST if the root is present in level one ? 2.55 , print , goto 2.45 , goto , end 2.15, end, print 2.7, end, goto

Sahil_Lather asked in Algorithms Jan 28

by Sahil_Lather

87 views

0 votes

0 answers

21

TestBook TestSeries question to find number of paths in directed graph
Consider the following directed graph and assume the number of paths to reach to itself i.e. N(A) = 1. Number of paths from A to K are __

Sahil_Lather asked in Algorithms Jan 28

by Sahil_Lather

68 views

0 votes

0 answers

22

TestBook testSeries dynamic programming and np problem question
Consider the following statements, which of the statement(s) is/are FALSE? The running time of dynamic programming algorithm is always θ (p) where p is number of subproblems When a recurrence relation has cyclic dependency, it is ... memorization If a problem X can be reduced to a known NP hard problem, then X must be NP-hard

Sahil_Lather asked in Algorithms Jan 28

by Sahil_Lather

67 views

53 votes

7 answers

23

GATE CSE 2015 Set 2 | Question: 45
Suppose you are provided with the following function declaration in the C programming language. int partition(int a[], int n); The function treats the first element of $a[\:]$ as a pivot and rearranges the array so that all elements less than or equal to the pivot is in the ... $(a, $ left_end$, k)$ $(a, n-$left_end$-1, k-$left_end$-1)$ and $(a, $left_end$, k)$

eliecher answered in Algorithms Jan 24

13.1k views

0 votes

0 answers

24

Dijkstra Algorithm

Elaf asked in Algorithms Jan 22

by Elaf

100 views

0 votes

1 answer

25

UPPCL AE 2018:12
Given below are some famous algorithms and some algorithm design paradigms ... $\text{1-(c), 2-(b), 3-(a), 4-(b)}$

Hira Thakur answered in Algorithms Jan 21

194 views

0 votes

0 answers

26

Topic - Dijkstra Algorithm Question 5a

gate20232 asked in Algorithms Jan 18

70 views

0 votes

0 answers

27

Asymptotic Notation
Let $f(n)$ be a positive increasing function. Consider the below two statements: S1: if an algorithm is $\Theta(f(n))$ in the average case, then it is $\Omega(f(n))$ in the worst case. S2: if an algorithm is $\Theta(f(n))$ in the average case, then it is ... understand it mathematically. Also, $g(n) = \Theta(f(n))$ actually means $g(n)$ belongs to the set $\Theta(f(n))$, right?

kira000 asked in Algorithms Jan 17

131 views

63 votes

10 answers

28

GATE CSE 2002 | Question: 2.10
Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values: Choose an $i$ at random from $1..n$ If $A[i] = x$, then Stop else Goto 1; Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates? $n$ $n-1$ $2n$ $\frac{n}{2}$

Johnny1001 answered in Algorithms Jan 16

18.4k views

57 votes

7 answers

29

GATE CSE 2006 | Question: 12
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree

Johnny1001 answered in Algorithms Jan 15

27.5k views

56 votes

9 answers

30

GATE CSE 2014 Set 3 | Question: 14
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)$

Johnny1001 answered in Algorithms Jan 15

27.3k views

31 votes

6 answers

31

GATE CSE 1995 | Question: 1.16
For merging two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, we require comparisons of $O(m)$ $O(n)$ $O(m+n)$ $O(\log m + \log n)$

Johnny1001 answered in Algorithms Jan 15

42.5k views

4 votes

4 answers

32

NIELIT 2016 DEC Scientist B (CS) - Section B: 16
Two main measures for the efficiency of an algorithm are: Processor and Memory Complexity and Capacity Time and Space Data and Space

Johnny1001 answered in Algorithms Jan 15

75.8k views

7 votes

2 answers

33

number of spanning tree
Consider a complete bipartite graph with ‘m’ and ‘n’ vertices. If m = 4, n = 4, then the number of spanning trees of graph are ________.

Johnny1001 answered in Algorithms Jan 15

4.6k views

0 votes

0 answers

34

Test series
Can anyone solve this recurrence relation T(n) = 3T(n-1) + O(n^2) Its ans is O(3^n n^2)

MonuKhan asked in Algorithms Jan 12

289 views

0 votes

0 answers

35

Quiz question
Given the tight asymptotic bound for the recurrence equation : T(n) = 2T($\frac{n }4{}$) + 1 O(√ n) Ω(√ n) θ(√ n) O(n^2) Using master's theorem, the result comes to be θ(√ n). Thus option A,B,C are definitely correct. According to the solutions option D ... get it why. Can't we write (√ n) = O(n^2) ? Or is it because we are asked for the tightest asymptotic bound? Please do let know!

Aryanzzzz asked in Algorithms Jan 12

95 views

0 votes

1 answer

36

How to solve this recurrence T(n)=17T(7n)+n^4

nishantsharma answered in Algorithms Jan 12

by nishantsharma

188 views

0 votes

1 answer

37

nishantsharma answered in Algorithms Jan 12

by nishantsharma

118 views

0 votes

1 answer

38

how to solve T(n)=2T(n/2)−n^3n with master theorem
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n

nishantsharma answered in Algorithms Jan 12

by nishantsharma

199 views

0 votes

1 answer

39

#self_doubt
T(n)={ 0:if n<1 1:if n==1 T(n-1)+T(n-2):n>1 } if the stack size is 48 bytes and one stack entry size =4 B then maximum n=? I thought it should be 13 but the answer is 12 T(1) and T(<1) should not be stored they are already given so can we take n=13 so the last call which will be stored will be T(2)

nishantsharma answered in Algorithms Jan 11

by nishantsharma

140 views

1 vote

1 answer

40

CS Data structures and algorithm 2022
Design an algorithm to construct one heap that contains all the elements of two given heaps of sizes n and m, respectively. The heaps are given in a linked-list representation ( each node has links to its two children). The running time of the algorithm should be O(log(m + n)) in the worst case

nishantsharma answered in Algorithms Jan 11

by nishantsharma

137 views

To see more, click for all the questions in this category.

Recent questions and answers in Algorithms