Recent questions tagged algorithms / GATE Overflow for GATE CSE

Acc. to dijkstra's algorithm:What will be the shortest path from A to B ?1) When the edge of length 15 is present.2) when the edge of length 15 is removed.

Aspi R Osa

2.0k views

Aspi R Osa asked Jan 11, 2016

1 votes

1 answer

3067

MadeEasy Test Series: Algorithms - Dynamic Programming
Given an array of n numbers, give an algorithm for finding a contiguous subsequence A(i) ...A(j) for which the sum of elements is maximum. Eg. [-2, 11, -4, 13, -5, 2] → 20 If dynamic programming approach is used then what is time complexity and space complexity? (a ... b.) O(n), O(n) (c.) O(n3), O(n) (d.) O(n2), O(1) Given answer is option (b.)

Given an array of n numbers, give an algorithm for finding a contiguous subsequence A(i) ...A(j) for which the sum of elements is maximum.Eg. [-2, 11, -4, 13, -5, 2] → ...

Utk

1.2k views

Utk asked Jan 11, 2016

1 votes

1 answer

3068

What is the time complexity of this problem ?
Given an array S containing n real numbers, and a real number x. We want to find any two elements p and q in the array such that their sum is greater than the real number x. What is the best possible time complexity to find p and q ? ... and second element's sum is greater than x , then it can be done in O(1) time , right ? Please correct me.

Given an array S containing n real numbers, and a real number x. We want to find any two elements p and q in the array such that their sum is greater than the real number...

worst_engineer

418 views

worst_engineer asked Jan 10, 2016

1 votes

1 answer

3069

Order of growth
Arrange the following functions in ascending order according to their order of growths. $\begin{align} f_1 &= 100000 \cdot n\\[1em] f_2 &= \frac1{30} \cdot n^2\\[1em] f_3 &= (\log n)^{200}\\[1em] f_4 &= 2^n\\[1em] f_5 &= n \cdot \log n \end{align}$

Arrange the following functions in ascending order according to their order of growths.$$\begin{align}f_1 &= 100000 \cdot n\\[1em]f_2 &= \frac1{30} \cdot n^2\\[1em]f_3 &=...

prathams

1.7k views

prathams asked Jan 10, 2016

0 votes

1 answer

3070

Median
what is the time complexity to find median of array with n elements??

what is the time complexity to find median of array with n elements??

Pranav Gupta 1

383 views

Pranav Gupta 1 asked Jan 10, 2016

2 votes

0 answers

3071

Algorithm: Array Fill the Blank
Consider a square matrix of N × N in which the values are located from A[1, 1] to A[N, N]. For all i and j, A[i, j] = A[i – 1, j – 1] where i > 1 and j > 1. In order to reduce the space complexity we avoid redundant ... i – 1] B [N + j – i – 1] B [N + i – j – 1] How to solve this ?

Consider a square matrix of N × N in which the values are located from A[1, 1] to A[N, N]. For all i and j, A[i, j] = A[i – 1, j – 1] where i 1 and j ...

Prasanna

786 views

Prasanna asked Jan 9, 2016

1 votes

1 answer

3072

complexity comparison of heap sort,quick sort and merge sort !!
Q:- which one is the best among heap sort ,quick sort and merge sort in terms of complexity ? please answer with explanation!!

Q:- which one is the best among heap sort ,quick sort and merge sort in terms of complexity ? please answer with explanation!!

AJAY KUMAR ARYAN

1.1k views

AJAY KUMAR ARYAN asked Jan 8, 2016

1 votes

2 answers

3073

DFS

Mojo-Jojo

1.2k views

Mojo-Jojo asked Jan 8, 2016

0 votes

0 answers

3074

How to solve below recurrence relation ?
T(n)=2T(n-1)+n-1, T(1)=1 , n>=2 T(n)=2kT(n-k)+2(k-1)(n-(k-1))+2(k-2)(n-(k-2))+.......+n Now k=n-1 T(n)=2(n-1)(1)+2(n-2)(2)+2(n-3)(3)+.......+2(n-n)(n) T(n)=2(n)[ 1/1 + 2/2(2) +3/2 (3) + 2/ 2(4) +....] + n Now I am struck at this point how to proceed from here ?

