Re: [algogeeks] Re: DP

[Anand]

Yes.
http://codepad.org/2KFrv8cs

On Fri, Oct 8, 2010 at 9:56 PM, Lego Haryanto wrote:

> I think this pasted code is incorrect ... answer for { 2, 5, 7, 1, 8, 9 }
> should be 18, right?
>
> On Thu, Oct 7, 2010 at 10:53 PM, Anand  wrote:
>
>> Using standard Dynamic Programing logic:
>> http://codepad.org/IwBTor4F
>>
>>
>>
>> On Thu, Oct 7, 2010 at 8:43 PM, Gene  wrote:
>>
>>> Nice problem.  Let N_1, N_2, ... N_n be the values of the N notes.
>>> Let F(i,j) be the maximum possible score the current player can get
>>> using only notes i through j.  Then
>>>
>>> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) )
>>>
>>> This is saying that the current player always makes the choice that
>>> minimizes B the best score that the other player can achieve.  When we
>>> know that choice, the best _we_ can do is the sum of all the available
>>> notes minus B.
>>>
>>> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j)
>>> where i > j.
>>>
>>> For example, suppose we have notes 3 7 2 1 .  The answer we want is
>>> F(1,4).
>>>
>>> Initially we have
>>> F(1,1) = 3
>>> F(2,2) = 7
>>> F(3,3) = 2
>>> F(4,4) = 1
>>>
>>> Now we can compute
>>> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7).
>>> F(2,3) =  9 - min(F(3,3), F(2,2)) =  9 - min(2,7) = 7 (pick N_2=7).
>>> F(3,4) =  3 - min(F(4,4), F(3,3)) =  3 - min(1,2) = 2 (pick N_3=2).
>>> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care).
>>> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7).
>>> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1).
>>>
>>>
>>> On Oct 7, 8:14 pm, Anand  wrote:
>>> > Given a row of notes (with specified values), two players play a game.
>>> At
>>> > each turn, any player can pick a note from any of the two ends. How
>>> will the
>>> > first player maximize his score? Both players will play optimally.
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
>
> --
> 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] Matroid Problem

[pre lak]

Hi all,
Show how to transform the weight function of a weighted matroid problem
where the desired optimal solution is a minimum weight maximal independent
subset to make it a standard weighted matroid problem.

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

[Lego Haryanto]

I think this pasted code is incorrect ... answer for { 2, 5, 7, 1, 8, 9 }
should be 18, right?

On Thu, Oct 7, 2010 at 10:53 PM, Anand  wrote:

> Using standard Dynamic Programing logic:
> http://codepad.org/IwBTor4F
>
>
>
> On Thu, Oct 7, 2010 at 8:43 PM, Gene  wrote:
>
>> Nice problem.  Let N_1, N_2, ... N_n be the values of the N notes.
>> Let F(i,j) be the maximum possible score the current player can get
>> using only notes i through j.  Then
>>
>> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) )
>>
>> This is saying that the current player always makes the choice that
>> minimizes B the best score that the other player can achieve.  When we
>> know that choice, the best _we_ can do is the sum of all the available
>> notes minus B.
>>
>> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j)
>> where i > j.
>>
>> For example, suppose we have notes 3 7 2 1 .  The answer we want is
>> F(1,4).
>>
>> Initially we have
>> F(1,1) = 3
>> F(2,2) = 7
>> F(3,3) = 2
>> F(4,4) = 1
>>
>> Now we can compute
>> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7).
>> F(2,3) =  9 - min(F(3,3), F(2,2)) =  9 - min(2,7) = 7 (pick N_2=7).
>> F(3,4) =  3 - min(F(4,4), F(3,3)) =  3 - min(1,2) = 2 (pick N_3=2).
>> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care).
>> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7).
>> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1).
>>
>>
>> On Oct 7, 8:14 pm, Anand  wrote:
>> > Given a row of notes (with specified values), two players play a game.
>> At
>> > each turn, any player can pick a note from any of the two ends. How will
>> the
>> > first player maximize his score? Both players will play optimally.
>>
>> --
>> 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.
>



-- 
Fear of the LORD is the beginning of knowledge (Proverbs 1:7)

-- 
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] double tower of hanoi

[Terence]

@ravindra

Great solution. But I need some clarification on my solution to the second.

My solution to the second is based on the solution to the first.

As I stated, in the solution to the first, only the last 2 disks are 
swapped, while the order of all other disks are preserved.
So moving the same pile of disks twice will preserve the original order 
of all disks.


In step 1) 3) 5) 7) of my solution to the second,  the process of a) is 
performed for the first (2n-2) disks. (No need to preserve order)
After step 1)-3) and 5)-7), the order of the first (2n-2) disks is 
preserved. So order of all disks is preserved after 1)-7).


