Recent questions and answers in Algorithms

0 votes

0 answers

Algorithms - Time Complexity analysis
1 .Let P be the problem. Suppose that the worst case asymptotic running time complexity of P is in O($n^2$lgn) and is also in Ω(n). Now let A be an algorithm that solves P. Which of the following is correct about A: A has worst-case time ... time case complexity of an algorithm is θ(n). The Algorithm executes in time T(n) = Ω($n^2$) for every input data.

asked 1 day ago in Algorithms by sagar2405 (192 points) | 10 views

0 votes

0 answers

Algorithms - Time complexity
1 .Solve the recurrence: $T(n) = 2T(\sqrt n) + log\ n$ $T(n) = T(\frac{n}{2}) + 2T(\frac{n}{4}) +n$ 2 .$f(n) = n^{1.01}$ and $g(n) = n(log\ n)^2$ then which one is true $f(n) = O(g(n))$ $f(n) = \Omega(g(n))$ $f(n) = \Theta(g(n))$ 3 . $f(n) = n^{\frac{1}{2}}, g(n) = 1$, then is it correct $g(n) = o(fn)$ {$o$ = small o Not big $O$} Please solve the above questions.

asked 1 day ago in Algorithms by sagar2405 (192 points) | 11 views

0 votes

0 answers

Sorting algorithm
An unsorted array of n elements is given to you and you have to print largest 10% of them. This can be done on time O(1) O(n) O(logn) O(nlogn)

asked 2 days ago in Algorithms by sagar2405 (192 points) | 20 views

0 votes

0 answers

f(m,n) { ans = 1; count = 0; while (ans <= m) { count = count + 1; ans = ans * n; } return(count) }

asked 2 days ago in Algorithms by Karlasravani (102 points) | 10 views

0 votes

1 answer

Made easy Algorithm
Which of the following procedure is suitable for finding the longest path from given vertex to any other vertex in a directed acyclic graph(weighted) with few negative weight edge. Divide and conquer Greedy algorithm Dynamic programming All of the above

answered 3 days ago in Algorithms by Debargha Bhattacharj (1.3k points) | 9 views

0 votes

0 answers

Made easy test series - Algorithm
How to do find 0/1 knapsack in minimum time?

asked 4 days ago in Algorithms by sagar2405 (192 points) | 13 views

0 votes

0 answers

proof n= O(nlogn) ....can any one explain the proof?

asked 4 days ago in Algorithms by subhadip997 (105 points) | 7 views

0 votes

0 answers

I have a doubt in GATE 2014-2 question of finding number of comparisons needed to merge sorted lists into a single list

asked 4 days ago in Algorithms by Syed Sauban (102 points) | 2 views

0 votes

0 answers

#Algorithms #Graphs Minimum Number of edges.
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from vertex i to a vertex j iff either j = i+1 or j = 4i. The minimum number of edges in a path in G from vertex 1 to 100 is ? I am getting 6 ... as answer but correct answer is 9 edges. The pattern of edges I'm following - 1 → 4 → 5 → 6 -→ 24 → 25 → 100

asked 4 days ago in Algorithms by iarnav (159 points) | 6 views

0 votes

0 answers

Find kth smallest element in a binary search tree in most Optimum way.

asked Aug 16 in Algorithms by iarnav (159 points) | 10 views

0 votes

0 answers

Online source
Consider the below algorithm.Where value is an array with n Boolean elements.Find the complexity? boolean find(boolean[]value){ for(int i=0;i<n;i++) { if(value[i]){ for(int j=i+1;j<n;j++) if(value[j]) return true; } } return false; }

asked Aug 12 in Algorithms by aseret (106 points) | 8 views

+1 vote

0 answers

0-1 Knapsack Problem
The recursive equation of the $0-1$ Knapsack Problem is $V[i,w] = max(v_{i}+V[i-1,w-w_{i}],V[i-1,w])\ for\ 1\leqslant i\leqslant n,\ 0\leqslant w\leqslant W$ Could anyone give me an example of weights, profits and Knapsack size where $(V[i-1,w]) \geqslant (v_{i}+V[i-1,w-w_{i}])$? Source: http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf

asked Aug 12 in Algorithms by Shiva Sagar Rao (178 points) | 7 views

0 votes

1 answer

