Re: [algogeeks] Road crossing algorithm

2010-07-15 Thread Ashish kumar Jain
I think this will help:

http://en.wikipedia.org/wiki/Frogger

Consider the roads to be n-laned and of constant width with constant time
traffic coming on each lane.For example,say after 1 minute,a car comes on
each lane but in a arithmetic sequence and not all at same time.To make it
more clear,

at t=1 minute,car at lane 1 travelling with constant velocity v and takes
T time to cross the screen/lane1.

at t=2 minute,another car comes now in lane 2 with same constant velocity
and so on..

Now the frog can cross one lane either back or forth in one jump.These are
the only movements allowed.The jump time is considerable(say in above case 1
minute only).Note that times are all not correctly mentioned and consider
times which are appropriate for the problem.The time details are mentioned
to make everyone understand the problem.

Design an algorithm to guarantee that the frog crosses the road safely.

Think first..Hint is
downwards.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.

Hint: Think in terms of multithreading,semaphores,mutex and vectors
etc..

On Wed, Jul 14, 2010 at 11:33 PM, Tech Id tech.login@gmail.com wrote:

 A frog has to cross a road to meet
 its beloved she-frog at the other end.

 The road however has cars coming and
 can crush the frog.

 Road is two lanes wide.

 Devise an algorithm to help the frog carry on its family.

 (I am sorry but it seems that I have missed
 some parts of the problem here. If someone
 remembers the complete question, please help me).
 Thanks in advance!

 --
 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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Regards,
Ashish

-- 
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: sort in O(n) array which increases and then decreased and then increases...5,10,15,14,9,4,1,3,6,7,11,9,8,2

2010-07-15 Thread jalaj jaiswal
try merging this array
[{5,9,10},{3,6,7,9}]...

On Wed, Jul 14, 2010 at 9:30 AM, Ashish Goel ashg...@gmail.com wrote:



 int dstart = -1;
 int dend = -1;
 int istart=-1; int iend = -1;
 bool decreasing = false;
 for (int i=1;in;i++)
 {
   if (a[i] =a[i-1])
   { if (decreasing)
 {
  dend =i-1; istart=i;
  reverse (a, dstart, dend);
  merge(a,0,dstart-1, dstart, dend); ///merge 0, dstart-1 array with
 array starting at dstart ending at dend
  decreasing = false;
  }
  //   else continue;
   }
if (!decreasing) //first decreasing
   {
  decreasing = true;
  dstart = i;
  iend=i-1;
  merge(a,0, istart-1, istart, iend);
}
 }

 the number of comparison in each merge would be max O(m+n) where m is int
 number of elements in first list and n in second. so if the merge is
 happening k times the order would become O(k*(m+n)) types


 merge will do the merging from bottom so that shift downs are not needed.

 int r1= end1;
 int r2=end2;
 //for every write position, only 1 comparison is done
 while (r2=start1)
 {
if (a[r1]a[r2])
{
 swap(a[r1],a[r2]);
 r2--;//r2 is also write position
}
else
{
  r1--;
}
if (r1==r2) r1--;
 }


 so fr
 5,10,9,14,13,12,17,16,21,20


 what would be the order?


 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Tue, Jul 13, 2010 at 6:00 AM, Gene gene.ress...@gmail.com wrote:

 On Jul 12, 10:48 am, Tech Id tech.login@gmail.com wrote:
  This is a good solution.
 
  Reversing the arrays will be O(n)
  Then merging will be O(n) too.
 
  In place merge is something like this.
  Have two indices as start1 and start2
  start1 points to beginning of mini-sorted portion1
  start2 points to beginning of mini-sorted portion2
 
  Increase both start1 and start2 and swap when necessary.
  adjust start1 and start2 accordingly.
 
  Do the same for other mini-sorted arrays.
 
  So the complexity of this is mO(n) where m is the number of mini
  arrays.
  For m=1, it becomes O(n^2) as expected for a normal sort!

 Correct algorithms for in-place merge are much harder than what you're
 describing here.  Think it through carefully, and you'll see this.

 And don't forget that if you are merging K lists, you need at least K
 log K comparisons to decide the merge order at each step. So if the
 lists being merged have about N items each, the cost of merging is O(N
 K log K) .  In other words, the K in K-tonic makes a difference.

 --
 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
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] stack