Denote the number of moves as f(n) in case a), and g(n) in case b).
We have:
f(n) = 2^(n+1) - 2 and
g(n) = 4f(n-1)+3.
So  g(n) = 4*2^n-5


On 2010-10-9 1:56, ravindra patel wrote:

@Terence

Solution for first one is trivial. Just double the number of moves of 
typical ToH as each pair requires now 2 moves.


In second one the approach is correct but the calculation is wrong.
F(n) = 4f(n-1) + 3 = 3(4^n -1)/(4-1) = 4^n-1 = 2^2n -1.

This can however be optimized as you can reduce the number of recursions.

1- Move (2n-2, From source, to dest) [f(n-1)]
2- Move the last 2 disks from source to temp (2 moves and order reversed)
3- Move (2n-2, From dest, to source) [f(n-1)]
4- Move the last 2 disks from temp to dest (2 moves and original order 
recovered)

5- Move(2n-2, From source, to dest) [f(n-1)]

so f(n) = 3f(n-1) + 4, f(1) = 4
f(n) = 4(3^n -1)/(3-1) = 2(3^n -1)

For larger n(>2) this is more efficient.

Thanks,
- Ravindra

On Fri, Oct 8, 2010 at 1:42 PM, Terence > wrote:




On 2010-10-8 15:14, snehal jain wrote:

A Double Tower of Hanoi contains 2n disks of n different
sizes, two of
each size. As usual, we’re required to move only one disk at a
time,
without putting a larger one over a smaller one.
a. How many moves does it take to transfer a double tower from one
peg to another, if disks of equal size are indistinguishable
from each
other?

Denote the minimum moves as f(n).
Like the classical Tower of Hanoi:
1) move the first (2n-2) disks from Peg 0 to Peg 1 -- f(n-1) moves
2) move the last 2 disks from Peg 0 to Peg 2  -- 2 moves
3) move the (2n-2) disks from Peg1 to Peg 2 -- f(n-1) moves
f(n) = 2f(n-1) + 2,  f(1) = 2
So f(n) = 2^(n+1) - 2



b. What if we are required to reproduce the original top-to-bottom
order of all the equal-size disks in the final arrangement?

Denote the minimum moves as g(n).
It can be proved that, in case a, only the last 2 disks are
swapped. The order of all other disks are preserved.
So we only need to modify the process to restore the order of the
last 2 disks.
1) move the first (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
2) move the second last disk from Peg 0 to Peg 1  -- 1 move
3) move the (2n-2) disks from Peg 2 to Peg 1 -- f(n-1) moves
4) move the last disk from Peg 0 to Peg 2 -- 1 move
5) move the first (2n-2) disks from Peg 1 to Peg 0 -- f(n-1) moves
6) move the second last disk from Peg 1 to Peg 2  -- 1 move
7) move the (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
g(n) = 4f(n-1)+3
   = 2^(n+2)-5


-- 
You received this message because you are subscribed to the Google

Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@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] Re: remove redundantt parenthesis

[Amit Agarwal]

@Dave
I agree, I missed those use cases. let me get back with the revised version.

-Regards
Amit Agarwal
blog.amitagrwal.com



On Fri, Oct 8, 2010 at 9:48 PM, Dave  wrote:

