Recent questions tagged algorithms

0 votes

1 answer 5 views

#self doubt #algorithm #asymptotic notation
Big O is fn=c.gn for some values of constant 'c>0' and for little o it is fn=c.gn for all values of constant 'c>0', now my question is what is the difference between this some c>0 and all values of c>0 mentioned here

Big O is fn=c.gn for some values of constant 'c>0' and for little o it is fn=c.gn for all values of constant 'c>0', now my question is what is the difference between this some c>0 and all values of c>0 mentioned here

asked 14 hours ago in Algorithms arnab2022 5 points 5 views

0 votes

3 answers 49 views

Algorithms Self Doubt. Topic- Sorting and Max-Heap

Which of the following is/are true? [MSQ] If f(n) = Ο(g(n)) and g(n) = Ο(h(n)), then h(n) = Ω( f(n)) If f(n) = Ο(g(n)) and g(n) = Ο( f(n)) then f(n) = θ(g(n)) The sequence < 20, 15, 18, 7, 9, 5, 12, 3, 6, 2 ... heap. After each insertion, the heap still has the max-heap property, so after n Insert operations, it is a max-heap on the n elements. Then this heap construction runs in Ο(n logn) time.

asked Jul 15 in Algorithms Sudarshan Bandyopadh 17 points 49 views

0 votes

1 answer 24 views

I came across these three questions on internet on Master Theorem

Help me solve these three questions on Master’s Theorem: T(n) = T(n/2) + 2^n T(n) = 2T (n/2) + n/logn T(n) = 16T (n/4) + n!

asked Jul 12 in Algorithms Naman9495 5 points 24 views

0 votes

1 answer 187 views

Different Types of Numerical in GATE 2022
I am making a list of different types of numericals that can possibly come in GATE from different subjects .. This list is not ... =IwAR0ezzTYvJdobF2hXtr3xVNZpZOFtw96yHAywR2_j9BOKGe1mBNSgVUcsvw#9xiori58gq22i 7. https://www.mediafire.com/folder/gp6z7khjzyl8d/gate_materials?fbclid=IwAR0ezzTYvJdobF2hXtr3xVNZpZOFtw96yHAywR2_j9BOKGe1mBNSgVUcsvw#mp3qyi2prh3fb

I am making a list of different types of numericals that can possibly come in GATE from different subjects .. This list is not comprehensive, so please ... ?fbclid=IwAR0ezzTYvJdobF2hXtr3xVNZpZOFtw96yHAywR2_j9BOKGe1mBNSgVUcsvw#9xiori58gq22i 7. https://www.mediafire.com/folder/gp6z7khjzyl8d/gate_materials?fbclid=IwAR0ezzTYvJdobF2hXtr3xVNZpZOFtw96yHAywR2_j9BOKGe1mBNSgVUcsvw#mp3qyi2prh3fb

asked Jul 5 in Others asqwer 633 points 187 views

0 votes

1 answer 22 views

#Made Easy Test Series 2022 #Algorithms-I
Assume a scenario in which min-max heap has the following property: An almost complete binary tree where each node at an even level in the tree is less than all of its descendants and each of the node at an odd level in the tree is greater than all of its ... (d) Ο(n) for max and Ο(log n) for min or Ο(n) for min and Ο(log n) for max respectively

Assume a scenario in which min-max heap has the following property: An almost complete binary tree where each node at an even level in the tree is less than all of its descendants and each of the node at an odd level in the tree is greater than all of its descendants. The worst-case ... log n) respectively (d) Ο(n) for max and Ο(log n) for min or Ο(n) for min and Ο(log n) for max respectively

asked Jun 29 in DS Sibu08 5 points 22 views

0 votes

0 answers 19 views

Time and space complexity
There is an algorithm that took array of strings, sorted each string and then sorted the entire array.What would be the runtime?

There is an algorithm that took array of strings, sorted each string and then sorted the entire array.What would be the runtime?

asked Jun 28 in Algorithms SaileeDas 5 points 19 views

0 votes

0 answers 14 views

Made easy test series #algorithm #graph #DFS
Did not understand answer of this question plz help me to resolve problem.

Did not understand answer of this question plz help me to resolve problem.

asked Jun 26 in Algorithms taatya bichhu 5 points 14 views

0 votes

1 answer 14 views

find meh
// C++ implementation to find the character in first // string that is present at minimum index in second // string #include <bits/stdc++.h> using namespace std; // function to find the minimum index character void printMinIndexChar(string str, string ... in unordered map or not because it only returns true or false but how can we assign the character inside the if condition.

// C++ implementation to find the character in first // string that is present at minimum index in second // string #include <bits/stdc++.h> using namespace std; // function to find the minimum index character void printMinIndexChar(string str, string patt) { // ... is present in unordered map or not because it only returns true or false but how can we assign the character inside the if condition.