2010-07-15 Thread Ashish kumar Jain
Another way in which this can be thought is in terms of Tower of Hanoi
problem.Just introduce two more stacks of same size as input stack and get
the sorted output as result.

On Mon, Jun 14, 2010 at 9:18 AM, Anurag Sharma anuragvic...@gmail.comwrote:

 Why not just pop all elements from stack ( O(n) )  and insert it in a self
 balancing Binary Search Tree (like RB Tree) (O(log(n) ) and then do and
 inorder traversal ( O(n) )and push elements in stack again.
 Time = O(nlog(n) + n)
 Space=O(n) (for storing the tree)

 Anurag Sharma



 On Sun, Jun 13, 2010 at 9:25 PM, Jitendra Kushwaha 
 jitendra.th...@gmail.com wrote:

 Stack can be sorted in O(n^2).

 @sankalp:
  Stack can always be sorted. Why do you think it cant be in some cases ?

 One can think like insertion sort
 algo :
 1. for i in (1,n)
   2. Pop up the top n-1 element and keep nth element in global variable
 say hold
   3. while pushing get the position for hold and push it there

 for loop will take O(n) and step 2 will take take O(n) time. So overall
 O(n^2) complexity
 Program can be done with recursion using a variable (hence O(1) space).
 But it will use system stack :)


 Any comments OR better solution is welcomed??

 --
 Regards
 Jitendra Kushwaha
 MNNIT, Allahabad

  --
 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Regards,
Ashish

-- 
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] b tree:

2010-07-15 Thread jalaj jaiswal
its b tree not binary tree

On Wed, Jul 14, 2010 at 10:45 AM, naveen naveen.cse@gmail.com wrote:

 if I do two traversals of a tree inorder wise i can get it in O(n).
 Questions should be one traversal i think . Then we should use a tree where
 nodes contain links to parents.


 On Tue, Jul 13, 2010 at 6:58 PM, sharad kumar sharad20073...@gmail.comwrote:

 Find the median in B-tree of order n

 --
 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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 *D.S.Naveen
 Trainee Engineer
 SQA*
 *My Blog: 
 **http://www.naveends.blogspot.com*http://www.naveends.blogspot.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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
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: Difference b/w two elements in a array

2010-07-15 Thread jalaj jaiswal

 I have one more question here , suppose we have some dynamic array
 ( of const size ) where insertions and removal is happening
 dynamically ---
 you want the 2 elements from the array having least difference. Design
 a data structure for this. Less than O(n) solution appreciated.


i have a nlogn solution for it... as the insertion and deletion is happening
dynamically... thinkin of O(n) is ...a bit tedious i think





 On Jul 14, 9:27 am, Ashish Goel ashg...@gmail.com wrote:
  count sort and then find mindiff
 
  fot (int i=1;in;i++)
  if (a[i]-a[i-1] mindiff) { mindiff =a[i]-a[i-1]; ele1=a[i-1];
 ele2=a[i];}
 
  Best Regards
  Ashish Goel
  Think positive and find fuel in failure
  +919985813081
  +919966006652
 
  On Tue, Jul 13, 2010 at 2:47 PM, Tech Id tech.login@gmail.com
 wrote:
   Construct a BST for the array - O(nlogn)
   Traverse the tree and find a node which has
   minimum difference with either its left or
   right child in whole of the tree.
   (Because the required numbers have to be
   adjacent to each other in a sorted array). - O(n)
 
   = Total order:O(nlogn)
 
   --
   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.comalgogeeks%2bunsubscr...@googlegroups.com
 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
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: AMAZON Interview Question

2010-07-15 Thread ankur aggarwal
@harit..
logic plz.. not the code..

On Wed, Jul 14, 2010 at 9:50 PM, harit agarwal agarwalha...@gmail.comwrote:

 this is O(n) solution and using O(n) space...

 #includeiostream
 #includevector
 #includestack
 using namespace std;
 void leader_count(vectorint v,int *ar)
 {
 stackint s;
 int n=v.size();
 int i=n-1;
  while(i=0)
 {
 if(s.empty())
  {
 ar[--n]=0;
 s.push(i);
  i--;
 }
 else
  {
 if(v[i] = v[s.top()])
 {
  ar[--n]=s.top();
 s.push(i);
 i--;
  }
 else
 {
  s.pop();
 }
 }
  }
 for(int i=v.size()-1;i=0;i--)
 if(ar[i]!=0)
  ar[i]=ar[ar[i]]+1;

 }
 main()
 {
 int i;
  vectorint v;
 while(cini)
 v.push_back(i);
  int *ar=new int[v.size()];
 leader_count(v,ar);
 for(int i=0;iv.size();i++)
 coutar[i]  ;
 }

  --
 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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards

Ankur Aggarwal

-- 
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] Finding latitude and longitude

2010-07-15 Thread siddharth srivastava
Hi

If I have a (latitude, langitude) as well as pixel positions of those
locations, then how can (longitude, latitude) or pixel coordinates of a
point x metres away can be found ?

If this information is not enough, what else information might be required ?

-- 
Siddharth Srivastava

When you have learned to snatch the error code from the trap frame, it will
be time for you to leave.

-- 
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] online movies streaming

2010-07-15 Thread ankur aggarwal
Hey moderator..

try 2 avoid these members...

On Thu, Jul 15, 2010 at 1:01 AM, X +18 mai...@jadidnet.net wrote:

 http://bit.ly/aRDr4E

 Streaming entertainment network with lots of video clips. ... Use a
 software called qvod player, you can watch the DVD movies online for free.
 ...

 http://bit.ly/aRDr4E

 Watch free Movies, TV-shows, Anime, Documentaries and Cartoons online on
 alluc.org - Worlds biggest video stream Database!

 http://bit.ly/aRDr4E

 --
 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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards

Ankur Aggarwal

-- 
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] Google Interview Question

2010-07-15 Thread harit agarwal
@varun
c should also be in the 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.



Re: [algogeeks] Google Interview Question

2010-07-15 Thread umesh kewat
Hi,

suppose we have given n distinct numbers are a[n].

1. sort them using quick or any other sort in O(nlogn)
2. use then

 int find(int *arr, int n) /* return largest number if fing it otheriwse
retirn 0*/
 {
 int i,j,k, temp;

 for(k=n-1; k2;k--)
 {
j = k-1
i=0;
 while(i!=j)
  {
temp = arr[i]+arr[j];
if(temp== arr[k])
return arr[k];
else if(temparr[k])
i++;
else
j--;
   }
  }
 return 0;
}


-- 
Thanks  Regards

Umesh kewat
Hyderabad


On Thu, Jul 15, 2010 at 9:07 AM, Ashish Goel ashg...@gmail.com wrote:

 sort using counting sort or quickselect

 now a and b are less than c

 so find c first
 suppose c's index is k
 the start two indexes i=0 and j=k-1, if a[i]+a[j] ==a[k] return these
 numbers, else add elements at i,j if the sum is greater than c reduce j, if
 less than c increase i

 alternatively sort array, find index of c, make a BST or a hash table,
 starting from index 0 of the sorted array, find c-athis is overhead on
 second thoughts, i will proceed with first approach


 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652



 On Wed, Jul 14, 2010 at 9:55 PM, siddharth shankar 
 siddharth.shanka...@gmail.com wrote:

 O ( n^2 ) soln can be done 
 step :

 1 . sort array in n*log(n) .
 2.  for every C from last find two number A  B such that A+B=C ...   O(
 n^2 )
 Total :- O(N^2)

 can we improve it further ??  any help please 

 On Wed, Jul 14, 2010 at 10:57 AM, Debajyoti Sarma 
 sarma.debajy...@gmail.com wrote:

 An array contains the set of positive integer. Find the largest number
 c such that c=a+b where a,b,c are distinct number of the set?
 [Consider , reducing 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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 siddharth shankar


  --
 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Stock prices.

2010-07-15 Thread jalaj jaiswal
int MaxStockGain(int arr[], int size)
{
if(size = 0)
return 0;

int curMin = arr[0];
int MaxGain = 0;

for(int i = 1; i  size; ++i)
{
if (arr[i]  curMin)
{
curMin = arr[i];

}


int currGain = arr[i] - curMin;
if(currGain  MaxGain)
{
MaxGain = currGain;
}
}

return MaxGain;
}

On Tue, Jul 13, 2010 at 4:02 PM, srikanth sg srikanthini...@gmail.comwrote:

 how you do that in O(n)...
 can you explain ???


 On Mon, Jul 12, 2010 at 11:37 PM, amit amitjaspal...@gmail.com wrote:

 Stock prices are given to you at various time intervals. p1, p2,
 p3,... you are allowed to buy and sell only once each. So write a
 program to find the index where you would buy and where you would sell
 to maximize profit

 Correct me if i am wrong --

 I think we can solve it in O(n) we simple have to find max(A[j]-A[i])
 with ji.
 This is already discussed or am i missing something??


 --
 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
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] b tree:

2010-07-15 Thread naveen
sorry i didnt see it ..

On Thu, Jul 15, 2010 at 4:18 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:

 its b tree not binary tree


 On Wed, Jul 14, 2010 at 10:45 AM, naveen naveen.cse@gmail.com wrote:

 if I do two traversals of a tree inorder wise i can get it in O(n).
 Questions should be one traversal i think . Then we should use a tree where
 nodes contain links to parents.


 On Tue, Jul 13, 2010 at 6:58 PM, sharad kumar 
 sharad20073...@gmail.comwrote:

 Find the median in B-tree of order n

 --
 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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 *D.S.Naveen
 Trainee Engineer
 SQA*
 *My Blog: 
 **http://www.naveends.blogspot.com*http://www.naveends.blogspot.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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 With Regards,
 Jalaj Jaiswal
 +919026283397
 B.TECH IT
 IIIT ALLAHABAD

 --
 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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
D.S.Naveen
Trainee Engineer
SQA
My Blog: http://www.naveends.blogspot.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] Re: Finding latitude and longitude

2010-07-15 Thread Tech Id
This seems to be asked in context of google maps.

While drawing map at a particular zoom level, ratio of map-area-on-
screen and shown-latitudes/longitudes-area is known.
So, x meters can be converted to latitiude/longitude difference easily
by this ratio.


On Jul 15, 12:59 pm, siddharth srivastava akssps...@gmail.com wrote:
 Hi

 If I have a (latitude, langitude) as well as pixel positions of those
 locations, then how can (longitude, latitude) or pixel coordinates of a
 point x metres away can be found ?

 If this information is not enough, what else information might be required ?

 --
 Siddharth Srivastava

 When you have learned to snatch the error code from the trap frame, it will
 be time for you to leave.

-- 
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] Stock prices.

2010-07-15 Thread Ashish Goel
technically i can sell first and buy later also
so this solution doesnot consider shorts and long..
my algo would be

return max(MaxStockGain(a,size), MaxStockGain(reverse(a,size),size));


can be done better..without reverse too :)
lol

Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Thu, Jul 15, 2010 at 4:29 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:

 int MaxStockGain(int arr[], int size)
 {
 if(size = 0)
 return 0;

 int curMin = arr[0];
 int MaxGain = 0;

 for(int i = 1; i  size; ++i)
 {
 if (arr[i]  curMin)
 {
 curMin = arr[i];

 }


 int currGain = arr[i] - curMin;
 if(currGain  MaxGain)
 {
 MaxGain = currGain;
 }
 }

 return MaxGain;

 }

 On Tue, Jul 13, 2010 at 4:02 PM, srikanth sg srikanthini...@gmail.comwrote:

 how you do that in O(n)...
 can you explain ???


 On Mon, Jul 12, 2010 at 11:37 PM, amit amitjaspal...@gmail.com wrote:

 Stock prices are given to you at various time intervals. p1, p2,
 p3,... you are allowed to buy and sell only once each. So write a
 program to find the index where you would buy and where you would sell
 to maximize profit

 Correct me if i am wrong --

 I think we can solve it in O(n) we simple have to find max(A[j]-A[i])
 with ji.
 This is already discussed or am i missing something??


 --
 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 With Regards,
 Jalaj Jaiswal
 +919026283397
 B.TECH IT
 IIIT ALLAHABAD

 --
 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.comalgogeeks%2bunsubscr...@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: Finding latitude and longitude

2010-07-15 Thread siddharth srivastava
Hi

On 15 July 2010 07:37, Tech Id tech.login@gmail.com wrote:

 This seems to be asked in context of google maps.


I asked in terms of OSM.


 While drawing map at a particular zoom level, ratio of map-area-on-
 screen and shown-latitudes/longitudes-area is known.
 So, x meters can be converted to latitiude/longitude difference easily
 by this ratio.