T(n)=2T(n-1)+n-1, T(1)=1 , n>=2T(n)=2kT(n-k)+2(k-1)(n-(k-1))+2(k-2)(n-(k-2))+.......+nNow k=n-1T(n)=2(n-1)(1)+2(n-2)(2)+2(n-3)(3)+.......+2(n-n)(n)T(n)=2(n)[ 1/1 + 2/2(2)...

radha gogia

386 views

radha gogia asked Jan 7, 2016

1 votes

1 answer

3075

Given the sequence of n integers in the order:

Payal Rastogi

482 views

Payal Rastogi asked Jan 7, 2016

6 votes

2 answers

3076

Asymptotics
Find the False statement. $O(2^n) = O(3^n)$ $O(\log n^2) = O(\log n)$ $f(n) = O \left ( (f(n))^2 \right )$ $2^{2 \log n} (\log n) = O(n^2 \log n)$

Find the False statement.$O(2^n) = O(3^n)$ $O(\log n^2) = O(\log n)$ $f(n) = O \left ( (f(n))^2 \right )$ $2^{2 \log n} (\log n) = O(n^2 \log n)$

Himanshu1

838 views

Himanshu1 asked Jan 6, 2016

3 votes

2 answers

3077

TestBook Test Series Algo Q
Q). What is the complexity of finding the $50^{th}$ smallest elements in an already constructed binary min-heap? $\theta(1)$ $\theta(logn)$ $\theta(n)$ $\theta(nlogn)$ solution: Exact complexity would be $50logn$ for heapify when we do heap sort iteration $50$ times

Q). What is the complexity of finding the $50^{th}$ smallest elements in an already constructed binary min-heap?$\theta(1)$$\theta(logn)$$\theta(n)$$\theta(nlogn)$solutio...

Akash Kanase

794 views

Akash Kanase asked Jan 6, 2016

4 votes

2 answers

3078

How to solve below recurrence relation ?
T(n)=2√nT(√n)+n In this If we take n=2m then and I divide the entire equation by n so I will get T(2m)/2m=2T(2m/2) + 1 Now T(2m)/2m=S(m), so equation becomes S(m)=2S(m/2)+1 therefore S(m)=⊝( ... #8861;(m) , T(2m)=2m⊝(logn)=⊝(nlogn) Is this correct approach or not ,since I am unable to do it with tree method .

T(n)=2√nT(√n)+n In this If we take n=2m then and I divide the entire equation by n so I will get T(2m)/2m=2T(2m/2) + 1Now T(2m)/2m=S(m), so equation becomes S...

radha gogia

2.7k views

radha gogia asked Jan 4, 2016

0 votes

1 answer

3079

What is the difference between double hashing and rehashing?

Nisha kumari

4.7k views

Nisha kumari asked Jan 4, 2016

4 votes

2 answers

3080

Madeeasy
Which of the following is true? $f(n)=O\left(\left(f\left(n\right)\right)^{2}\right)$ $f(n)=O\left(g\left(n\right)\right)\Rightarrow 2^{f\left (n\right)}=O\left(2^{g\left(n\right)}\right)$ $f(n)+O\left(f\left(n\right)\right)=\theta \left(f\left(n\right)\right)$ Both (a) and (b)

Which of the following is true?$f(n)=O\left(\left(f\left(n\right)\right)^{2}\right)$$f(n)=O\left(g\left(n\right)\right)\Rightarrow 2^{f\left (n\right)}=O\left(2^{g\left(n...

saurav04

1.1k views

saurav04 asked Jan 4, 2016

0 votes

1 answer

3081

HOW TO FIND NO OF PASSES IN MERGE SORT
IF ONE USES STRAIGHT MERGE SORT TO THE FOLLOWING ELEMENTS 20,47,15,8,9,4,40,30,12,17 THEN THE ORDER OF THE ELEMENTS AFTER 2ND PASS OF THE ALGORITHM

IF ONE USES STRAIGHT MERGE SORT TO THE FOLLOWING ELEMENTS 20,47,15,8,9,4,40,30,12,17 THEN THE ORDER OF THE ELEMENTS AFTER 2ND PASS OF THE ALGORITHM

Santhosh Devulapally

6.7k views

Santhosh Devulapally asked Jan 3, 2016

1 votes

1 answer

3082

Find time complexity of following code:

Nisha kumari

1.1k views

Nisha kumari asked Jan 2, 2016

0 votes

2 answers

3083

MadeEasy Test Series: Algorithms - Graph Algorithms
Which of the following statements is/are true? S1: Dijkstra’s algorithm is not affected by negative edge weight cycles in the graph and gives correct shortest path. S2: Bellman ford algorithm finds all negative edge weight cycles present in the graph. a) Only S2 b) Only S1 c) Both S1 and S2 d) Neither S1 and nor S2