asked Jun 23 in Programming Lekhraj 9 points 14 views

0 votes

0 answers 10 views

[SELF DOUBT] DSA BUBBLE SORT
is bubble sort an online algorithm? cause whenever new element is fed, it can be take to its place by swapping the adjacent numbers. is my thinking right?

is bubble sort an online algorithm? cause whenever new element is fed, it can be take to its place by swapping the adjacent numbers. is my thinking right?

asked Jun 18 in Algorithms rythmrana 5 points 10 views

0 votes

0 answers 18 views

[SELF DOUBT] DSA INSERTION SORT
for an almost sorted array, which algorithm is better, shell sort or insertion sort? and also for a fully sorted array?

for an almost sorted array, which algorithm is better, shell sort or insertion sort? and also for a fully sorted array?

asked Jun 17 in Algorithms rythmrana 5 points 18 views

0 votes

0 answers 13 views

[SELF DOUBT] DSA , IN PLACE SORTING
if we require a large(more than size of array or 1000000mb) but constant( irrespective of size of input array) extra space for an algorithm, will the algorithm be in place or not? the extra space is not required to manipulate the elements of array but may be required for some other purpose.

if we require a large(more than size of array or 1000000mb) but constant( irrespective of size of input array) extra space for an algorithm, will the algorithm be in place or not? the extra space is not required to manipulate the elements of array but may be required for some other purpose.

asked Jun 17 in Algorithms rythmrana 5 points 13 views

0 votes

0 answers 12 views

Topic name : heapify and heapsort
We can reduce the space complexity of heapsort to o(1) by using heapify using loops, then why we dont reduce the space complexity of heapify from o(logn) to o(1) by using loops here also.?

We can reduce the space complexity of heapsort to o(1) by using heapify using loops, then why we dont reduce the space complexity of heapify from o(logn) to o(1) by using loops here also.?

asked Jun 9 in Algorithms Ayush1718 5 points 12 views

0 votes

1 answer 22 views

self doubt regarding the full binary tree
This is in regards to Binary tree. The question is The image given below is full binary tree or not?

This is in regards to Binary tree. The question is The image given below is full binary tree or not?

asked Jun 5 in Algorithms rish1602 9 points 22 views

0 votes

0 answers 18 views

I have been practicing question using Master Theorem, I find one is hard so posted here for expert review

Hi Experts, I have been practicing Master Theorem since Yesterday as I am recently involved in algorithm course. I have found a hard the following problem whether the Master Theorem is applicable or it violates rules. if yes then kindly elaborate for better understanding…. Apology for English grammar T(n) = 2^1.534T( n 2 ) + 2^ 2n

asked Jun 1 in Algorithms Irfan123 5 points 18 views

0 votes

0 answers 24 views

Go Book 2020 volume 2 page number 160 question no. 3.14.6

In avl tree can we take base case for minimum height as n(1)=2 rather than n(0)=1 in the recurrence relation : n(h)=2n(h-1)+1 where h is height of the tree.

asked May 23 in DS prateek_hazard 5 points 24 views

0 votes

0 answers 13 views

Asymptotic notation
T(n)=T(n-1)-1 what is complexity of this

T(n)=T(n-1)-1 what is complexity of this

asked May 6 in Algorithms Rahul06 5 points 13 views

0 votes

0 answers 19 views

Reference from GATE IT-2005 (2 marks)
"In Binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2." How is this statement valid in case of Left or Right Skewed Binary tree?

"In Binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2." How is this statement valid in case of Left or Right Skewed Binary tree?

asked May 2 in Programming Anupreet13 5 points 19 views

0 votes

1 answer 53 views

made easy question about time complexity
what is the time complexity in f( int n) { if(n <=2) return 1 else return f(floor(sqrt(n))) + n; }

what is the time complexity in f( int n) { if(n <=2) return 1 else return f(floor(sqrt(n))) + n; }

asked Apr 28 in Algorithms pppankajsaini 9 points 53 views

0 votes

1 answer 25 views

CRLS question 6.5-7
How to Implement a stack with a priority queue ?

How to Implement a stack with a priority queue ?

asked Mar 17 in Algorithms Raj_81 23 points 25 views

0 votes

0 answers 49 views

Made Easy Postal study material objective practice sets- algorithm-asymptotic analysis

Q.9 Determine the asymptotic running time of f(n) for the following C program. Int f(int n) int x; if (n == 0) x = 1: else x = f(n-1) 2; g(x): return x; void g(int m) { int y: for (y = m, y > 0; y/ = 2):}

asked Mar 12 in Algorithms Harshit2021 5 points 49 views

0 votes

0 answers 33 views