would it change then ?




 On Jul 15, 12:59 pm, siddharth srivastava akssps...@gmail.com wrote:
  Hi
 
  If I have a (latitude, langitude) as well as pixel positions of those
  locations, then how can (longitude, latitude) or pixel coordinates of a
  point x metres away can be found ?
 
  If this information is not enough, what else information might be
 required ?
 
  --
  Siddharth Srivastava
 
  When you have learned to snatch the error code from the trap frame, it
 will
  be time for you to leave.

 --
 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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Siddharth Srivastava

When you have learned to snatch the error code from the trap frame, it will
be time for you to leave.

-- 
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: sort in O(n) array which increases and then decreased and then increases...5,10,15,14,9,4,1,3,6,7,11,9,8,2

2010-07-15 Thread Ashish Goel
good one

shifting array is the solution but i want to do it without shifting, is
there a solution!!!


Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Thu, Jul 15, 2010 at 4:26 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:

 try merging this array
 [{5,9,10},{3,6,7,9}]...

 On Wed, Jul 14, 2010 at 9:30 AM, Ashish Goel ashg...@gmail.com wrote:



 int dstart = -1;
 int dend = -1;
 int istart=-1; int iend = -1;
 bool decreasing = false;
 for (int i=1;in;i++)
 {
   if (a[i] =a[i-1])
   { if (decreasing)
 {
  dend =i-1; istart=i;
  reverse (a, dstart, dend);
  merge(a,0,dstart-1, dstart, dend); ///merge 0, dstart-1 array with
 array starting at dstart ending at dend
  decreasing = false;
  }
  //   else continue;
   }
if (!decreasing) //first decreasing
   {
  decreasing = true;
  dstart = i;
  iend=i-1;
  merge(a,0, istart-1, istart, iend);
}
 }

 the number of comparison in each merge would be max O(m+n) where m is int
 number of elements in first list and n in second. so if the merge is
 happening k times the order would become O(k*(m+n)) types


 merge will do the merging from bottom so that shift downs are not needed.

 int r1= end1;
 int r2=end2;
 //for every write position, only 1 comparison is done
 while (r2=start1)
 {
if (a[r1]a[r2])
{
 swap(a[r1],a[r2]);
 r2--;//r2 is also write position
}
else
{
  r1--;
}
if (r1==r2) r1--;
 }


 so fr
 5,10,9,14,13,12,17,16,21,20


 what would be the order?


 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Tue, Jul 13, 2010 at 6:00 AM, Gene gene.ress...@gmail.com wrote:

 On Jul 12, 10:48 am, Tech Id tech.login@gmail.com wrote:
  This is a good solution.
 
  Reversing the arrays will be O(n)
  Then merging will be O(n) too.
 
  In place merge is something like this.
  Have two indices as start1 and start2
  start1 points to beginning of mini-sorted portion1
  start2 points to beginning of mini-sorted portion2
 
  Increase both start1 and start2 and swap when necessary.
  adjust start1 and start2 accordingly.
 
  Do the same for other mini-sorted arrays.
 
  So the complexity of this is mO(n) where m is the number of mini
  arrays.
  For m=1, it becomes O(n^2) as expected for a normal sort!

 Correct algorithms for in-place merge are much harder than what you're
 describing here.  Think it through carefully, and you'll see this.

 And don't forget that if you are merging K lists, you need at least K
 log K comparisons to decide the merge order at each step. So if the
 lists being merged have about N items each, the cost of merging is O(N
 K log K) .  In other words, the K in K-tonic makes a difference.

 --
 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 With Regards,
 Jalaj Jaiswal
 +919026283397
 B.TECH IT
 IIIT ALLAHABAD

 --
 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.comalgogeeks%2bunsubscr...@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: Road crossing algorithm

2010-07-15 Thread Tech Id
An inefficient but working method is the brute force one.
Do a recursive test for all the cases possible and if you
find one which helps the frog cross the road, then that is it.

Let int car_times[numLanes] store the time each car will take to reach
the path where the frog is crossing the road.

Frog has 3 commands at his disposal:
a) jump_fwd
b) jump_back
c) wait


Let Vector command cmds be the desired sequence of commands to reach
the destination.
We need to write a function which will produce the above global vector
as its output.

enum command {F, B, W};
Vector command cmds;
int car_times[numLanes]; //given in the beginning

