Re: [algogeeks] Re: zero sum subarray

2010-11-30 Thread Puneet Ginoria 
You may solve it using depth first search. it will give you all possible
solutions

On Sun, Nov 7, 2010 at 12:11 AM, Raj rajmangaltiw...@gmail.com wrote:

 Compute PrefixSum Array.
 PrefixSum[i]=a[0]+a[1]+a[2]++a[i-1]+a[i]

 Now problem reduces to finding two elements having same value.


 For  PrefixSum[i], search an element having value PrefixSum[i] in
 array PrefixSum from indices 0 to i-1.
 Linear search would cost O(n^2), balanced tree O(nlogn), hash O(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.



-- 
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] cycle cover

2010-11-30 Thread Lewis H 
With a directed graph G and we want to find the cycle cover(a set of
cycles s.t. every vertex is in exactly 1 cycle), can we do this in
poly-time? Can we break each node into entry/exit nodes and do
bipartite matching? Would this work?

Thanks,
L.H.

-- 
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 prog.

2010-11-30 Thread Algoose chase 
thats right !
DP must be the best approach to solve it !



On Tue, Nov 30, 2010 at 10:40 PM, Akash Agrawal
akash.agrawa...@gmail.comwrote:

 In addition to these assumptions, you have also assumed that numbers are
 greater than 1 else * will lower the result.

 Regards,
 Akash Agrawal
 http://tech-queries.blogspot.com/



 On Thu, Nov 25, 2010 at 11:18 AM, Algoose chase harishp...@gmail.comwrote:

 For this specific case since only 2 operators are used : + , *  and we
 know that * is the operator that maximizes the value(provided both the
 operands are not equal to one / none of the operand is zero and also given
 that operands are +ve ).
 Doing * operation as late as possible should suffice right ?

 For Eg: Do all additions in the first pass and do all multiplications in
 2nd pass.

 is there be any case where the above mentioned logic fails ?

 On Wed, Nov 24, 2010 at 4:07 PM, Amir hossein Shahriari 
 amir.hossein.shahri...@gmail.com wrote:

 you can  use an algorithm similar to matrix chain multiplication i.e. if
 dp[i][j] is the maximum value that you can get with the numbers v_i to v_j
 and in order to maximize it find k that maximizes ( dp[i][k]  op_k  dp[k][j]
 )
 v_i is the ith value and op_k is the kth operator
 obviously if i==j : dp[i][j] = v_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.


  --
 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.