Need to change the book content details
Here, Chapter 9 is missing. This makes me loose 2 marks. Because I blindly believed that the content described in this material is accurate. So plz update the latest content in this material.

Here, Chapter 9 is missing. This makes me loose 2 marks. Because I blindly believed that the content described in this material is accurate. So plz update the latest content in this material.

asked Mar 11 in Algorithms Raj_81 23 points 33 views

1 vote

0 answers 50 views

PLEASE HELP WITCH COMPUTER SCIENCE

asked Mar 2 in Others Zipko 9 points 50 views

4 votes

3 answers 1.4K views

GATE CSE 2021 Set 2 | Question: 1 | Video Solution

Let $G$ be a connected undirected weighted graph. Consider the following two statements. $S_1$: There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$. $S_2$: If every edge in $G$ has distinct weight, then $G$ has a unique minimum spanning ... $S_1$ is true and $S_2$ is false $S_1$ is false and $S_2$ is true Both $S_1$ and $S_2$ are false

asked Feb 18 in Algorithms Arjun 1.5k points 1.4K views

0 votes

2 answers 1K views

GATE CSE 2021 Set 2 | Question: 8 | Video Solution

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$

asked Feb 18 in Algorithms Arjun 1.5k points 1K views

3 votes

2 answers 660 views

GATE CSE 2021 Set 2 | Question: 23 | Video Solution

Consider the following $\text{ANSI C}$ function: int SomeFunction (int x, int y) { if ((x==1) || (y==1)) return 1; if (x==y) return x; if (x > y) return SomeFunction(x-y, y); if (y > x) return SomeFunction (x, y-x); } The value returned by $\textrm{SomeFunction(15, 255)}$ is __________

asked Feb 18 in Algorithms Arjun 1.5k points 660 views

2 votes

2 answers 871 views

GATE CSE 2021 Set 2 | Question: 26 | Video Solution

Consider the string $\textrm{abbccddeee}$. Each letter in the string must be assigned a binary code satisfying the following properties: For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. For any two letters ... assignments which satisfy the above two properties, what is the minimum length of the encoded string? $21$ $23$ $25$ $30$

asked Feb 18 in Algorithms Arjun 1.5k points 871 views

4 votes

3 answers 907 views

GATE CSE 2021 Set 2 | Question: 39 | Video Solution

For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers: $T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$ Which one of the following options is correct about the recurrence $T(n)$? If $f(n)$ is $n \log_2(n)$, then $T(n)$ ... $\Theta(n^{\log_b(a)})$ If $f(n)$ is $\Theta(n^{\log_b(a)})$, then $T(n)$ is $\Theta(n^{\log_b(a)})$

asked Feb 18 in Algorithms Arjun 1.5k points 907 views

2 votes

2 answers 819 views

GATE CSE 2021 Set 2 | Question: 46 | Video Solution

Consider the following directed graph: Which of the following is/are correct about the graph? The graph does not have a topological order A depth-first traversal starting at vertex $S$ classifies three directed edges as back edges The graph does not have a strongly connected component For each pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$

asked Feb 18 in Algorithms Arjun 1.5k points 819 views

3 votes

2 answers 698 views

GATE CSE 2021 Set 2 | Question: 49 | Video Solution

Consider the following $\text{ANSI C}$ program #include <stdio.h> int foo(int x, int y, int q) { if ((x<=0) && (y<=0)) return q; if (x<=0) return foo(x, y-q, q); if (y<=0) return foo(x-q, y, q); return foo(x, y-q, q) + foo(x-q, y, q); } int main( ) { int r = foo(15, 15, 10); printf(“%d”, r); return 0; } The output of the program upon execution is _________

asked Feb 18 in Algorithms Arjun 1.5k points 698 views

3 votes

2 answers 872 views

GATE CSE 2021 Set 2 | Question: 55 | Video Solution

In a directed acyclic graph with a source vertex $\textsf{s}$, the $\textit{quality-score}$ of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex $v$ other than $\textsf{s}$, the quality-score of $v$ is ... quality-score of $\textsf{s}$ is assumed to be $1$. The sum of the quality-scores of all vertices on the graph shown above is _______

asked Feb 18 in Algorithms Arjun 1.5k points 872 views

3 votes

2 answers 837 views

GATE CSE 2021 Set 1 | Question: 3 | Video Solution

Consider the following three functions. $f_1=10^n\quad f_2=n^{\log n}\quad f_3=n^{\sqrt {n}}$ Which one of the following options arranges the functions in the increasing order of asymptotic growth rate? $f_3, f_2, f_1$ $f_2, f_1, f_3$ $f_1, f_2,f_3$ $f_2, f_3, f_1$

asked Feb 18 in Algorithms Arjun 1.5k points 837 views