Which of the following statements is/are true?S1: Dijkstra’s algorithm is not affected by negative edge weight cycles in the graph and gives correct shortest path.S2: B...

Sandeep Singh

1.3k views

Sandeep Singh asked Jan 2, 2016

0 votes

2 answers

3084

How to evaluate below expression involving asymptotic notations?
If f(n)=ϴ(n),g(n)=ϴ(n) and h(n)=Ω(n) Then how to evaluate f(n)g(n)+h(n)? I am getting expression such that it is equivalent to O(n^2 ) , since f(n)g(n)=theta(n^2),Now I am just confused at one point that how to proceed for calculating f(n)g(n)+h(n) ,theta(n^2)+h(n) ?

Iff(n)=ϴ(n),g(n)=ϴ(n)andh(n)=Ω(n)Then how to evaluate f(n)g(n)+h(n)? I am getting expression such that it is equivalent to O(n^2 ) , since f(n)g(n)=theta(n^2),Now I am...

radha gogia

366 views

radha gogia asked Dec 31, 2015

0 votes

1 answer

3085

Prefix code
How to solve this ? I am getting 1111 , the given answer is 1011.

How to solve this ? I am getting 1111 , the given answer is 1011.

Rohit Mallik

325 views

Rohit Mallik asked Dec 30, 2015

19 votes

8 answers

3086

Minimum number of comparisons required to sort 5 elements is
The minimum number of comparisons required to sort 5 elements is - 4 5 6 7

The minimum number of comparisons required to sort 5 elements is -4567

piyushkr

43.6k views

piyushkr asked Dec 30, 2015

1 votes

1 answer

3087

How to solve below recurrence relation using subtitution method ?
T(n)=T(n-3)+cn2 T(n-3)=T(n-6)+c(n-3)2 T(n-6)=T(n-9)+c(n-6)2 Continuing like this I am getting T(n)=T(n-3k)+cn2+c(n-3k)2+c(n-(3k+3))2+c(n-(3k+6))2+c(n-(3k+9))2+...... Now let k=(n-1)/3 ,I am only able to get terms like cn2+c+4c+25c +64c, with which I am unable to reach any conclusion , so how to proceed through this .

T(n)=T(n-3)+cn2T(n-3)=T(n-6)+c(n-3)2T(n-6)=T(n-9)+c(n-6)2Continuing like this I am getting T(n)=T(n-3k)+cn2+c(n-3k)2+c(n-(3k+3))2+c(n-(3k+6))2+c(n-(3k+9))2+......Now let ...

radha gogia

382 views

radha gogia asked Dec 30, 2015

1 votes

1 answer

3088

Recurrence relation explanation
Whenever we have a recurrence relation of type T(n) = a * T(n/b) + c here a is the number of sub problems. what will be Size of sub problems ? Is it n/b ?

Whenever we have a recurrence relation of typeT(n) = a * T(n/b) + chere a is the number of sub problems. what will be Size of sub problems ? Is it n/b ?

Sandeep Singh

322 views

Sandeep Singh asked Dec 30, 2015

0 votes

1 answer

3089

what is the relation between two functions ?
A) nlg c , clg n , B) lg(n!) , lg(nn) I guess both are equivalent so then how to represent them using asymptotic notation ?

A) nlg c , clg n , B) lg(n!) , lg(nn)I guess both are equivalent so then how to represent them using asymptotic notation ?

radha gogia

432 views

radha gogia asked Dec 29, 2015

2 votes

1 answer

3090

Asymptotics
Ans given is D. Is it because, in analyzing this we would ignore the constants involved in the equation?

Ans given is D. Is it because, in analyzing this we would ignore the constants involved in the equation?

UK

419 views

UK asked Dec 29, 2015

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