MST of that graph always contains edges with first minimum and second minimum weight. State true/false.

answered Aug 10 in Algorithms by Rudr Pawan (419 points) | 18 views

0 votes

1 answer

from online source
A is an array with n elements.What is the worst case time complexity of algorithm change? change(A) { int i=0,j=0; while((i<n)and(A[i]>A[i+1])) { i=i+1; j=i; while((j<n)&&(A[j+1]>A[j])) j++; }

answered Aug 8 in Algorithms by Satbir (1k points) | 19 views

0 votes

1 answer

Minimum cost spanning trees
How many no of spanning trees are possible if the graph is not complete graph?

answered Aug 7 in Algorithms by user2525 (1.6k points) | 15 views

0 votes

2 answers

GATEBOOK TESTSERIES
Consider the below statements S1: Selection sort runs faster than Insertion sort for an array with all keys identical. S2: Selection sort runs faster than Insertion sort for an array in reverse order. Which of the following statements is true? (A) Only S1 (B) Only S2 (C) Both S1 and S2 (D) Neither S1 or S2

answered Aug 7 in Algorithms by goxul (203 points) | 18 views

0 votes

1 answer

Made easssy test series
The number of distinct BFS and DFS traversal possible on complete graph of n vertices is?

answered Aug 7 in Algorithms by Debargha Bhattacharj (1.3k points) | 13 views

0 votes

1 answer

#ISI 2019 Interview Question
Given an array of n integers, for all indices i except t ,A[i]=i and A[t]=t+1. Find the t by writing the pseudo code or Algorithm? (I told them that it will form the sequence of integers in ascending order and I will apply Binary Search, then I Unable to ... if I write it in the blog will i get ban or not i don't // know about that @Arjun Sir please reply for that ]*/

answered Aug 6 in Algorithms by Satbir (1k points) | 24 views

0 votes

1 answer

this is from GATEBOOK test series
Suppose that we run insertion sort on an array with only three distinct values then the running time in the worst case?

answered Aug 6 in Algorithms by Satbir (1k points) | 6 views

0 votes

1 answer

Algorithms matrix insertion
If in a matrix (m*n) having sorted rows and sorted columns then time complexity to insert new element?

answered Aug 5 in Algorithms by Satbir (1k points) | 12 views

0 votes

0 answers

Recurrence Relations
T(n) = $T(\frac{n}{k}) + T(\frac{3n}{4}) + n$ if n>=2 = 1 if n=1 Which of the following is false? T(n) is O($n^{\frac{3}{2}}$) when k=3 T(n) is O(n log n) when k=3 T(n) is O(n log n) when k=4 T(n) is O(n log n) when k=5

asked Aug 5 in Algorithms by Sambhrant Maurya (281 points) | 6 views

0 votes

1 answer

#Algorithms Min Heap Question
In a min heap of n elements, the Kth smallest element can be found in? O(n) O(nlogn) O(logn) O(1).

answered Aug 5 in Algorithms by Satbir (1k points) | 33 views

0 votes

0 answers

Algorithms: Asymptotic Analysis
The decreasing asymptotic order of the functions: F1:$2^{2^{n+1}}$ F2: log*log n F3: log log* n F4: (log n)! F5: $n^{log log n}$ F1,F5,F4,F2,F3 F1,F4,F5,F3,F2 F1,F5,F4,F2,F3 None of these

asked Aug 5 in Algorithms by Sambhrant Maurya (281 points) | 7 views

+1 vote

0 answers

Algorithms: Recurrence Relations
Consider the following recurrence relation for some unknown recursive algorithm. Take some assumption about the termination condition of algorithm. $T(n)=\sqrt{n} T(\sqrt{n}) + \sqrt{n}$ What is the tightest time bound? O(log log n) O(n log log n) O(n) O(n log $log^{2}n$)

asked Aug 5 in Algorithms by Sambhrant Maurya (281 points) | 8 views

0 votes

1 answer

Algorithm ME practice book
The average no. of comparisons performed by the merge sort algo. , in merging two sorted list of length 2 is . a) 8/3 b) 8/5 c) 11/7 d) 11/6

answered Aug 5 in Algorithms by Hirak (1.3k points) | 16 views

0 votes

1 answer

Recurrence Relation
Solve it using substitution method pls give the solution??

