[algogeeks] Re: Smallest window of K[] in N[]. Best order solution
Let I,Q be input array,query array respectively. 1. Sort query array. O(klogk) 2. Allocate an array A of size N. 3. Fill A such that A[i]= position of Q[i] in I, -1 if not present in I. O(nlogk) 4. Allocate an array B of size k with all elements initiated to -1. 5. for(counter=0,i=0,counter wrote: > @prodigy: how is it coming O(nlogk) can u explain??? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: remove redundantt parenthesis
For every pair of braces, Evaluate the expression within the outer braces of current braces under consideration (1)With current braces (2)Without current braces If both are the same, then you can drop the current braces that its redundant. P.S for outer most braces, evaluate the entire expression with and without it Ex: (a+[b+c]) Here to check if square braces are redundant (1)Evaluate (a+[b+c]) and (a+b+c) (2)If both are equal then drop the braces so expression can be reduced as (a+b+c) (3)Else the braces are required so they remain as (a+[b+c]) Cheers 'Coding is an art and I'm one of the finest of them' -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: remove redundantt parenthesis
For every pair of braces, Evaluate the expression within the outer braces of current braces under consideration (1)With current braces (2)Without current braces If both are the same, then you can drop the current braces that its redundant. P.S for outer most braces, evaluate the entire expression with and without it Ex: (a+[b+c]) Here to check if square braces are redundant (1)Evaluate (a+[b+c]) and (a+b+c) (2)If both are equal then drop the braces so expression can be reduced as (a+b+c) (3)Else the braces are required so they remain as (a+[b+c]) Cheers 'Coding is an art and I'm one of the finest of them' -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sorted array
dont multiply by 5! and 3! because sub-arrays have to remain sorted too so there will be only ONE possible arrangement of 5 elements and 3 elements in sub-array. On Wed, Oct 13, 2010 at 9:27 AM, sudheer babu wrote: > 8C5*(5!*3!)=8! > > > On Tue, Oct 12, 2010 at 9:31 PM, ANUJ KUMAR wrote: > >> 56 >> >> On Tue, Oct 12, 2010 at 5:09 PM, divya wrote: >> > Given a sorted array A with 8 integers.We want to have 2 sorted arrays >> > B(with 5 integers) >> > And C(with 3 integers) such that merging B and C would result in A. >> > How many such pairs exists >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups "Algorithm Geeks" group. >> > To post to this group, send email to algoge...@googlegroups.com. >> > To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> > For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > >> > >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sorted array
8C5*(5!*3!)=8! On Tue, Oct 12, 2010 at 9:31 PM, ANUJ KUMAR wrote: > 56 > > On Tue, Oct 12, 2010 at 5:09 PM, divya wrote: > > Given a sorted array A with 8 integers.We want to have 2 sorted arrays > > B(with 5 integers) > > And C(with 3 integers) such that merging B and C would result in A. > > How many such pairs exists > > > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Least fare for a return trip Algorithm
Could you please elaborate on O(n+m) algorithm that you have used On Oct 12, 6:43 pm, ligerdave wrote: > sorting is absolutely required. w/o the sorting, how are you going to > find the min? comparison is also a sorting algorithm. > it also depends on how many suggestions you wanna have. if it's just > the best deal, you can complete this in O(n+m) where n is the number > of different fares of trip to and m is the trip back > > On Oct 12, 9:06 am, Amod wrote: > > > > > > > > > Suppose there are 100 flights from A to B and 1000 flights from B to > > A. > > Now a user selects the round trip from A to B and back to A, the site > > presents suggestions based on the least fare of the return journey. > > Could someone please help me to device and algorithm where based on > > number of suggestions the results are displayed. > > ex > > A->B B->A > > A1 1 B1 1 > > A2 2 B2 3 > > A3 4 B3 5 > > A4 6 B4 8 > > > So if i want four suggestions then A1+B1, A2+B1, A1+B2, A2+B2 > > > Please also suggest whether sorting based on fares is required or not -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Bee Maja spoj
i am getting wa for http://www.spoj.pl/problems/BMJ/
My logic is that i have seen that the numbers in Willi's Coordinate
System vertically downwards from 1 are following a pattern and i
have stored that pattern in array ar and the index of the array for
each value of Willi's Coordinate System is the y co-ordinate of Maja's
Coordinate System and as we proceed in the clockwise fashion in Maja's
Coordinate System from any value of the index of array ar say for example
0 2 we observe that 1st x decreases and then y decreases and then
(x increases and y decreases simultaneously) and the y increases and the
last one i have seen that is always 1 y(1 2) in this case.
i have attached my code.
please help!
#include
#include
#include
using namespace std;
int main()
{
int ar[183] = {1,2, 9, 22, 41, 66, 97, 134, 177, 226, 281,
342, 409, 482, 561, 646, 737, 834, 937, 1046, 1161, 1282, 1409,
1542,1681, 1826, 1977, 2134, 2297, 2466, 2641, 2822, 3009, 3202, 3401,
3606, 3817, 4034, 4257, 4486, 4721, 4962, 5209, 5462, 5721, 5986,
6257, 6534, 6817, 7106, 7401, 7702, 8009, 8322, 8641, 8966, 9297,
9634, 9977, 10326, 10681, 11042, 11409, 11782, 12161, 12546, 12937,
13334, 13737, 14146, 14561, 14982, 15409, 15842, 16281, 16726, 17177,
17634, 18097, 18566, 19041, 19522, 20009, 20502, 21001, 21506, 22017,
22534, 23057,23586, 24121, 24662, 25209, 25762, 26321, 26886, 27457,
28034, 28617, 29206, 29801, 30402, 31009, 31622, 32241, 32866, 33497,
34134, 34777, 35426, 36081, 36742, 37409, 38082, 38761, 39446, 40137,
40834, 41537, 42246, 42961, 43682, 44409, 45142, 45881,46626, 47377,
48134, 48897, 49666, 50441, 51222, 52009, 52802, 53601, 54406, 55217,
56034, 56857, 57686, 58521, 59362, 60209,61062, 61921, 62786, 63657,
64534, 65417, 66306, 67201, 68102,69009, 69922, 70841, 71766, 72697,
73634, 74577, 75526, 76481, 77442, 78409, 79382, 80361, 81346, 82337,
83334, 84337, 85346,86361, 87382, 88409, 89442, 90481, 91526, 92577,
93634, 94697, 95766, 96841, 97922, 99009};
int n;
while(cin>>n)
{
int st=0,end=182,mid=(st+end)/2;
int ans=ar[mid];
while(st<=end)
{
ans=ar[mid];
mid=(st+end)/2;
if(n>ar[mid])
st=mid+1;
else if(n-yy)
{
x--;
ini++;
}
if(ini==n)
{cout<0)
{
y--;
ini++;
}
if(ini==n)
{cout<-yy)
y--;
ini++;
}
if(ini==n)
{cout
[algogeeks] MAX size of an array
what is the maximum size an array can have in spoj in c++? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sorted array
56 On Tue, Oct 12, 2010 at 5:09 PM, divya wrote: > Given a sorted array A with 8 integers.We want to have 2 sorted arrays > B(with 5 integers) > And C(with 3 integers) such that merging B and C would result in A. > How many such pairs exists > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: missing 2 nums in an array
On Tue, Oct 12, 2010 at 9:04 PM, vijay k wrote: > @Nikhil, > > But your solution changes original array, which is not an acceptable > method. > Ya I know.But he didnt explicitly mention that.If we can't change the original array then this is not an acceptable algorithm. > > On Tue, Oct 12, 2010 at 6:18 PM, Nikhil Agarwal > wrote: > >> @Asquare : Please check the following example: >> >> Given: an array of numbers ranging from 1-n >> A[]= 3,3,5,2,1,2 >> >> As we encounter a number make the index of that number negative if it is >> positive. >> >> A[]= -3,-2,-5,2,-1,2 >> >> Since our index 4 and 6 are positive after the complete pass we conclude >> they are missing ones. >> >> Advantages: No extra space requirement & time is O(n). >> >> >> On Tue, Oct 12, 2010 at 11:49 AM, Dave wrote: >> >>> @Asquare: The two numbers that are not present at least once must be >>> missing. Suppose that a and b are missing and c and d occur twice >>> (with the possibility that c = d so that one number occurs three >>> times). We are going to need four equations in the four unknowns a, b, >>> c, and d. Here are four possible equations: >>> >>> 1. The sum of the numbers = n(n+1)/2 - a - b + c + d, >>> 2. The sum of the squares of the numbers = n(n+1)(2n+1)/6 - a^2 - b^2 >>> + c^2 + d^2, >>> 3. The sum of the cubes of the numbers = n^2(n+1)^2/4 - a^3 - b^3 + >>> c^3 + d^3, and >>> 4. The sum of the fourth powers of the numbers = n(n+1)(2n+1) >>> (3n^2+3n-1)30 - a^3 - b^3 + c^3 + d^3. >>> >>> This system of equations probably will take some fancy algebra to >>> solve for a, b, c, and d. >>> >>> If it is permitted to rearrange the array, another way to do this is >>> as follows using 1-based arrays (warning: untested pseudocode) >>> >>> for i = 1 to n >>>j = i >>>while a(j) not_equal j >>>k = a(a(j)) >>>a(j) = j >>>j = k >>>end_while >>> end_for >>> for i = 1 to n >>>if a(i) not_equal i >>>print i " is missing" >>>end_if >>> end_for >>> >>> This puts each number in its own spot in the array. Obviously missing >>> numbers can't be in their own spots. Because each number is moved only >>> once, the algorithm is O(n). >>> >>> @Bharath. Of course, n! will overflow quite quickly, and two equations >>> isn't enough to determine the two missing numbers, since there are two >>> more unknowns. >>> >>> Dave >>> >>> On Oct 11, 8:11 pm, bharath kannan wrote: >>> > sum of n elements from 1=n(n+1)/2 >>> > product from 1 to n=n! >>> > calculate dis.. >>> > sum=calculated sum-orig sum >>> > prod=calculated prod-orig prod >>> > with dis form quadratic eq and solve... >>> > hope this works... >>> > >>> > >>> > >>> > On Tue, Oct 12, 2010 at 12:29 AM, Asquare >>> wrote: >>> > > Given an array of size n. It contains numbers in the range 1 to n. >>> > > Each number is present at least once except for 2 numbers. >>> > > Find the missing numbers. >>> > >>> > > I know of a solution using another array to store frequency of each >>> > > number.. >>> > > But this holds for than 2 nums also.. >>> > > So Is there any other solution apart from this specific for 2 nums >>> and >>> > > of lesser complexity..?? >>> > >>> > > -- >>> > > You received this message because you are subscribed to the Google >>> Groups >>> > > "Algorithm Geeks" group. >>> > > To post to this group, send email to algoge...@googlegroups.com. >>> > > To unsubscribe from this group, send email to >>> > > algogeeks+unsubscr...@googlegroups.com >>> >>> > > . >>> > > For more options, visit this group at >>> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - >>> > >>> > - Show quoted text - >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> Thanks & Regards >> Nikhil Agarwal >> Senior Undergraduate >> Computer Science & Engineering, >> National Institute Of Technology, Durgapur,India >> http://tech-nikk.blogspot.com >> http://beta.freshersworld.com/communities/nitd >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.goo
Re: [algogeeks] regarding output
On Wed, Oct 13, 2010 at 2:06 AM, newcomer wrote:
>
> #include
> int main()
> {
> int a=3,b=8;
> void *p=(void *)a;
> void *z=(void *)&p[b];
> printf("%u\n",(int)z);
> return(0);
> }
> how the output is coming 11? I am not geting.
> explain void *p=(void)*a;wht does it imply?
> correct
>
explain void *p=(void *)a; wht does it imply?
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] regarding output
#include
int main()
{
int a=3,b=8;
void *p=(void *)a;
void *z=(void *)&p[b];
printf("%u\n",(int)z);
return(0);
}
how the output is coming 11? I am not geting.
explain void *p=(void)*a;wht does it imply?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: missing 2 nums in an array
@Asquare: You've got it! Each for loop runs n times, and within the first for loop, the sum of the number of times the while loop runs is at most n, because it only loops for numbers that are in the wrong spot and every iteration puts another number in the right spot, so after at most n iterations, every number is in the right spot (except the duplicates). E.g., on the input 2,3,4,5,1,2,3, the while loop iterates 5 times while i = 1 to produce the array 1,2,3,4,5,2,3, and then does not iterate at all for the remaining 6 values of i. Thus, the algorithm is O(n). Dave On Oct 12, 1:43 pm, Asquare wrote: > @Dave - > I have a doubt.. > will we not incorporate the complexity we get for each while loop > within the for loop..?? > Basically complexity 2n right..?? > another n because while loop runs for each misplaced number.. right?? > which we take as O(n).. Have I understood it the right way?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] first unrepeated char
take two integer arrays A and B of size 26 ,A is for storing count and
B is for index .Initialize both the array with 0's. Then iterate
through the string once and keep incrementing the respective character
count in A and store the character index in B. Now in array B find
the minimum index whose count in A is 1.
Time Complexity : O(n)
code:
#include
#include
int main()
{
int i=0, min=100;
char c;
char a[26],b[26];
char s[100];
scanf("%s",s);
for( i=0;i<26;i++)
{
a[i]=0;
b[i]=0;
}
for( i=0;i wrote:
> Given a string,find the first un-repeated character in it?
> Im getting O(n2) or O(mn)
> Anyone with a solution of lower complexity..??
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: plz explain output
So its like the printf function cannot convert a int to float and hence prints the last float value which was given to printf. Correct if i have understood it wrong. On Mon, Oct 11, 2010 at 10:25 PM, Asquare wrote: > This modified code also works in exactly the same way.. > The explanation I had given earlier is correct.. > and holds for this code as well > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] first unrepeated char
Given a string,find the first un-repeated character in it? Im getting O(n2) or O(mn) Anyone with a solution of lower complexity..?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: missing 2 nums in an array
@Asquare If you have additional array, why'd you take so much pain. Just put each number in corresponding bucket (read same index in the new array). The empty buckets are the missing numbers. Thanks, - Ravindra On Wed, Oct 13, 2010 at 12:03 AM, Asquare wrote: > Thanks everyone for putting in ur efforts.. > > @lingerdave - > the array is not sorted.. > > @ Dave - > > although the equations will ultimately solve the problem > but I guess it will get tedious and may also go out of bounds > in case of the 4th power equation.. > > As for the other method of placing the number at its index using a > temp variable, > that'll be great.. without requirement of extra space.. > > @Nikhil - > > Thanks for that method.. it saves space but as vijay pointed out it > would alter the array.. > I dnt know to wht extent that would be permitted but not a bad > thought.. > Its a good application of the same logic we use wen we tk an > additional array.. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: missing 2 nums in an array
@Dave - I have a doubt.. will we not incorporate the complexity we get for each while loop within the for loop..?? Basically complexity 2n right..?? another n because while loop runs for each misplaced number.. right?? which we take as O(n).. Have I understood it the right way?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: missing 2 nums in an array
Thanks everyone for putting in ur efforts.. @lingerdave - the array is not sorted.. @ Dave - although the equations will ultimately solve the problem but I guess it will get tedious and may also go out of bounds in case of the 4th power equation.. As for the other method of placing the number at its index using a temp variable, that'll be great.. without requirement of extra space.. @Nikhil - Thanks for that method.. it saves space but as vijay pointed out it would alter the array.. I dnt know to wht extent that would be permitted but not a bad thought.. Its a good application of the same logic we use wen we tk an additional array.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: wiki issue on dijkstra's algorithm
well the animation could have marked the last node with red, they probably got lazy and skipped the last step. Both the algorithm part, and the pseudocode does seem ok to me. However, both of them are too cluttered. I have to say that the pseudocode in CLRS introduction to algorithms MIT press is excellent, both concise and easy to understand. On Oct 12, 4:37 pm, ligerdave wrote: > @Ercan exactly. so do you also find the wiki somewhat misleading? > especially the animation? looks to me when it finds the min, it stops > and reset the start node to be the min and start over again. > > or, > > if you have more vertices between nodes in my example above, you are > able to find the shortest path by following wiki steps. > > On Oct 12, 2:05 am, Gönenç Ercan wrote: > > > > > Dijkstra's algorithm is a dynamic programming algorithm. no matter > > which path is first discovered, the relax operation (if the new path > > is shorter update the path to the node, step 3) will find the correct > > answer in the end. The smallest distance criteria, which selects the > > next current node (step 5) ensures that an already visited node can > > not be relaxed (no shorter path to there). One big mistake is, > > terminating the algorithm when the destination node is reached. The > > first path discovered is not necessarily the correct solution. Your > > problem in particular is that, you are choosing the smallest distance > > node only from the path you are discovering. So lets trace this > > algorithm. > > > Assume that vertices are letters from bottom to up, left to right; A, > > B, C, D, E, F > > > A -> B,C (discovered costs 7, 4) A is marked as visited > > C -> E (discovered cost is 13) C is marked as visited > > Remember that we choose the smallest distance to initial node. one of > > the nodes B or E (costs: 7 or 13) > > B -> D (discovered, cost 9) B is marked as visited > > D-> F (discovered, cost 10) D is marked as visited > > We should nt stop here, we still have unvisited node E. In > > this example E does not relax the path to F, but it should be checked > > in general or the solution may not be minimal. > > E -> F (already discovered, its current cost is 10, since 14 is not > > smaller, no relax operation) > > > All nodes are visited, we are done. Output the path A -> B -> D -> F > > > On Oct 6, 5:47 pm, ligerdave wrote: > > > > so i was reading http://en.wikipedia.org/wiki/ > > > Dijkstra's_algorithm">wiki on dijkstra's algorithm for finding > > > shortest path. i dont think article specifically define the > > > requirements of the graph in order to make the algorithm working > > > properly.(unless i missed something?) > > > > for instance, in the graph below, the shortest path from 1to1 should > > > be 1>7>2>1. however, by following dijkstra's, you would get 1>4>9>1 > > > because compared to 7, 4 is smallest among all direct vertices. > > > > 1 > > > / \ > > > 2 9 > > > | | > > > 7 4 > > > \ / > > > 1 > > > > anyone knows the requirements, especially the ration of #of edges to > > > #of vertices? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] sorted array
8C5 (8!/(3! * 5!)) On Tue, Oct 12, 2010 at 5:09 PM, divya wrote: > Given a sorted array A with 8 integers.We want to have 2 sorted arrays > B(with 5 integers) > And C(with 3 integers) such that merging B and C would result in A. > How many such pairs exists > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: missing 2 nums in an array
@Nikhil, But your solution changes original array, which is not an acceptable method. On Tue, Oct 12, 2010 at 6:18 PM, Nikhil Agarwal wrote: > @Asquare : Please check the following example: > > Given: an array of numbers ranging from 1-n > A[]= 3,3,5,2,1,2 > > As we encounter a number make the index of that number negative if it is > positive. > > A[]= -3,-2,-5,2,-1,2 > > Since our index 4 and 6 are positive after the complete pass we conclude > they are missing ones. > > Advantages: No extra space requirement & time is O(n). > > > On Tue, Oct 12, 2010 at 11:49 AM, Dave wrote: > >> @Asquare: The two numbers that are not present at least once must be >> missing. Suppose that a and b are missing and c and d occur twice >> (with the possibility that c = d so that one number occurs three >> times). We are going to need four equations in the four unknowns a, b, >> c, and d. Here are four possible equations: >> >> 1. The sum of the numbers = n(n+1)/2 - a - b + c + d, >> 2. The sum of the squares of the numbers = n(n+1)(2n+1)/6 - a^2 - b^2 >> + c^2 + d^2, >> 3. The sum of the cubes of the numbers = n^2(n+1)^2/4 - a^3 - b^3 + >> c^3 + d^3, and >> 4. The sum of the fourth powers of the numbers = n(n+1)(2n+1) >> (3n^2+3n-1)30 - a^3 - b^3 + c^3 + d^3. >> >> This system of equations probably will take some fancy algebra to >> solve for a, b, c, and d. >> >> If it is permitted to rearrange the array, another way to do this is >> as follows using 1-based arrays (warning: untested pseudocode) >> >> for i = 1 to n >>j = i >>while a(j) not_equal j >>k = a(a(j)) >>a(j) = j >>j = k >>end_while >> end_for >> for i = 1 to n >>if a(i) not_equal i >>print i " is missing" >>end_if >> end_for >> >> This puts each number in its own spot in the array. Obviously missing >> numbers can't be in their own spots. Because each number is moved only >> once, the algorithm is O(n). >> >> @Bharath. Of course, n! will overflow quite quickly, and two equations >> isn't enough to determine the two missing numbers, since there are two >> more unknowns. >> >> Dave >> >> On Oct 11, 8:11 pm, bharath kannan wrote: >> > sum of n elements from 1=n(n+1)/2 >> > product from 1 to n=n! >> > calculate dis.. >> > sum=calculated sum-orig sum >> > prod=calculated prod-orig prod >> > with dis form quadratic eq and solve... >> > hope this works... >> > >> > >> > >> > On Tue, Oct 12, 2010 at 12:29 AM, Asquare >> wrote: >> > > Given an array of size n. It contains numbers in the range 1 to n. >> > > Each number is present at least once except for 2 numbers. >> > > Find the missing numbers. >> > >> > > I know of a solution using another array to store frequency of each >> > > number.. >> > > But this holds for than 2 nums also.. >> > > So Is there any other solution apart from this specific for 2 nums and >> > > of lesser complexity..?? >> > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups >> > > "Algorithm Geeks" group. >> > > To post to this group, send email to algoge...@googlegroups.com. >> > > To unsubscribe from this group, send email to >> > > algogeeks+unsubscr...@googlegroups.com >> >> > > . >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - >> > >> > - Show quoted text - >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Thanks & Regards > Nikhil Agarwal > Senior Undergraduate > Computer Science & Engineering, > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: missing 2 nums in an array
@Asquare : Please check the following example: Given: an array of numbers ranging from 1-n A[]= 3,3,5,2,1,2 As we encounter a number make the index of that number negative if it is positive. A[]= -3,-2,-5,2,-1,2 Since our index 4 and 6 are positive after the complete pass we conclude they are missing ones. Advantages: No extra space requirement & time is O(n). On Tue, Oct 12, 2010 at 11:49 AM, Dave wrote: > @Asquare: The two numbers that are not present at least once must be > missing. Suppose that a and b are missing and c and d occur twice > (with the possibility that c = d so that one number occurs three > times). We are going to need four equations in the four unknowns a, b, > c, and d. Here are four possible equations: > > 1. The sum of the numbers = n(n+1)/2 - a - b + c + d, > 2. The sum of the squares of the numbers = n(n+1)(2n+1)/6 - a^2 - b^2 > + c^2 + d^2, > 3. The sum of the cubes of the numbers = n^2(n+1)^2/4 - a^3 - b^3 + > c^3 + d^3, and > 4. The sum of the fourth powers of the numbers = n(n+1)(2n+1) > (3n^2+3n-1)30 - a^3 - b^3 + c^3 + d^3. > > This system of equations probably will take some fancy algebra to > solve for a, b, c, and d. > > If it is permitted to rearrange the array, another way to do this is > as follows using 1-based arrays (warning: untested pseudocode) > > for i = 1 to n >j = i >while a(j) not_equal j >k = a(a(j)) >a(j) = j >j = k >end_while > end_for > for i = 1 to n >if a(i) not_equal i >print i " is missing" >end_if > end_for > > This puts each number in its own spot in the array. Obviously missing > numbers can't be in their own spots. Because each number is moved only > once, the algorithm is O(n). > > @Bharath. Of course, n! will overflow quite quickly, and two equations > isn't enough to determine the two missing numbers, since there are two > more unknowns. > > Dave > > On Oct 11, 8:11 pm, bharath kannan wrote: > > sum of n elements from 1=n(n+1)/2 > > product from 1 to n=n! > > calculate dis.. > > sum=calculated sum-orig sum > > prod=calculated prod-orig prod > > with dis form quadratic eq and solve... > > hope this works... > > > > > > > > On Tue, Oct 12, 2010 at 12:29 AM, Asquare > wrote: > > > Given an array of size n. It contains numbers in the range 1 to n. > > > Each number is present at least once except for 2 numbers. > > > Find the missing numbers. > > > > > I know of a solution using another array to store frequency of each > > > number.. > > > But this holds for than 2 nums also.. > > > So Is there any other solution apart from this specific for 2 nums and > > > of lesser complexity..?? > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com > > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > > > - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Thanks & Regards Nikhil Agarwal Senior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] GENETIC ALGORITHM TOOLBOX IN MATLAB
If anyone has used the *genetic algorithm toolbox of matlab* then please reply as soon as possible as we urgently need help with that. -- regards Apoorve Mohan (apoorvemo...@gmail.com) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] sorted array
Given a sorted array A with 8 integers.We want to have 2 sorted arrays B(with 5 integers) And C(with 3 integers) such that merging B and C would result in A. How many such pairs exists -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: missing 2 nums in an array
Replying to myself, I think the pseudocode algorithm I posted earlier is wrong. Here is the correction: for i = 1 to n j = a(i) while a(j) not_equal j k = a(j) a(j) = j j = k end_while end_for for i = 1 to n if a(i) not_equal i print i " is missing" end_if end_for As before, the algorithm is O(n) in time and O(1) in space. Also note that the algorithm will detect any number of missing numbers in the range 1 to n in an array of size n, not just two missing numbers. Dave On Oct 12, 1:19 am, Dave wrote: > @Asquare: The two numbers that are not present at least once must be > missing. Suppose that a and b are missing and c and d occur twice > (with the possibility that c = d so that one number occurs three > times). We are going to need four equations in the four unknowns a, b, > c, and d. Here are four possible equations: > > 1. The sum of the numbers = n(n+1)/2 - a - b + c + d, > 2. The sum of the squares of the numbers = n(n+1)(2n+1)/6 - a^2 - b^2 > + c^2 + d^2, > 3. The sum of the cubes of the numbers = n^2(n+1)^2/4 - a^3 - b^3 + > c^3 + d^3, and > 4. The sum of the fourth powers of the numbers = n(n+1)(2n+1) > (3n^2+3n-1)30 - a^3 - b^3 + c^3 + d^3. > > This system of equations probably will take some fancy algebra to > solve for a, b, c, and d. > > If it is permitted to rearrange the array, another way to do this is > as follows using 1-based arrays (warning: untested pseudocode) > > for i = 1 to n > j = i > while a(j) not_equal j > k = a(a(j)) > a(j) = j > j = k > end_while > end_for > for i = 1 to n > if a(i) not_equal i > print i " is missing" > end_if > end_for > > This puts each number in its own spot in the array. Obviously missing > numbers can't be in their own spots. Because each number is moved only > once, the algorithm is O(n). > > @Bharath. Of course, n! will overflow quite quickly, and two equations > isn't enough to determine the two missing numbers, since there are two > more unknowns. > > Dave > > On Oct 11, 8:11 pm, bharath kannan wrote: > > > > > sum of n elements from 1=n(n+1)/2 > > product from 1 to n=n! > > calculate dis.. > > sum=calculated sum-orig sum > > prod=calculated prod-orig prod > > with dis form quadratic eq and solve... > > hope this works... > > > On Tue, Oct 12, 2010 at 12:29 AM, Asquare wrote: > > > Given an array of size n. It contains numbers in the range 1 to n. > > > Each number is present at least once except for 2 numbers. > > > Find the missing numbers. > > > > I know of a solution using another array to store frequency of each > > > number.. > > > But this holds for than 2 nums also.. > > > So Is there any other solution apart from this specific for 2 nums and > > > of lesser complexity..?? > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Least fare for a return trip Algorithm
sorting is absolutely required. w/o the sorting, how are you going to find the min? comparison is also a sorting algorithm. it also depends on how many suggestions you wanna have. if it's just the best deal, you can complete this in O(n+m) where n is the number of different fares of trip to and m is the trip back On Oct 12, 9:06 am, Amod wrote: > Suppose there are 100 flights from A to B and 1000 flights from B to > A. > Now a user selects the round trip from A to B and back to A, the site > presents suggestions based on the least fare of the return journey. > Could someone please help me to device and algorithm where based on > number of suggestions the results are displayed. > ex > A->B B->A > A1 1 B1 1 > A2 2 B2 3 > A3 4 B3 5 > A4 6 B4 8 > > So if i want four suggestions then A1+B1, A2+B1, A1+B2, A2+B2 > > Please also suggest whether sorting based on fares is required or not -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: wiki issue on dijkstra's algorithm
@Ercan exactly. so do you also find the wiki somewhat misleading? especially the animation? looks to me when it finds the min, it stops and reset the start node to be the min and start over again. or, if you have more vertices between nodes in my example above, you are able to find the shortest path by following wiki steps. On Oct 12, 2:05 am, Gönenç Ercan wrote: > Dijkstra's algorithm is a dynamic programming algorithm. no matter > which path is first discovered, the relax operation (if the new path > is shorter update the path to the node, step 3) will find the correct > answer in the end. The smallest distance criteria, which selects the > next current node (step 5) ensures that an already visited node can > not be relaxed (no shorter path to there). One big mistake is, > terminating the algorithm when the destination node is reached. The > first path discovered is not necessarily the correct solution. Your > problem in particular is that, you are choosing the smallest distance > node only from the path you are discovering. So lets trace this > algorithm. > > Assume that vertices are letters from bottom to up, left to right; A, > B, C, D, E, F > > A -> B,C (discovered costs 7, 4) A is marked as visited > C -> E (discovered cost is 13) C is marked as visited > Remember that we choose the smallest distance to initial node. one of > the nodes B or E (costs: 7 or 13) > B -> D (discovered, cost 9) B is marked as visited > D-> F (discovered, cost 10) D is marked as visited > We should nt stop here, we still have unvisited node E. In > this example E does not relax the path to F, but it should be checked > in general or the solution may not be minimal. > E -> F (already discovered, its current cost is 10, since 14 is not > smaller, no relax operation) > > All nodes are visited, we are done. Output the path A -> B -> D -> F > > On Oct 6, 5:47 pm, ligerdave wrote: > > > > > so i was reading http://en.wikipedia.org/wiki/ > > Dijkstra's_algorithm">wiki on dijkstra's algorithm for finding > > shortest path. i dont think article specifically define the > > requirements of the graph in order to make the algorithm working > > properly.(unless i missed something?) > > > for instance, in the graph below, the shortest path from 1to1 should > > be 1>7>2>1. however, by following dijkstra's, you would get 1>4>9>1 > > because compared to 7, 4 is smallest among all direct vertices. > > > 1 > > / \ > > 2 9 > > | | > > 7 4 > > \ / > > 1 > > > anyone knows the requirements, especially the ration of #of edges to > > #of vertices? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: wiki issue on dijkstra's algorithm
@krunal that's just different representation On Oct 11, 9:26 am, Krunal Modi wrote: > Each edge will have a cost not the nodes(vertices). > Upload an image of the graph. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: missing 2 nums in an array
i think you need to define whether the array is in a sorted order or not. some solutions work on both, but if you want the optimized solution, more information is needed On Oct 11, 2:59 pm, Asquare wrote: > Given an array of size n. It contains numbers in the range 1 to n. > Each number is present at least once except for 2 numbers. > Find the missing numbers. > > I know of a solution using another array to store frequency of each > number.. > But this holds for than 2 nums also.. > So Is there any other solution apart from this specific for 2 nums and > of lesser complexity..?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Least fare for a return trip Algorithm
Suppose there are 100 flights from A to B and 1000 flights from B to A. Now a user selects the round trip from A to B and back to A, the site presents suggestions based on the least fare of the return journey. Could someone please help me to device and algorithm where based on number of suggestions the results are displayed. ex A->B B->A A1 1B11 A2 2B23 A3 4B35 A4 6B48 So if i want four suggestions then A1+B1, A2+B1, A1+B2, A2+B2 Please also suggest whether sorting based on fares is required or not -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