bool try_remaining_path (int lane_num, int time_passed) {

int orig_time = time_passed;
int orig_lanes = lane_num;

while (car_times[lane_num] - time_passed= 1) {
cmds.push_back (F);
bool rest_is_possible  = try_remaining_path (time_passed+1,
lane_num+1);
if (rest_is_possible)
return true;
cmds.pop();
cmds.push_back (W);
time_passed++;
}

// if we come here, means that there was no point
// in waiting in this lane_num, as the frog will be
// killed at one point or the other.

// let us try by jumping back one step.
time_passed = orig_time;

while (lane_num  0) {

cmds.push_back (B);
time_passed++;
lane_num--;

bool rest_is_possible  = try_remaining_path (time_passed,
lane_num);
if (rest_is_possible)
return true;
}

// Nothing is possible in this lane.
// Empty the commands B from the vector and try something else.

   while (orig_lanes  0 ) {
   cmds.pop();
   orig_lanes--;
   }

return false;
}

Above seems very inefficient to me because it calculates all the
possible jumps at each lane.
Please help in improving it.


On Jul 15, 9:24 am, Ashish kumar Jain akjlucky4...@gmail.com wrote:
 I think this will help:

 http://en.wikipedia.org/wiki/Frogger

 Consider the roads to be n-laned and of constant width with constant time
 traffic coming on each lane.For example,say after 1 minute,a car comes on
 each lane but in a arithmetic sequence and not all at same time.To make it
 more clear,

 at t=1 minute,car at lane 1 travelling with constant velocity v and takes
 T time to cross the screen/lane1.

 at t=2 minute,another car comes now in lane 2 with same constant velocity
 and so on..

 Now the frog can cross one lane either back or forth in one jump.These are
 the only movements allowed.The jump time is considerable(say in above case 1
 minute only).Note that times are all not correctly mentioned and consider
 times which are appropriate for the problem.The time details are mentioned
 to make everyone understand the problem.

 Design an algorithm to guarantee that the frog crosses the road safely.

 Think first..Hint is
 downwards.
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 ..
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .

 Hint: Think in terms of multithreading,semaphores,mutex and vectors
 etc..





 On Wed, Jul 14, 2010 at 11:33 PM, Tech Id tech.login@gmail.com wrote:
  A frog has to cross a road to meet
  its beloved she-frog at the other end.

  The road however has cars coming and
  can crush the frog.

  Road is two lanes wide.

  Devise an algorithm to help the frog carry on its family.

  (I am sorry but it seems that I have missed
  some parts of the problem here. If someone
  remembers the complete question, please help me).
  Thanks in advance!

  --
  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.comalgogeeks%2bunsubscr...@googlegroups 
  .com
  .
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 --
 Regards,
 Ashish

-- 
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: Road crossing algorithm

2010-07-15 Thread Ashish Goel
http://code.google.com/p/frogger-game/source/browse/trunk/

can it be interview question??

the frong will wait and this would vary at run time, the car_times is
storing just one value, multiple cars can come in a lane so it should be
hash map

one thought: for each lane we know when the car would not be there
we only need to consider the time t+delta in a lane when frong is in lane n
at time t
so it implies that if there are n lanes, and we know all the time when the
car is not at the crossing point, we need to find a monotonically increasing
sequence


eg
lane1 4 7 10
lane2 2 5  9
lane3 3 6 11
lane4 1 4  7

so the times when the car is not there will be


lan1 1 2 3 5 6 8 9 11 12
lan2  1 3 4 6 7 8 10 11 12
lan3  1 2 4 5 7 8 9 10 12
lan4 2 3 5 6 8 9 10 11 12