> @Amit: There is more to it than that, involving operators of equal
> precedence. Consider a-(b+c) versus (a-b)+c or a+(b-c), or a/(b*c)
> versus (a/b)*c or (a*b)/c. In the first case of each set, removing the
> parentheses is wrong, but in the other cases of each, the parentheses
> are redundant and can be removed. I don't think this can be solved by
> choosing different precedences for + and - or for * and / because
> there is the left-to-right rule for applying sequences of + or -
> operators or sequences of * and / operators.
>
> Dave
>
> On Oct 8, 2:46 am, Amit Agarwal  wrote:
> > 1) Recursion has to be used.
> > 2) Stack has to used
> > 3) If any pair of paranthesis doesn't has any operator outside it, remove
> > the pair
> > 4) If low precedence operator is inside the pair of paranthesis than the
> one
> > surrounding the pair of parenthesis, don't remove paranthesis.
> > 5) If high precedence operator is inside the pair of paranthesis than the
> > one surrounding the pair of parenthesis, remove paranthesis.
> >
> > -Regards
> > Amit Agarwal
> > blog.amitagrwal.com
> >
> >
> >
> > On Fri, Oct 8, 2010 at 11:42 AM, snehal jain 
> wrote:
> > > write a program to remove redundantt parenthesis from an expression
> > > eg
> > > input ((a+b))
> >
> > > output  a+b
> >
> > > input   a+(b*c)
> >
> > > output  a+b*c
> >
> > > inputa*(b+c)
> > > output   a*(b+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.- 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.
>
>

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

[Mukesh Gupta]

4th element of inorder traversal





On Fri, Oct 8, 2010 at 11:49 PM, Anand  wrote:

> Binary search Tree was given. Find 4ths smallest element.
>
> --
> 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: linked lists

[ashita dadlani]

I think we can use KMP string matching algorithm.

On Fri, Oct 8, 2010 at 6:40 PM, shashank jain wrote:

> there are 2 unsorted array we have to want a third array in sorted
> form in mininmum time complexicity
>
> answer can like be this merge the two array in 3rd array then sort the
> array
>
>  or
> sort the individual array and then merge
>
> if feel first one is better
>
> can any one can help
>
>
> On 10/8/10, snehal jain  wrote:
> > @ligerdave
> > m nt getting ur algo..can u explain with an example
> >
> >
> > On 10/8/10, snehal jain  wrote:
> >>
> >> @neeraj
> >> ur worst case complexity will be O(mn)
> >>
> >>
> >>  On 10/8/10, snehal jain  wrote:
> >>>
> >>> @tech
> >>> the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with
> >>> prefix of 2nd
> >>>
> >>>
> >>>  On 10/7/10, ligerdave  wrote:
> 
>  use pointer. shift to left if one more leading char has been found.
>  any unmatched char resets the pointer to first char
> 
>  once you went through the entire list(first one), the pointer on the
>  second list tells you where to concatenate
> 
>  that gives you O(n) where n is the length of first list
> 
>  On Oct 7, 3:52 am, snehal jain  wrote:
>  > There are two linked list, both containing a character in each node.
>  >
>  > If one linked list contain characters  o x e n c and second contain
>  > characters e n c a r t a then the final linked list should contain o
> x
>  > e n c a r t ai.e. if the end of one list is same as the start of
>  > second then those characters should come only once.
>  >
>  > can we do it in O(n+m) where n and m are the length of list. both
> are
>  > singly link list.
> 
>  --
>  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.

[algogeeks] need help solving this problem

[soundar]

how to find last k digits of n power n
0http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] BST

[Anand]

Binary search Tree was given. Find 4ths smallest element.

-- 
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] double tower of hanoi

[ravindra patel]

@Terence

Solution for first one is trivial. Just double the number of moves of
typical ToH as each pair requires now 2 moves.

In second one the approach is correct but the calculation is wrong.
F(n) = 4f(n-1) + 3 = 3(4^n -1)/(4-1) = 4^n-1 = 2^2n -1.

This can however be optimized as you can reduce the number of recursions.

1- Move (2n-2, From source, to dest) [f(n-1)]
2- Move the last 2 disks from source to temp (2 moves and order reversed)
3- Move (2n-2, From dest, to source) [f(n-1)]
4- Move the last 2 disks from temp to dest (2 moves and original order
recovered)
5- Move(2n-2, From source, to dest) [f(n-1)]

so f(n) = 3f(n-1) + 4, f(1) = 4
f(n) = 4(3^n -1)/(3-1) = 2(3^n -1)

For larger n(>2) this is more efficient.

Thanks,
- Ravindra

On Fri, Oct 8, 2010 at 1:42 PM, Terence  wrote:

>
>
> On 2010-10-8 15:14, snehal jain wrote:
>
>> A Double Tower of Hanoi contains 2n disks of n different sizes, two of
>> each size. As usual, we’re required to move only one disk at a time,
>> without putting a larger one over a smaller one.
>> a. How many moves does it take to transfer a double tower from one
>> peg to another, if disks of equal size are indistinguishable from each
>> other?
>>
> Denote the minimum moves as f(n).
> Like the classical Tower of Hanoi:
> 1) move the first (2n-2) disks from Peg 0 to Peg 1 -- f(n-1) moves
> 2) move the last 2 disks from Peg 0 to Peg 2  -- 2 moves
> 3) move the (2n-2) disks from Peg1 to Peg 2 -- f(n-1) moves
> f(n) = 2f(n-1) + 2,  f(1) = 2
> So f(n) = 2^(n+1) - 2
>
>
>
>  b. What if we are required to reproduce the original top-to-bottom
>> order of all the equal-size disks in the final arrangement?
>>
>>  Denote the minimum moves as g(n).
> It can be proved that, in case a, only the last 2 disks are swapped. The
> order of all other disks are preserved.
> So we only need to modify the process to restore the order of the last 2
> disks.
> 1) move the first (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
> 2) move the second last disk from Peg 0 to Peg 1  -- 1 move
> 3) move the (2n-2) disks from Peg 2 to Peg 1 -- f(n-1) moves
> 4) move the last disk from Peg 0 to Peg 2 -- 1 move
> 5) move the first (2n-2) disks from Peg 1 to Peg 0 -- f(n-1) moves
> 6) move the second last disk from Peg 1 to Peg 2  -- 1 move
> 7) move the (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
> g(n) = 4f(n-1)+3
>= 2^(n+2)-5
>
>
> --
> 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: Birds on wire

[Mridul Malpani]

i think we can use poisson distribution formulae for it.


On Oct 7, 2:02 pm, malli  wrote:
> An interesting puzzle. Assume size of each bird to be negligibly
> small. Please provide your answers with analysis.
>
> Take a wire stretched between two posts, and have a large number of
> birds land on it at random. Take a bucket of yellow paint, and for
> each bird, paint the interval from it to its closest neighbour. The
> question is: what proportion of the wire will be painted. More
> strictly: as the number of birds goes to infinity, what is the limit
> of the expected value of the proportion of painted wire, assuming a
> uniform probability distribution of birds on the wire.

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

[JD]

this can be done in O(n) using a stack .

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

[Gene]

We worked on this one before.  Please see
http://groups.google.com/group/algogeeks/msg/e8fb40ab2ba0ecc0

On Oct 8, 2:12 am, snehal jain  wrote:
> write a program to remove redundantt parenthesis from an expression
> eg
> input ((a+b))
>
> output  a+b
>
> input   a+(b*c)
>
> output  a+b*c
>
> input    a*(b+c)
> output   a*(b+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] plz clear my basics

[Soundar]

it is very simple..just think that for sufficiently large n...the
number of times the loop runs will be depend upon wat ?
for example
for(int i=0 to n)
{
  for(int =0 to n)
  {
  //operations
  //
  }
}
for this the time complexity is O(n^2)
because for every i..it runs n times.
for lg n it is more likely to form a binary treeit is just 2 often used
termfor more ,refer algorithms book by thomas coreman

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

[Dave]

@Amit: There is more to it than that, involving operators of equal
precedence. Consider a-(b+c) versus (a-b)+c or a+(b-c), or a/(b*c)
versus (a/b)*c or (a*b)/c. In the first case of each set, removing the
parentheses is wrong, but in the other cases of each, the parentheses
are redundant and can be removed. I don't think this can be solved by
choosing different precedences for + and - or for * and / because
there is the left-to-right rule for applying sequences of + or -
operators or sequences of * and / operators.

Dave

On Oct 8, 2:46 am, Amit Agarwal  wrote:
> 1) Recursion has to be used.
> 2) Stack has to used
> 3) If any pair of paranthesis doesn't has any operator outside it, remove
> the pair
> 4) If low precedence operator is inside the pair of paranthesis than the one
> surrounding the pair of parenthesis, don't remove paranthesis.
> 5) If high precedence operator is inside the pair of paranthesis than the
> one surrounding the pair of parenthesis, remove paranthesis.
>
> -Regards
> Amit Agarwal
> blog.amitagrwal.com
>
>
>
> On Fri, Oct 8, 2010 at 11:42 AM, snehal jain  wrote:
> > write a program to remove redundantt parenthesis from an expression
> > eg
> > input ((a+b))
>
> > output  a+b
>
> > input   a+(b*c)
>
> > output  a+b*c
>
> > input    a*(b+c)
> > output   a*(b+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.- 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.

Re: [algogeeks] Re: Largest Rectangle in a binary Matrix:

[Soundar]

Can u explain z-curve?wat data structure can be used .plz provide a
link  to learn thatthanks 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.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: BiasedRandom fron unbiasedRandom.

[Dave]

@Snehal: If p has a finite binary representation, of say n bits, then
generate a sequence of up to n unbiased random numbers, continuing the
sequence as long as the ith random number agrees with the ith bit to
the right of the binary point. When the ith number disagrees with the
ith bit, return that ith number. If the computation continues until
even the nth number matches the nth bit, then start over.

Example: Suppose that the binary representation of p is 0.101101.
If the first unbiased random number is 1, generate the second number.
If the second number is 0, continue to the third number.
If the third number is 0, return 0.

If p does not have a finite binary representation, e.g., if p = 1/3 or
sqrt(1/2) and you are not using a finite precision floating point
representation, then the algorithm will terminate with probability 1.

Dave

On Oct 8, 2:44 am, snehal jain  wrote:
> Given a unbiased function that generates 0 and 1 with equal
> probability write a function biasedrandom that genreates 0 with
> probability p and 1 with probability 1-p.

-- 
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] double tower of hanoi

[Terence]

On 2010-10-8 15:14, snehal jain wrote:

A Double Tower of Hanoi contains 2n disks of n different sizes, two of
each size. As usual, we’re required to move only one disk at a time,
without putting a larger one over a smaller one.
a. How many moves does it take to transfer a double tower from one
peg to another, if disks of equal size are indistinguishable from each
other?