answered Aug 5 in Algorithms by Brij gopal Dixit (130 points) | 17 views

+1 vote

1 answer

Asymptotic Analysis
Consider the following functions: $f(n)=\Omega(n^{3}) $ $g(n)=O(n^{2})$ $h(n)=\Theta (n^{2})$ Which one of the following is the correct asymptotic representation of f(n) + g(n) * h(n) ? $\Omega (n^{3})$ O($n^{4}$) $\Theta (n^{3})$ $\Omega (n^{4})$

answered Aug 4 in Algorithms by Hirak (1.3k points) | 21 views

0 votes

0 answers

merge sort (self doubts)
the key comparisons that are needed in the worst case using efficient algorithm ?

asked Aug 4 in Algorithms by altamash (139 points) | 5 views

0 votes

1 answer

Self Doubt in Algorithms
State true or false, with explanation for a graph G and a constant c>0: Adding c to every edge of G can change the graph's Minimal Spanning Tree. Subtracting c from every edge of G can change the graph's Minimal Spanning Tree. ... can change the shortest path between two vertices. Multiplying c to every edge of G can change the shortest path between two vertices.

answered Aug 4 in Algorithms by Hirak (1.3k points) | 20 views

0 votes

2 answers

Gateforum test series: Algorithms
What is the time complexity for finding maximum profit in Greedy fractional knapsack algorithm if number of items are N= $2^{n}$ ? O(n log n) O($n^{2}$log n) O($2^{n}$) O(n.$2^{n}$)

answered Aug 4 in Algorithms by Hirak (1.3k points) | 22 views

0 votes

0 answers

CLRS: Kruskal's algo
Suppose that the edge weights are uniformly distributed in the half open interval [0.1), which algorithm, Kruskal or Prims can we make run faster and why?

asked Aug 3 in Algorithms by Sambhrant Maurya (281 points) | 4 views

0 votes

1 answer

Algorithm Made Easy Book
Suppose we want to arrange the n numbers stored in an array such that all negative value occur before the positive ones,maximum number of exchanges required by using best algo is? n-1 n^2 n n(n+1)/2

answered Jul 31 in Algorithms by goxul (203 points) | 10 views

0 votes

1 answer

Narsimha Karunamachi
What will be the time complexity and how?

answered Jul 31 in Algorithms by Arnabh Gangwar (183 points) | 12 views

0 votes

0 answers

Peter linz algorithm
State true or false x=theta (n^4), y=theta (n^2) therefore x/y=theta (n^2)

asked Jul 30 in Algorithms by Anuj kumar yadav (108 points) | 10 views

0 votes

0 answers

Algorithm Hashing
Using open addressing with linear probing, we sequentially insert three distinct keys k1, k2 and k3 into a hash table of size m. Assuming simple uniform hashing, what is the probability that we will need three probes, when inserting the third key, k3? a.3/m^2 b. 3/m c.2/m d.2/m^2 anyone please explain above problem in detail….

asked Jul 30 in Algorithms by Manasa.M (119 points) | 4 views

+1 vote

0 answers

How to solve this recurrence relation?
T(n)=T(k)+T(n−k−1)+θ(n) Can someone explain how to solve this?

asked Jul 30 in Algorithms by iarnav (159 points) | 10 views

0 votes

1 answer

#madeeasy_testseries

answered Jul 30 in Algorithms by Rudr Pawan (419 points) | 14 views

0 votes

0 answers

Coreman chpt22. Exercise22.1 question1.
After solving I am getting complexity of O(out degree) = O(edges) {using adjacency list } but in answer they have mentioned O(vertices + edges), so please explain why O(vertices ) is also taken in complexity.

asked Jul 30 in Algorithms by aksh (103 points) | 10 views

0 votes

1 answer

Asymptotic Notation
$\sum_{j=0}^{n} j^{2}=A$ and following choice for $A$ $\theta (n^{4})$ $\theta (n^{3})$ $\Omega (n^{2})$, $O(n^{4})$

answered Jul 29 in Algorithms by goxul (203 points) | 12 views

–1 vote

1 answer

Cormen exercises
Is $2^{n+1}$=$O(2^{n})?$ Is $2^{2n}$=$O(2^{^{n}})$?

answered Jul 28 in Algorithms by Hirak (1.3k points) | 10 views