so 1-345 gives one solution
2-3-4-5 another solution



Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Thu, Jul 15, 2010 at 9:56 PM, Tech Id tech.login@gmail.com wrote:

 An inefficient but working method is the brute force one.
 Do a recursive test for all the cases possible and if you
 find one which helps the frog cross the road, then that is it.

 Let int car_times[numLanes] store the time each car will take to reach
 the path where the frog is crossing the road.

 Frog has 3 commands at his disposal:
 a) jump_fwd
 b) jump_back
 c) wait


 Let Vector command cmds be the desired sequence of commands to reach
 the destination.
 We need to write a function which will produce the above global vector
 as its output.

 enum command {F, B, W};
 Vector command cmds;
 int car_times[numLanes]; //given in the beginning

 bool try_remaining_path (int lane_num, int time_passed) {

int orig_time = time_passed;
int orig_lanes = lane_num;

while (car_times[lane_num] - time_passed= 1) {
cmds.push_back (F);
bool rest_is_possible  = try_remaining_path (time_passed+1,
 lane_num+1);
if (rest_is_possible)
return true;
cmds.pop();
cmds.push_back (W);
time_passed++;
}

// if we come here, means that there was no point
// in waiting in this lane_num, as the frog will be
// killed at one point or the other.

// let us try by jumping back one step.
time_passed = orig_time;

while (lane_num  0) {

cmds.push_back (B);
time_passed++;
lane_num--;

bool rest_is_possible  = try_remaining_path (time_passed,
 lane_num);
if (rest_is_possible)
return true;
}

// Nothing is possible in this lane.
// Empty the commands B from the vector and try something else.

   while (orig_lanes  0 ) {
   cmds.pop();
   orig_lanes--;
   }

return false;
 }

 Above seems very inefficient to me because it calculates all the
 possible jumps at each lane.
 Please help in improving it.


 On Jul 15, 9:24 am, Ashish kumar Jain akjlucky4...@gmail.com wrote:
  I think this will help:
 
  http://en.wikipedia.org/wiki/Frogger
 
  Consider the roads to be n-laned and of constant width with constant time
  traffic coming on each lane.For example,say after 1 minute,a car comes on
  each lane but in a arithmetic sequence and not all at same time.To make
 it
  more clear,
 
  at t=1 minute,car at lane 1 travelling with constant velocity v and takes
  T time to cross the screen/lane1.
 
  at t=2 minute,another car comes now in lane 2 with same constant velocity
  and so on..
 
  Now the frog can cross one lane either back or forth in one jump.These
 are
  the only movements allowed.The jump time is considerable(say in above
 case 1
  minute only).Note that times are all not correctly mentioned and consider
  times which are appropriate for the problem.The time details are
 mentioned
  to make everyone understand the problem.
 
  Design an algorithm to guarantee that the frog crosses the road safely.
 
  Think first..Hint is
  downwards.
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  ..
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
 
  Hint: Think in terms of multithreading,semaphores,mutex and vectors
  etc..
 
 
 
 
 
  On Wed, Jul 14, 2010 at 11:33 PM, Tech Id tech.login@gmail.com
 wrote:
   A frog has to cross a road to meet
   its beloved she-frog at the other end.
 
   The road however has cars coming and
   can crush the frog.
 
   Road is two lanes wide.
 
   Devise an algorithm to help the frog carry on its family.
 
   (I am sorry but it seems that I have missed
   some parts of the problem here. If someone
   remembers the complete question, please help me).
   Thanks in advance!
 
   --
   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.comalgogeeks%2bunsubscr...@googlegroups.com
 

[algogeeks] Re: Road crossing algorithm

2010-07-15 Thread Tech Id
Hi Ashish,

Your algo does not have a chance for jump_back.
This may be required for certain cases, especially when multiple cars
are running on one lane.

My solution was for one car on one lane, hence car_times[i] gives the
car in i-th lane will take to hit the path frog is trying to cross.
It should not be too difficult to put multiple cars on single lane in
my algo.

Actually, from a game perspective, the problem can have many parts
like:
speed of cars vary,
frog can move sideways too instead of vertically on the road.
frog can make upto m jumps
etc etc.

Regards
Techie

-- 
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: Finding latitude and longitude

2010-07-15 Thread Gene
Think about it more carefully. If you are 1m south of the north pole,
then walk pi meters east or west, your longitude changes by 180
degrees.  At the equator it changes hardly at all.  This is hard to do
accurately and correctly over the whole earth.  Google geographic
coordinate transformations.  There is free software available at
http://earth-info.nga.mil/GandG/geotrans/index.html .  If you only
need approximate answers or your distances are short, you can use
spherical geometry, which is not so bad.

On Jul 15, 11:03 am, siddharth srivastava akssps...@gmail.com wrote:
 Hi

 On 15 July 2010 07:37, Tech Id tech.login@gmail.com wrote:

  This seems to be asked in context of google maps.

 I asked in terms of OSM.



  While drawing map at a particular zoom level, ratio of map-area-on-
  screen and shown-latitudes/longitudes-area is known.
  So, x meters can be converted to latitiude/longitude difference easily
  by this ratio.

 would it change then ?







  On Jul 15, 12:59 pm, siddharth srivastava akssps...@gmail.com wrote:
   Hi

   If I have a (latitude, langitude) as well as pixel positions of those
   locations, then how can (longitude, latitude) or pixel coordinates of a
   point x metres away can be found ?

   If this information is not enough, what else information might be
  required ?

   --
   Siddharth Srivastava

   When you have learned to snatch the error code from the trap frame, it
  will
   be time for you to leave.

  --
  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.comalgogeeks%2bunsubscr...@googlegroups 
  .com
  .
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 --
 Siddharth Srivastava

 When you have learned to snatch the error code from the trap frame, it will
 be time for you to leave.