Denote the minimum moves as f(n).
Like the classical Tower of Hanoi:
1) move the first (2n-2) disks from Peg 0 to Peg 1 -- f(n-1) moves
2) move the last 2 disks from Peg 0 to Peg 2  -- 2 moves
3) move the (2n-2) disks from Peg1 to Peg 2 -- f(n-1) moves
f(n) = 2f(n-1) + 2,  f(1) = 2
So f(n) = 2^(n+1) - 2



b. What if we are required to reproduce the original top-to-bottom
order of all the equal-size disks in the final arrangement?


Denote the minimum moves as g(n).
It can be proved that, in case a, only the last 2 disks are swapped. The 
order of all other disks are preserved.
So we only need to modify the process to restore the order of the last 2 
disks.

1) move the first (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
2) move the second last disk from Peg 0 to Peg 1  -- 1 move
3) move the (2n-2) disks from Peg 2 to Peg 1 -- f(n-1) moves
4) move the last disk from Peg 0 to Peg 2 -- 1 move
5) move the first (2n-2) disks from Peg 1 to Peg 0 -- f(n-1) moves
6) move the second last disk from Peg 1 to Peg 2  -- 1 move
7) move the (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
g(n) = 4f(n-1)+3
= 2^(n+2)-5

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

[Amit Agarwal]

for getting O(n), Counting sort will work but limitation is that you must
know max element possible in the array.

-Regards
Amit Agarwal
blog.amitagrwal.com



On Fri, Oct 8, 2010 at 5:41 AM, Anand  wrote:

> Is there O(n) solution available for it?
>
>
> On Tue, Sep 28, 2010 at 7:19 AM, Nishant Agarwal <
> nishant.agarwa...@gmail.com> wrote:
>
>> #include
>> #include
>> int main()
>> {
>> int a[20],i,n,max,t,j,k;
>> printf("Enter the no. of elements\n");
>> scanf("%d",&n);
>> for(i=0;i> scanf("%d",&a[i]);
>> for(i=0;i> {
>> j=n-1;
>> max=0;
>> k=i;
>> while(i> {
>> if(a[j]=max)
>> {
>> max=a[j];
>> k=j;
>> j--;
>> }
>> else
>> j--;
>> }
>> t=a[i];
>> a[i]=a[k];
>> a[k]=t;
>> }
>> for(i=0;i> printf("%d\t",a[i]);
>> return 0;
>>
>> }
>>
>> On Tue, Sep 28, 2010 at 3:43 AM, Chi  wrote:
>>
>>> Move-To-The-Front.
>>>
>>> On Sep 27, 11:58 pm, Anand  wrote:
>>> >  Given an array of integers, for each index i, you have to swap the
>>> value at
>>> > i with the first value smaller than A[ i ] that comes after index 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.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] BiasedRandom fron unbiasedRandom.

[Terence]

 Use the unbiased random function k times to get an k-bit value x.
If x < 2^k*p, return 0; else return 1;

If p = N/2^r for some integer N and r, choose k=r.
Otherwise, larger k results in better accuracy.

On 2010-10-8 15:44, snehal jain wrote:

Given a unbiased function that generates 0 and 1 with equal
probability write a function biasedrandom that genreates 0 with
probability p and 1 with probability 1-p.



--
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] Binary tree as threads and weights

[Amit Agarwal]

1) Suppose the node which you hold is P
2) Navigate on path from P to Root of Tree[Upside] and flip the relationship
direction for every edge you encounter on the path
3) Make P as Root of tree
4) redraw(P);

-Regards
Amit Agarwal
blog.amitagrwal.com



On Fri, Oct 8, 2010 at 1:29 PM, snehal jain  wrote:

> If we consider the edges in binary tree as threads and nodes in the
> tree as weights hanging from it(it is suspended from the root) then
> how the tree structure will change when the tree is hung from a
> particular leaf.
>
> --
> 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] Find push/pop/min or max in O(1)

[Amit Agarwal]

yes, on every push/pop there will be max 2 push/pop and 2 comparisons which
is ultimately O(1).
(only in case of 1st element of stack there will be 3 push/pop)

-Regards
Amit Agarwal
blog.amitagrwal.com



On Fri, Oct 8, 2010 at 9:31 AM, saurabh singh wrote:

> yes i too think now that it should work..but on every push/pop we will
> need  to update the other two stacks also which can be done in constant
> time..
>
>
> On Fri, Oct 8, 2010 at 12:58 AM, tech rascal wrote:
>
>> I think saurabh gupta is rite.if v take 2 extra stacks ...1 for min
>> and 1 for max, thn some space wud b saved.
>> for the above example .max_stack wud b-
>>
>> >top
>> 45 56 66 76 44343
>>
>> and min_stack wud b-
>>
>> --->top
>> 45 22 3 2 -999
>>
>> so, here v need 2 save only 5 elements in max_stack, 5 elements in
>> min_stack and 15 elements in full_stack ( acc 2 above example only), hence
>> total=25 elements..othrwise if u do it by taking only 1 stack thn u
>> need space for ..15X3 (45)elements.
>>
>> tell me if I am wrong..
>>
>> On Thu, Oct 7, 2010 at 11:49 PM, saurabh singh wrote:
>>
>>> Sorry but I have still not got the solution u have tried to propose here.
>>> Firstly the space complexity remain O(n) only what I said.
>>>
>>> To understand thing u said better lets take an example of stack with
>>> following entries
>>>
>>> --->top
>>> 45  22  56 44 55 3  2  4 -999 4 2  45 66 76 44343
>>>
>>> how will your second stack look like and how will the push/pop/min/max
>>> will work here ?
>>>
>>>
>>>
>>> On Thu, Oct 7, 2010 at 11:33 PM, Saurabh Gupta <
>>> saurabhgupta1...@gmail.com> wrote:
>>>


 On Tue, Oct 5, 2010 at 9:47 AM, saurabh singh 
 wrote:

> elaborate plz


 For every new element in stack, you need thrice of space to store the
 min and max elements also. This has the effect that at state of stack, you
 can get the min and max till that point. Instead of this, maintaining a new
 stack for min elements would be much more efficient in terms of memory 
 since
 in that all the number of elements would be lesser than the main one.

 so, basically in your solution, the size of object will be three times
 bigger than the data type which can hold the number otherwise.


>
> On Tue, Oct 5, 2010 at 9:42 AM, Saurabh Gupta <
> saurabhgupta1...@gmail.com> wrote:
>
>> In this method, the extra memory is used. In fact, maintaining a
>> separate stack of min and max would consume lesser memory than this.
>>
>> On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh <
>> saurabh.n...@gmail.com> wrote:
>>
>>> You will just need to see what is min and max available on the
>>> current top before push. in case of pop u dnt need to do anything...
>>>
>>> consider this array imp of stack
>>> each array index is stored with this object : {data, min_till_here,
>>> max_till_here}
>>>
>>> ->Top
>>> [{4,4,4} , {2,2,4}, {7,2,7} , {-6,-6,7}, {1,-6,7}, {9,-6,9}]
>>>
>>>
>>>
>>> So if u push say 20 then at top u see whats max and min till now.
>>> since curr min (-6) is smaller than 20 so min remains unaffected and 
>>> since
>>> curr max (9) is smaller than 20 so curr max becomes 20. Hence the 
>>> object at
>>> top in stack looks like {20,-6,20}
>>>
>>>
>>> On Wed, Sep 29, 2010 at 10:18 PM, albert theboss <
>>> alberttheb...@gmail.com> wrote:
>>>

 when we pop out something 
 we need to find the max min again if max or min is popped out...
 this ll take again O(n) to find max and min

 Correct me if am wrong

  --
 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,
>>> Saurabh
>>>
>>>  --
>>> 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 un

Re: [algogeeks] remove redundantt parenthesis

[Amit Agarwal]

1) Recursion has to be used.
2) Stack has to used
3) If any pair of paranthesis doesn't has any operator outside it, remove
the pair
4) If low precedence operator is inside the pair of paranthesis than the one
surrounding the pair of parenthesis, don't remove paranthesis.
5) If high precedence operator is inside the pair of paranthesis than the
one surrounding the pair of parenthesis, remove paranthesis.


-Regards
Amit Agarwal
blog.amitagrwal.com



On Fri, Oct 8, 2010 at 11:42 AM, snehal jain  wrote:

> write a program to remove redundantt parenthesis from an expression
> eg
> input ((a+b))
>
> output  a+b
>
> input   a+(b*c)
>
> output  a+b*c
>
> inputa*(b+c)
> output   a*(b+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.
>
>

-- 
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: Google Question: Find kth largest of sum of elements in 2 array

[ligerdave]

@sourav


I think the best way to explain my logic is to draw a 2D matrix

   5  4  2  1
6
5
4
2

then you would find the patten. i have something draw on the paper. if
you need, i guess i can scan and send it out


On Oct 7, 10:05 am, sourav  wrote:
> @lingerdave
>
> If you get the larget element from the 2 arrays
> A -> 5, 4, 2, 1
> B -> 6, 5, 4, 2,
>
> say 6, do not underestimate the next element in A. The difference
> between the first two elements in A may be less and 2nd element in A
> may be string enough to make itself plus an element in B greater than
> first element in A plus kth element in B. More so if elements in B are
> very small after first few. for example see example
>
> A-> 100, 99,
> B-> 50,9,2,1,1
>
> Here A[i] + B[1} is largest but A[2]+B[1] is much larger than
> A[2]+B[2].
>
> Sourav
>
> On Oct 7, 6:22 pm, ligerdave  wrote:
>
>
>
> > @ Ercan,
>
> > yes, you were right. i forgot about that.
> > anyway, that's the idea. you would need to move pointers on both,
> > depends on which is bigger. for loop w/ i<=k, when the loop stops, you
> > have the pointers pointing at the numbers you wanted
>
> > On Oct 6, 7:16 pm, Gönenç Ercan  wrote:
>
> > > A -> 5, 4, 2, 1
> > > B -> 6, 5, 4, 2, 1
>
> > > k = 3,
>
> > > ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the
> > > algorithm below give 8 (a=2, b=6)?
>
> > > On Oct 6, 9:06 pm, ligerdave  wrote:
>
> > > > use pointers and lengths of two arrays. depends on what K is, if K>
> > > > m*n/2, you reverse the pointers. therefore, the worst case is either
> > > > O(m) when length of m is shorter or O(n) when length of n is
> > > > shorter,
>
> > > > make the pointers pointing to the first elements in both arrays.
>
> > > > A)
> > > > 4,3,2,2,1
> > > > ^
>
> > > > B)
> > > > 5,3,2,1
> > > > ^
>
> > > > compare them to find out which one is larger, here 5 is larger than 4.
> > > > by definition, you know 5 would be bigger than any elements in array
> > > > A, and sum of 5 with kth element of array A (here, kth <= A.length)
> > > > will be the one(kth largest sum(a+b) overall) you are looking for.
>
> > > > if k>A.length, shift the pointer of B one number to the right and
> > > > repeat the same process.
>
> > > > like i said, if the k> m*n/2, start from small
>
> > > > On Oct 6, 6:34 am, sourav  wrote:
>
> > > > > you are given 2 arrays sorted in decreasing order of size m and n
> > > > > respectively.
>
> > > > > Input: a number k <= m*n and >= 1
>
> > > > > Output: the kth largest sum(a+b) possible. where
> > > > > a (any element from array 1)
> > > > > b (any element from array 2)
>
> > > > > The Brute force approach will take O(n*n). can anyone find a better
> > > > > logic. thnkx 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.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: linked lists

[shashank jain]

there are 2 unsorted array we have to want a third array in sorted
form in mininmum time complexicity

answer can like be this merge the two array in 3rd array then sort the array

  or
sort the individual array and then merge

if feel first one is better

can any one can help


On 10/8/10, snehal jain  wrote:
> @ligerdave
> m nt getting ur algo..can u explain with an example
>
>
> On 10/8/10, snehal jain  wrote:
>>
>> @neeraj
>> ur worst case complexity will be O(mn)
>>
>>
>>  On 10/8/10, snehal jain  wrote:
>>>
>>> @tech
>>> the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with
>>> prefix of 2nd
>>>
>>>
>>>  On 10/7/10, ligerdave  wrote:

 use pointer. shift to left if one more leading char has been found.
 any unmatched char resets the pointer to first char

 once you went through the entire list(first one), the pointer on the
 second list tells you where to concatenate

 that gives you O(n) where n is the length of first list

 On Oct 7, 3:52 am, snehal jain  wrote:
 > There are two linked list, both containing a character in each node.
 >
 > If one linked list contain characters  o x e n c and second contain
 > characters e n c a r t a then the final linked list should contain o x
 > e n c a r t ai.e. if the end of one list is same as the start of
 > second then those characters should come only once.
 >
 > can we do it in O(n+m) where n and m are the length of list. both are
 > singly link list.

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

[Gene]

Here is code for inputs up to NMAX long.  With more fiddling, you
could easily get the storage requirement down to O(n).

#include 

#define NMAX 100

int min(int x, int y) { return x < y ? x : y; }

int best_score(int *notes, int n)
{
  int F[NMAX][NMAX], i, j, d;

  for (i = 0; i < n; i++)
F[i][i] = notes[i];
  // Compute the summations efficiently.
  for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
  F[i][j] = F[i][j - 1] + notes[j];
  // Complete the DP values
  for (d = 1; d < n; d++)
for (i = 0; i < n - d; i++) {
  j = i + d;
  F[i][j] -= min(F[i + 1][j], F[i][j - 1]);
}
  return F[0][n - 1];
}

int main(void)
{
  int notes[] = {2,5,7,1,8,9};
  printf("best is %d\n", best_score(notes, sizeof notes / sizeof
notes[0]));
  return 0;
}