2 votes

3 answers 858 views

GATE CSE 2021 Set 1 | Question: 9 | Video Solution

Consider the following array.$\begin{array}{|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline\end{array}$ Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order? Selection sort Mergesort Insertion sort Quicksort using the last element as pivot

asked Feb 18 in Algorithms Arjun 1.5k points 858 views

0 votes

3 answers 859 views

GATE CSE 2021 Set 1 | Question: 17 | Video Solution

Consider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is ___________.

asked Feb 18 in Algorithms Arjun 1.5k points 859 views

5 votes

5 answers 1.9K views

GATE CSE 2021 Set 1 | Question: 30 | Video Solution

Consider the following recurrence relation. $T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$ Which one of the following options is correct? $T(n)=\Theta (n^{5/2})$ $T(n)=\Theta (n\log n)$ $T(n)=\Theta (n)$ $T(n)=\Theta ((\log n)^{5/2})$

asked Feb 18 in Algorithms Arjun 1.5k points 1.9K views

1 vote

2 answers 1.1K views

GATE CSE 2021 Set 1 | Question: 40 | Video Solution

Define $R_n$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i>0$, let $p[i]$ denote the selling price of a rod whose length is $i$ meters. Consider the array of prices: ... $R_7$? $R_7=18$ $R_7=19$ $R_7$ is achieved by three different solutions $R_7$ cannot be achieved by a solution consisting of three pieces

asked Feb 18 in Algorithms Arjun 1.5k points 1.1K views

2 votes

1 answer 646 views

GATE CSE 2021 Set 1 | Question: 47 | Video Solution

Consider a $\textit{dynamic}$ hashing approach for $4$-bit integer keys: There is a main hash table of size $4$. The $2$ least significant bits of a key is used to index into the main hash table. Initially, the main hash table entries are empty. Thereafter, when more keys are hashed into it, to resolve ... in decimal notation)? $5,9,4,13,10,7$ $9,5,10,6,7,1$ $10,9,6,7,5,13$ $9,5,13,6,10,14$

asked Feb 18 in Algorithms Arjun 1.5k points 646 views

1 vote

3 answers 463 views

GATE CSE 2021 Set 1 | Question: 48 | Video Solution

Consider the following $\text{ANSI C}$ function: int SimpleFunction(int Y[], int n, int x) { int total = Y[0], loopIndex; for (loopIndex=1; loopIndex<=n-1; loopIndex++) total=x*total +Y[loopIndex]; return total; } Let $\textsf{Z}$ be an array of $10$ elements with $\textsf{Z}[i]=1$, for all $i$ such that $0 \leq i \leq 9$. The value returned by $\textsf{SimpleFunction(Z},10,2)$ is __________

asked Feb 18 in Algorithms Arjun 1.5k points 463 views

0 votes

1 answer 49 views

Selection sort
Can anybody explain me why the number of swaps in selection sort algorithm is (n-1) in worst case ? Let's say the array is {6,5,4,3,2,1} then the number of swaps should be 5. But I think the no of swaps should be 3. Please explain.

Can anybody explain me why the number of swaps in selection sort algorithm is (n-1) in worst case ? Let's say the array is {6,5,4,3,2,1} then the number of swaps should be 5. But I think the no of swaps should be 3. Please explain.

asked Feb 7 in Algorithms Akshay0798 7 points 49 views

0 votes

0 answers 14 views

gate overflow book
https://gateoverflow.in/25666/tifr2013-b-5 The above is the link of the question. Just for the point that I have understood the solution correctly, I'm going to explain what I understood. First we are negating the edges, so any positive weight cycle ... again, we will be able to find whether there is a negative weight cycle reachable from the source. Is the explaination correct?

https://gateoverflow.in/25666/tifr2013-b-5 The above is the link of the question. Just for the point that I have understood the solution correctly, I'm going to explain what I understood. First we are negating the edges, so any positive weight cycle which was ... -Ford again, we will be able to find whether there is a negative weight cycle reachable from the source. Is the explaination correct?

asked Feb 6 in Algorithms hadarsh 5 points 14 views

0 votes

0 answers 37 views

gate overflow book
https://gateoverflow.in/4208/gate2000-2-19 The above is the link of the question. In the question it is given that DFS results in a DFS tree T. Does this strictly imply that the graph is connected? Because if not then we can even have a disconnected graph as a counter example

https://gateoverflow.in/4208/gate2000-2-19 The above is the link of the question. In the question it is given that DFS results in a DFS tree T. Does this strictly imply that the graph is connected? Because if not then we can even have a disconnected graph as a counter example

asked Feb 4 in DS hadarsh 5 points 37 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Log In

Register

Recent Posts

No Recent Blog Comments

Recent questions tagged algorithms