-- 
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: graph

2010-07-15 Thread Gene
Construct the transitive closure of the graph.  You can use Warshall's
algorithm, which is O(v^3) in run time.  If any row of the adjacency
matrix is all 1's, the corresponding vertex can reach all others.  You
can ignore the diagonal element if you don't care whether vertices are
reachable from themselves (i.e. whether they are contained in a
cycle).

On Jul 12, 1:06 pm, Love-143 lovekesh6mn...@gmail.com wrote:
 1.Give an efficient algorithm which takes as input a directed graph G =
 (V,E), and determines whether or not there is a vertex s is in V from which
 all other vertices are reachable.?

-- 
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] The strong NO to circular lists argument

2010-07-15 Thread Jacko
http://groups.google.com/group/comp.lang.misc/browse_thread/thread/35967349de8446c1#

-- 
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] Dynamic Programming Problem on Strings

2010-07-15 Thread mohit ranjan
@Ajeet
*
Google Dyck words*


Mohit


On Mon, Jul 12, 2010 at 1:43 PM, aejeet aej...@gmail.com wrote:

  A string can contain only the characters A and B.

 The string formation must follow the following rules
 1. The number of occurrences of A and that of B must be equal in the
 string
 2. For any prefix of string, the number occurrences of A must be
 greater than or equal to the number of occurrences of B.

 Now given an integer of length N, find the number of possible string
 formations adhering the rules above.

 --
 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.comalgogeeks%2bunsubscr...@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] 0-1 knapsack problem: uniqueness of optimal solutions

2010-07-15 Thread Greg
Hello:

This is a problem in theoretical computer science and algorithms.
When solving the 0-1 knapsack problem using dynamic programming, how
can you use the resulting table to determine whether the optimal
solution is unique?

The problem is the following:  A thief is going to steal some items
and put them in his knapsack, which has a maximum weight capacity of
W, a positive integer.  He must select from a finite set of items,
each of which has a positive integer weight and a positive integer
value (in dollars, say).  The thief has to determine which collection
of items light enough for him to carry has the maximum total value.

The solution method is described at 
http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
.  The thief makes a table indexed by item number i (from 0 to the
total number of items N) and total weight j (from 0 to W).  Let c(i,j)
be the number in the ith row and jth column.  c(i,j) is the maximum
total value of items chosen from among items #1, 2, ... i whose total
weight is less than or equal to j.  The 0 row and 0 column of the
table are of course zero.  It is a simple matter to fill in the table
in row-major order.  After the table is complete, c(N,W) is the
maximum value of loot the thief can carry away.  The completed table
is then used to determine which items the thief should choose.

My question is, how can you use the table to determine whether the
optimal solution is unique?  For example, suppose the knapsack
capacity is 5 pounds, and there are four items, with weight/value
pairs (1 lb, $1), (2 lb., $3), (3 lb., $3), (4 lb., $5).  The thief
should take either the first and fourth, or the second and third
items, for a total weight of 5 lb. and value of $6.

The solutions which I have read use a deterministic process for
determining which items the thief takes, which gives you one solution
but does not tell whether it is unique.


Greg Spradlin

-- 
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] Dynamic Programming Problem on Strings

2010-07-15 Thread Anil C R
that would be the Catlan number...
Anil


On Thu, Jul 15, 2010 at 11:41 PM, mohit ranjan shoonya.mo...@gmail.comwrote:

 @Ajeet
 *
 Google Dyck words*


 Mohit



 On Mon, Jul 12, 2010 at 1:43 PM, aejeet aej...@gmail.com wrote:

  A string can contain only the characters A and B.

 The string formation must follow the following rules
 1. The number of occurrences of A and that of B must be equal in the
 string
 2. For any prefix of string, the number occurrences of A must be
 greater than or equal to the number of occurrences of B.

 Now given an integer of length N, find the number of possible string
 formations adhering the rules above.

 --
 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.