On Oct 7, 11:43 pm, Gene  wrote:
> Nice problem.  Let N_1, N_2, ... N_n be the values of the N notes.
> Let F(i,j) be the maximum possible score the current player can get
> using only notes i through j.  Then
>
> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) )
>
> This is saying that the current player always makes the choice that
> minimizes B the best score that the other player can achieve.  When we
> know that choice, the best _we_ can do is the sum of all the available
> notes minus B.
>
> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j)
> where i > j.
>
> For example, suppose we have notes 3 7 2 1 .  The answer we want is
> F(1,4).
>
> Initially we have
> F(1,1) = 3
> F(2,2) = 7
> F(3,3) = 2
> F(4,4) = 1
>
> Now we can compute
> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7).
> F(2,3) =  9 - min(F(3,3), F(2,2)) =  9 - min(2,7) = 7 (pick N_2=7).
> F(3,4) =  3 - min(F(4,4), F(3,3)) =  3 - min(1,2) = 2 (pick N_3=2).
> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care).
> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7).
> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1).
>
> On Oct 7, 8:14 pm, Anand  wrote:
>
>
>
> > Given a row of notes (with specified values), two players play a game. At
> > each turn, any player can pick a note from any of the two ends. How will the
> > first player maximize his score? Both players will play optimally.- 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] Binary tree as threads and weights

[snehal jain]

If we consider the edges in binary tree as threads and nodes in the
tree as weights hanging from it(it is suspended from the root) then
how the tree structure will change when the tree is hung from a
particular leaf.

-- 
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] BiasedRandom fron unbiasedRandom.

[snehal jain]

Given a unbiased function that generates 0 and 1 with equal
probability write a function biasedrandom that genreates 0 with
probability p and 1 with probability 1-p.

-- 
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: linked lists

[snehal jain]

@ligerdave
m nt getting ur algo..can u explain with an example


On 10/8/10, snehal jain  wrote:
>
> @neeraj
> ur worst case complexity will be O(mn)
>
>
>  On 10/8/10, snehal jain  wrote:
>>
>> @tech
>> the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with
>> prefix of 2nd
>>
>>
>>  On 10/7/10, ligerdave  wrote:
>>>
>>> use pointer. shift to left if one more leading char has been found.
>>> any unmatched char resets the pointer to first char
>>>
>>> once you went through the entire list(first one), the pointer on the
>>> second list tells you where to concatenate
>>>
>>> that gives you O(n) where n is the length of first list
>>>
>>> On Oct 7, 3:52 am, snehal jain  wrote:
>>> > There are two linked list, both containing a character in each node.
>>> >
>>> > If one linked list contain characters  o x e n c and second contain
>>> > characters e n c a r t a then the final linked list should contain o x
>>> > e n c a r t ai.e. if the end of one list is same as the start of
>>> > second then those characters should come only once.
>>> >
>>> > can we do it in O(n+m) where n and m are the length of list. both are
>>> > singly link list.
>>>
>>> --
>>> 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: linked lists

[snehal jain]

@neeraj
ur worst case complexity will be O(mn)


On 10/8/10, snehal jain  wrote:
>
> @tech
> the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with
> prefix of 2nd
>
>
>  On 10/7/10, ligerdave  wrote:
>>
>> use pointer. shift to left if one more leading char has been found.
>> any unmatched char resets the pointer to first char
>>
>> once you went through the entire list(first one), the pointer on the
>> second list tells you where to concatenate
>>
>> that gives you O(n) where n is the length of first list
>>
>> On Oct 7, 3:52 am, snehal jain  wrote:
>> > There are two linked list, both containing a character in each node.
>> >
>> > If one linked list contain characters  o x e n c and second contain
>> > characters e n c a r t a then the final linked list should contain o x
>> > e n c a r t ai.e. if the end of one list is same as the start of
>> > second then those characters should come only once.
>> >
>> > can we do it in O(n+m) where n and m are the length of list. both are
>> > singly link list.
>>
>> --
>> 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: linked lists

[snehal jain]

@tech
the ouput will be abhgrtsghgrthswert as no suffix of 1st matches with prefix
of 2nd


On 10/7/10, ligerdave  wrote:
>
> use pointer. shift to left if one more leading char has been found.
> any unmatched char resets the pointer to first char
>
> once you went through the entire list(first one), the pointer on the
> second list tells you where to concatenate
>
> that gives you O(n) where n is the length of first list
>
> On Oct 7, 3:52 am, snehal jain  wrote:
> > There are two linked list, both containing a character in each node.
> >
> > If one linked list contain characters  o x e n c and second contain
> > characters e n c a r t a then the final linked list should contain o x
> > e n c a r t ai.e. if the end of one list is same as the start of
> > second then those characters should come only once.
> >
> > can we do it in O(n+m) where n and m are the length of list. both are
> > singly link list.
>
> --
> 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] double tower of hanoi

[snehal jain]

A Double Tower of Hanoi contains 2n disks of n different sizes, two of
each size. As usual, we’re required to move only one disk at a time,
without putting a larger one over a smaller one.
a. How many moves does it take to transfer a double tower from one
peg to another, if disks of equal size are indistinguishable from each
other?
b. What if we are required to reproduce the original top-to-bottom
order of all the equal-size disks in the final arrangement?

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