Re: [algogeeks] output

[Pramod Jayswal]

when swap is called ,as it is a macro ,before compilation its code is
replaced and the code before compilation bcomes:

> # define swap(a,b) temp=a; a=b; b=temp;
> main( )
> {
> int i, j, temp;
> i=5;
> j=10;
> temp=0;
> if( i > j)
>
   //code replaced here

> temp=a;   //not executed (false)
>
   a=b; //a=10(from b=10)
   b=temp;   //b=0 (from temp=0)

> printf( “%d %d %d”, i, j, temp);
> }
>
> and that is why u get output  10,0,0...
>
>

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

Re: [algogeeks] Immediate interview ASP.Net/Silverlight Developer -- NY

[Pramod Negi]

you guys going to get everone from this group only?

On Fri, Mar 11, 2011 at 12:11 AM, Sam Riley wrote:

> Dear Folks,
> Wishes for the Day !!!
> We Need consultant for ASP.Net/Silverlight Developer
> Please share suitable profiles to s...@panzersolutions.com
>
> *Job Title   :  ASP.Net/Silverlight Developer
> Location   :  NYC, NY
> Duration  :   6 Months
> Rate   :   Market
> Local NY/NJ/CT  Only *
>
> ASP.Net/Silverlight Developer Needed ASAP.
> --
> Thanks and Best Regards,
> Sam Riley | Sr Technical Recruiter
> Email: s...@panzersolutions.com
> Direct: 201-710-8278
>
> --
> 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 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.

Re: [algogeeks] Doubly linklist to Singly linklist...........

[Pramod Negi]

Search XoR List on Wiki

On Sun, Aug 8, 2010 at 10:19 AM, UMESH KUMAR wrote:

> how to convert Doubly Link list to a Singly link list without changes
> the Structure of the list if possible or not ,if possible then try to
> discus of that problem.
>
>
> thanks and Regards
> Umesh kumar
>
>  --
> 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: Find the duplicate

[Pramod Negi]

Already posted

compare pair wise i.e a[0] and a[1]a[2] and a[3]..
leave out last 4 elements...
repeated element can be found in 3 comparison for these 3 elements...

total no of comparison in worst case
(n/2+1)


Thanks
Pramod Negi

On Sat, Aug 7, 2010 at 7:14 PM, ankur bhardwaj  wrote:

> we can do one thing. compare first element with all others. if it matches
> with any of them, we have found our number, else leave the first number and
> now the required number is available (n/2)+1 times in the rest of the array,
> which can be found in 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.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 the duplicate

[Pramod Negi]

compare pair wise i.e a[0] and a[1]a[2] and a[3]..

leave out last 4 elements...

repeated element can be found in 3 comparison for these 3 elements...


total no of comparison in worst case
(n/2+1)

Negi

On Thu, Aug 5, 2010 at 10:55 PM, Shiv ...  wrote:

> In constant space??? How? will you please elaborate?
>
>
>
> On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal  wrote:
>
>> If I understand the question correctly... there is an array of size n
>> which has n/2 distinct elements and one element is repeated n/2 times.
>>
>> For e.g.:
>>n = 4:   1 2 3 3
>>n = 61 2 3 4 4 4
>>n = 81 2 3 4 5 5 5 5
>>
>> So now this problem can be reduced to finding the first duplicate element
>> in the array because remaining other elements will be unique. I think this
>> can be done in linear time.
>>
>>
>>  --
> 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] Permutation.................

[Pramod Negi]

http://pramnegi.blogspot.com/2009/11/dons-permutaion.html

Thanks
Pramod Negi

On Sun, Aug 1, 2010 at 4:30 PM, UMESH KUMAR wrote:

>  Write a C  code for generate all possible Permutation
>  as:- 1 2 3
> Total no. of Per=6
> also print all permutation
> as:- 1 2 3
>1 3 2
> 2 1 3
>2 3 1
>3 1 2
>   3 2 1
> if inpute is 1 2 3 2
>  total no of permutation = 12
>
>  --
> 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] number of BST's

[Pramod Negi]

Follow up on Catalon Nubmer...


On Fri, Jul 30, 2010 at 10:44 AM, Amit Jaspal wrote:

> n is clearly a number lets say 3 then BST's with 1,2,3 values as key are to
> be calculated
>
>
> On Fri, Jul 30, 2010 at 9:08 AM, Apoorve Mohan wrote:
>
>> @AMIT: what does "n" represents?
>>
>>
>> On Fri, Jul 30, 2010 at 5:46 AM, sharad kumar wrote:
>>
>>> @amit is it BST or binary tree??cos BST is unique rite???binary tree meas
>>> use catalan numbers 2nCn/(n+1)!
>>>
>>>
>>>
>>> On Thu, Jul 29, 2010 at 9:56 PM, amit  wrote:
>>>
 Given the numbers from 1 to n, write an algorithm to find how many
 distinct binary search trees can be formed.. eg n=4, no of distinct
 bst's are 14. ??

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


>>>
>>>
>>> --
>>> yezhu malai vaasa venkataramana Govinda Govinda
>>>
>>>  --
>>> 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.
>>>
>>
>>
>>
>> --
>> regards
>>
>> Apoorve Mohan
>>
>>  --
>> 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.
>>
>
>
>
> --
> Amit Jaspal
> Btech 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.
>

-- 
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 0's 1's and 2's

[Pramod Negi]

3 pointers

temp0 = first non 0 from start
temp2 = first non 2 from end

temp1 = temp0

loop till temp1 < temp2

if temp1 ==0
 swap a[temp1] a[temp0]
 temp0++
if temp1 == 2
 swap a[temp1] a[temp2]
temp2--
if temp1==1
temp1++

end

On Fri, Jul 2, 2010 at 8:16 AM, Gene  wrote:

> On Jul 1, 4:04 pm, jalaj jaiswal  wrote:
> > i was talking about the space complexity.. running time is obvs O(n)
>
> Hello J.J.
>
> Why would those 3 lines of executable code you cited say anything
> about space complexity?  They don't allocate memory.  You must be
> quibbling.
>
> There's no issue with space either.  Whatever space the lookup table
> takes is O(M) where M is the number of distinct symbols.  But if you
> didn't have the table, you'd need a chain of "if"s or a switch (as the
> other posted solutions use), which compile to code that's O(M) in
> size.  It's a wash.
>
> Finally, if the number of symbols M were large, you could use a O(1)
> time lookup scheme like a perfect hash to avoid the O(M) factor of
> runtime for the linear lookup.
>
> Cheers.
>
> > On Thu, Jul 1, 2010 at 9:14 PM, Gene  wrote:
> > > On Jun 30, 3:38 am, Debajyoti Sarma  wrote:
> > > > @Gene
> > > > your code's last 3 line gives doubt.
> > > >  ...
> > > >  for (i = j = 0; j < M; j++)
> > > >while (c[j]--)
> > > >  a[i++] = j;
> > > > ...
> > > > Is it don't make the complexity more than O(n) ??
> >
> > > Not at all. The inner loop body executes n times no matter what the
> > > value of M is.
> >
> > > Guys, this is just a special case of counting sort.  Obviously 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.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.
>
>

-- 
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] 2_D matrix

[Pramod Negi]

Young's Tableau.. go along non-major diagonal in a stair up or down fashion


On Fri, Jul 2, 2010 at 11:46 PM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:

> @Rahul: the worst case running time for your algo is O(nlogn)
>
> but here's another approach:
> suppose we're searching for x
> binary search on the diameter of the matrix (note that the diameter is
> sorted)
> if x is not on the diameter
> when you find i such that a[i][i] split the matrix to four matrices
>
> -
> | R1  |  R2  |
> |-
> | R3  |  R4  |
> -
>
> x cannot be in R1 since it's biggest element is a[i][i] which is less than
> x
> and it can't be in R4 since it's least element is a[i+1][i+1] which is
> bigger than x
> so we search recursively in R3 and R2
> in avg case since the avg size of R3 and R2 is n/2 * n/2
> T(n) = 2T(n/2) + O(lgn)
> using the master method the running time is 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.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: rotation

[Pramod Negi]

I guess you want the following juggling algorithm
http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf


On Fri, Jul 2, 2010 at 11:16 PM, Dave  wrote:

> @Jalaj. The original poster said, "P.S---do not give block reversal
> method for array rotation "
>
> Dave
>
> On Jul 2, 10:54 am, jalaj jaiswal  wrote:
> > reverse full array first
> > then, reverse last k elemnts and initial n-k elements seperately
> > this will do
> > On Fri, Jul 2, 2010 at 8:34 PM, Ratnesh Thakur <
> ratneshthaku...@gmail.com>wrote:
> >
> >
> >
> >
> >
> > > correction..
> > > a[j]=a[j-1] instead of a[i]=a[i-1]
> >
> > > On Fri, Jul 2, 2010 at 7:30 PM, Ratnesh Thakur <
> ratneshthaku...@gmail.com>wrote:
> >
> > >> i think this should work.
> >
> > >> for(i=1;i<=k;i++)
> > >> {
> > >> var=a[n-1]
> > >> for(j=n-1;j>=1;j--)
> > >> a[i]=a[i-1]
> > >> a[0]=var
> >
> > >> }
> >
> > >> On Fri, Jul 2, 2010 at 5:36 PM, Saurabh Ahuja  >wrote:
> >
> > >>> a[0] = a[2]
> > >>> a[1] = a[3]
> > >>> a[2] = a[4]
> >
> > >>> a[0] and a[1] has been changed
> > >>> a[3] = a[0]
> > >>> a[4] = a[1]
> >
> > >>> so this solution would not work.
> >
> > >>> On Fri, Jul 2, 2010 at 5:14 PM, Akash Gangil  >wrote:
> >
> >  wouldn't this work:
> >
> >  for i in range(0,len)
> >  a[i] = a[(i+2)%5];
> >
> >  where len is the length of array
> >
> >  On Sat, Jun 26, 2010 at 3:37 PM, sharad kumar <
> sharad20073...@gmail.com
> >  > wrote:
> >
> > > i have to right rotate an array by k positions
> > > 1 2 3 4 5 for k=2 o/p shud be
> > > 3 4 5 1 2
> >
> > > P.S---do not give block reversal method for array rotation and soln
> > > must be inplace.plzz write ur logic also along with d code
> >
> > > --
> > > 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.
> >
> >  --
> >  Best Regards
> >  Akash Gangil
> >
> >    --
> >  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.
> >
> > --
> > With Regards,
> > Jalaj Jaiswal
> > +919026283397
> > B.TECH IT
> > IIIT ALLAHABAD- 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] amazon question

[Pramod Negi]

if it means storing it in a file, store at 2i and 2i+1 location and NULL if
some child doesn't exists

On Sat, Jul 3, 2010 at 7:42 PM, ashish agarwal  wrote:

> We can do 4 type of treversal.
> If we do inorder then we will get sorted array .If we do an inorder
> traversal then we would get a sorted list which if we convert into a BST
> would again become a list and we would loose out on the original structure
> of the tree.
>
> and same will be happen with post order
> now remaining preorder and level order.
> when we do level order traversal it will require more space as it uses BFS
> approach .So to do in o(logn) we do preorder travesal.
>
>
> On Sat, Jul 3, 2010 at 5:46 AM, jalaj jaiswal 
> wrote:
>
>> serialize... is it level order traversal ???
>> give an example...?
>>
>>
>> On Sat, Jul 3, 2010 at 12:36 PM, divya  wrote:
>>
>>> Design an algorithm and write code to serialize a binary tree.
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> 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.
>>
>
>  --
> 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] array

[Pramod Negi]

Median Can be found out in O(n) times (kth order statistic)


On Sat, Jul 3, 2010 at 4:46 PM, Akash Gangil  wrote:

> Hi Amir
>
> On Fri, Jul 2, 2010 at 10:13 PM, Amir hossein Shahriari <
> amir.hossein.shahri...@gmail.com> wrote:
>
>> both problems can be done in O(n)
>> pick the first two elements count the number of their appearances in the
>> array ( O(n) )
>> if they are not the result we now that there is an element that is
>> repeated n times in 2n-1 elements and we can do the moore's algorithm for
>> finding it here's a link to this algorithm:
>> userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
>>
>> I didnt understand the algo correctly what is the sequence is
>
>
> C C C C C A A B B A B
>
> now the last current candidate is B 1
> but B is certainly not in majority. Can you please explain that to me?
>
>
>
>
>> --
>> 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.
>>
>
>
>
> --
> Best Regards
> Akash Gangil
>
>
>  --
> 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: ds

[Pramod Negi]

Hello All,

What every algorithm mentioned above have some problem.



The Recursive swapping won’t work if you don’t have 2^n elements.

Same with getting the indexes, it will form a cycle.



Thanks

Pramod Negi




On Fri, Jun 11, 2010 at 7:09 PM, sharad kumar wrote:

> excellent soln!!
>
> --
> 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: bits

[Pramod Negi]

>From last few days I'm seeing the question that is coming here is not
algorithm specific.
Purpose of this group is achieved or defeated???


Thanks
Pramod Negi

On Sun, Jun 13, 2010 at 9:48 PM, jalaj jaiswal wrote:

> hey i too have a doubt... and its just 1 ... i'll not ask c/c++ again,,,
>
> we have a union a{
>int i;
>char ch[4];
> }
> int here is of 4 bytes.
> i initialise i=512...
> what value will ch[0] get the upper 8 bits or the lower 8 bits... is it big
> endian or little endian dependent... please explain this ??
>
>
> On Sun, Jun 13, 2010 at 9:43 PM, Rohit Saraf 
> wrote:
>
>> I agree mass bombarding with such questions is not very good.. but one
>> doesn't join groups and all for getting a few doubts cleared.
>> Anyways, i have no problem with anything. :D
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>>
>>
>> On Sun, Jun 13, 2010 at 9:26 PM, souravsain  wrote:
>>
>>> and @rohit you will get better insight into the topic by more expert
>>> people by posting the question in right forum. I guess thats a win-win
>>> situation for one who has the question as he is get to know more and
>>> for people you are interested in going through C++ questions as they
>>> will read views from many more experts :)
>>>
>>> On Jun 13, 7:31 pm, Rohit Saraf  wrote:
>>> > @Souravsain : Is there any serious problem in this. Anyone can just add
>>> a
>>> > [C++] in the subject and uninterested people can make filters in gmail
>>> :)
>>> >
>>> > --
>>> > Rohit Saraf
>>> > Second Year Undergraduate,
>>> > Dept. of Computer Science and Engineering
>>> > IIT 
>>> > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>>> >
>>> >
>>> >
>>> > On Sun, Jun 13, 2010 at 6:35 PM, souravsain 
>>> wrote:
>>> > > @divya
>>> >
>>> > > Lets keep discussions in t his group limited to Algos and problems
>>> > > neutral to any language.
>>> >
>>> > > Request you to post these C++ / C language specific questions to
>>> those
>>> > > language specific groups. This will not only help this group remain
>>> > > confined to its core purpose but will help you get better insights to
>>> > > ur problem by language specific geeks there. For C++ I would
>>> recommend
>>> > > you to try the group
>>> > >http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en
>>> .
>>> >
>>> > > Regards,
>>> > > Sourav
>>> >
>>> > > On Jun 13, 2:29 pm, divya  wrote:
>>> > > > tell the o/p of following with explanations
>>> >
>>> > > > 1. #include
>>> > > > int main()
>>> > > > {
>>> > > >   struct value
>>> > > > {
>>> > > > int bit1:1;
>>> > > > int bit3:4;
>>> > > > int bit4:4;
>>> >
>>> > > > }bit;
>>> >
>>> > > > printf("%d\n",sizeof(bit));
>>> > > > return 0;
>>> >
>>> > > > }
>>> >
>>> > > > 2.
>>> > > > #include
>>> > > > int main()
>>> > > > {
>>> > > > struct value
>>> > > > {
>>> > > > int bit1: 1;
>>> > > > int bit3: 4;
>>> > > > int bit4: 4;} bit={1,2,2};
>>> >
>>> > > > printf("%d %d %d\n",bit.bit1,bit.bit3,bit.bit4);
>>> > > > return 0;
>>> >
>>> > > > }
>>> >
>>> > > > 3 can bit field be used in union??
>>> >
>>> > > --
>>> > > 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
>>> 

Re: [algogeeks] Where does OS scheduling run??

[Pramod Negi]

Hello,



There exists differnet google groups for OS related queries. Could you
please move out your discussion there.



Thanks

Pramod Negi


On Thu, May 6, 2010 at 5:34 AM, Yalla Sridhar  wrote:

> yea if your processor has multiple cores or is Hyper Threading support then
> it can execute more than 1 instruction concurrently.
>
>
> On Thu, May 6, 2010 at 12:10 AM, praba garan wrote:
>
>> Windows Task Manager Performance tab shows the presence of two processors.
>> Will 2 instructions be executed concurrently??
>>
>> With Regards,
>> Prabagaran.
>>
>>
>>
>> On Wed, May 5, 2010 at 4:56 PM, Varun Nagpal wrote:
>>
>>> I guess with Virtual machines, instructions that simulate instructions
>>> of microprocessor are scheduled onto the real processor. But good
>>> question is how the scheduling of real microprocessor instructions
>>> done in a virtual machine. And the answer is again that its done on
>>> virtual processor, which essentially has all hardware components of
>>> real processor modeled in software. All sub-parts of this software
>>> representing essential hardware components, again run synchronously
>>> (in parallel) either at instruction accurate level or cycle accurate
>>> level.
>>>
>>> All new processor that are designed as of today, are first mostly are
>>> verified using simulators written in hardware description languages
>>> like VHDL/SystemVerilog/SystemC and then simulated either in software
>>> or hardware. For hardware simulation, in some cases its eventually
>>> possible to create them on FPGA's and verify before they are sent to
>>> fab lab. Its an arduous task.
>>> For example, you can get HDL code for free for SUN Open Sparc
>>> processor and can flash it on FPGA.
>>>
>>> So It doesn't really matter whether your processor is real or virtual,
>>> so you need to understand architecture principles and some digital
>>> electronics to  understand at hardware(VLSI ) level
>>>
>>> Intel x86 and now x64 are the most popular architectures. Other
>>> popular architectures are ARM, MIPS, SPARC, PowerPC, etc.
>>> You should probably read  the book: Computer Architecture, by hennrey
>>> Peterson
>>>
>>>
>>> On Tue, May 4, 2010 at 10:49 PM, praba garan 
>>> wrote:
>>> > I think it is necessary to study the full architecture of INTEL
>>> MotherBoard
>>> > to get a full picture.
>>> > How does scheduling happen incase of Virtual Machines??
>>> > Then how does a packet coming to the Guest OS is sent to Guest OS.
>>> > ie, either directly to Guest OS or through Host OS.
>>> > With Regards,
>>> > Prabagaran.
>>> >
>>> >
>>> > On Mon, May 3, 2010 at 12:25 PM, Varun Nagpal >> >
>>> > wrote:
>>> >>
>>> >> I think its a good question and fairly complicated to explain at
>>> >> hardware(RTL) level. Anyways, let me give it a try :
>>> >>
>>> >> You suggested that only 1 instruction is executed by one processor,
>>> >> which is not true(if you have read computer architecture). Briefly,
>>> >> lets assume the instruction pipeline(assuming only single hardware
>>> >> thread) is filled with instructions from the present thread(or
>>> >> process) of execution. Assume number of pipeline stages to be 20. In
>>> >> the pipeline, 20 instructions from the current instruction control
>>> >> flow are executing synchronously on every clock tick. Depending upon
>>> >> the design of pipeline, data from registers/memory is read in
>>> >> different pipeline stages. Also there may also be many execution
>>> >> stages(ALU) before the data is written to register/memory.
>>> >>
>>> >> The OS kernel keeps a track of all the threads/processes presently
>>> >> executing, active, waiting, suspended etc. in memory in the form of a
>>> >> data structure, which is to say that it always knows the next
>>> >> thread/process it needs to schedule on to the processor. I think it
>>> >> has a compare register that stores an arbitrary number(as decided by
>>> >> kernel) of clock ticks for a time slice expiry and keeps another
>>> >> counter register to keep track of time slice expiration for present
>>> >> thread. At every clock tick, it increments the counter register and
>>> &

Re: [algogeeks] Why is inorder traversal necessary to reconstruct a binary tree?

[Pramod Negi]

why only Preorder and Postorder is not suffice.
consider Two Binary Tree

Root = A
Left Chid = B

Preorder: A,B
Postorder: B,A

and
Root = A
Right Child = B

Preorder: ,A,B
Postorder: B,A


for given preorder and postorder two different binary trees can be formed

Thanks
Pramod Negi


On Thu, Apr 8, 2010 at 10:53 PM, Himanshu Aggarwal
wrote:

> For a binary tree , if we are given an inorder traversal and a
> preorder/postorder/level-order traversal, we can always reconstruct back the
> binary tree. This technique can be used to save and restore the binary tree
> efficiently.
>
> I have read that it is necessary to have an inorder traversal to
> reconstruct the tree. i.e. if we are given a preorder and a postorder
> traversal, the binary tree can not be reconstructed.
>
> Can someone help me in understanding why this is so? i.e. why is inorder
> traversal a mandatory requirement. Why can not we reconstruct the tree with
> a given preorder and a postorder
>
> Thanks to everyone for their suggestions and replies.
>
> ~Himanshu 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.
>

-- 
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] Finding youngest common ancestor of two nodes in a binary tree

[Pramod Negi]

could you please elucidate more??

On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal
wrote:

> For a given binary tree, given the root and two node pointers, how can we
> find their youngest common ancestor.
>
> Say the node is like:
>
> struct node{
>int data;
>struct node*left, *right;
> };
>
> i.e the father field is not there.
>
> Please note that it is not a binary search tree, but just a binary tree.
>
> Thanks,
> Himanshu
>
> --
> 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] Convert a BST into sorted doubly linked list...

[Pramod Negi]

This is the best description.

http://cslibrary.stanford.edu/109/TreeListRecursion.html

Thanks
Pramod Negi


On Sun, Mar 28, 2010 at 1:39 PM, Piyush Verma <114piy...@gmail.com> wrote:

> How can we convert a BST into a sorted doubly linked list?
>  i have the solution that i traverse BST in inorder traversal and
> storing elements in doubly linked list.
> anyone has any best solution.
>
> --
> Piyush Kumar Verma
> NIT 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.
>

-- 
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 span of Increasing Pair in an array

[Pramod Negi]

Hello Saurabh,

can you explain the algo??

On Sun, Mar 14, 2010 at 9:55 PM, saurabh gupta  wrote:

> O(N)
>
> my @a = @ARGV;
> my ($m, $j, $k, $l) = (0, 0, 0, 0);
> my $len = 0;
> my $curr = 0;
> for (my $i = 1; $i < @a; $i++) {
> if ($a[$i] >= $a[$i-1]) {
> if ($m == $k) {
> $j++;
> $l++;
> $curr++;
> $len++;
> }
> else {
> $l++;
> $curr++;
> }
> }
> else {
> if ($curr > $len) {
> $m = $k;
> $j = $l;
> $len = $curr;
> }
> $k = $l = $i;
> $curr = 0;
> }
> }
> if ($curr > $len) {
> print "$k  $l";
> }
> else {
> print "$m $j";
>
> }
>
>
> On Sun, Mar 14, 2010 at 8:49 PM, Ralph Boland  wrote:
>
>>
>> On Mar 14, 7:46 am, ASHISH MISHRA  wrote:
>> > @ankur how u can solve it in o(n)
>> > i suppose u need atleast o(n lgn)
>> >
>> > On Sun, Sep 6, 2009 at 2:52 PM, ankur aggarwal <
>> ankur.mast@gmail.com>wrote:
>> >
>> > > o(n) is the best sol known to me..
>> >
>> > > On Sun, Sep 6, 2009 at 1:54 PM, Pramod Negi 
>> wrote:
>> >
>> > >> i guess sorting will do the work.
>> > >> any other constraint??
>> >
>> > >> On Sun, Sep 6, 2009 at 9:52 AM, p0r$h <1987.shis...@gmail.com>
>> wrote:
>> >
>> > >>> Given an array of integers A[N], find the maximum value of (j-k)
>> such
>> > >>> that A[k] <= A[j] & j>k.
>> > >>> I am looking for a solution with time complexity better than O(N^2).
>> >
>>
>> I don't know how to solve this in the claimed  O(N) time.
>> However, I have coded a data structure that,
>> given  j,  will find  k  in  O(log(N))  time.
>> With it you can solve your problem in  O(N log N) time.
>> The data structure is built in  O(N)  time and space.
>> It is part of a larger data structure that I will implement
>> and release as open source in a few months.
>>
>> Regards,
>>
>> Ralph Boland
>>
>> --
>> 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.
>>
>>
>
>
> --
> Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
> Says he feels all alone in a threatening world where what lies ahead is
> vague and uncertain. Doctor says "Treatment is simple. Great clown
> Pagliacci is in town tonight. Go and see him. That should pick you up." Man
> bursts into tears. Says "But, doctor...I am Pagliacci."
>
>  --
> 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: second highest elemt in an aary

[Pramod Negi]

It won't
try with [1,3,2]

On Mon, Sep 28, 2009 at 11:56 AM, harit agarwal wrote:

> It will take n comparisons.observe this code
>
>
> #include
> using namespace std;
> int sec_largest(int ar[],int n)
> {
> int i,max=-32767,sec_max=0;
> for(i=0;i {
> if(ar[i]>max)
> {
> sec_max=max;
> max=ar[i];
> }
> }
> return sec_max;
> }
> main()
> {
> int n,i,res;
> cout<<"enter number of elements\n";
> cin>>n;
> int ar[n];
> for(i=0;i cin>>ar[i];
> res=sec_largest(ar,n);
> cout<<"second largest number="<
> }
>
>
> >
>

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

[algogeeks] Re: second highest elemt in an aary

[Pramod Negi]

This will,I guss take 3N/2 comparison, for N + Lg -2.
Find Max(Winner) in N-1 (Tournament Method)
Compare Looser(fron Winner) For every Round with The Looser(from Winner) of
previous round..

_Negi


highest2=a[1];
> for(i=1;i<5;i++)
>  {
>  if( a[i] > highest1)
>  {
>  highest2 = highest1;
>  highest1 = a[i];
>  flag++;
>  }
>  else if( a[i] > highest2 )
>  {
>  highest2 = a[i];
>  flag++;
>  }
>  else
>  flag++;
> }
>
> if( !flag )
>  highest2 = highest1;
>
> printf("%d",highest2);
> }
>
> >
>

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

[algogeeks] Re: Largest span of Increasing Pair in an array

[Pramod Negi]

i guess sorting will do the work.
any other constraint??

On Sun, Sep 6, 2009 at 9:52 AM, p0r$h <1987.shis...@gmail.com> wrote:

>
> Given an array of integers A[N], find the maximum value of (j-k) such
> that A[k] <= A[j] & j>k.
> I am looking for a solution with time complexity better than O(N^2).
>
> >
>

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

[algogeeks] Re: swap every two bits in the byte..

[Pramod Negi]

i guess
num = ((num&0xAA)>>1) | ((num&0x55)<<1))
will work

Negi

On Sat, Sep 5, 2009 at 2:08 PM, Gokul  wrote:

>
> how ll u swap every two bits in the a byte??? can anyone help me???
> for eg.
> consider a byte as input...
> 10111010
>
> output should be
> 01110101
>
> it exactly swap the two bits(no complement is takesplace here)..
>
> >
>

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

[algogeeks] Re: Find an element in sorted matrix

[Pramod Negi]

I guess it is famous "Younge Tableau" Problem of tableau MxN and searching
can be done in O(M+N).
I doubt the problem can be solved in O(lgn) if no space constraint and no
pre-processing constraint present.

On Thu, Aug 20, 2009 at 9:42 PM, Anil C R  wrote:

> A more general problem is discussed in "Introduction to Algorithms" by
> Cormen et al
> problem 6-3, although the running time is O(n)...
> nagendra kumar wrote:
> > How can we find an element in the matrix [n*n] which is sorted row
> > wise and column wise in O(log n).
> >
> > >
> >
> >
>
>
> >
>

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

[algogeeks] Re: bits required to convert A to B

[Pramod Negi]

i guess XORing A and B and count the no of set bits will do.

On Sun, Aug 16, 2009 at 11:09 PM, richa gupta  wrote:

>
> Given two integers A & B. Determine how many bits required to convert
> A to B.how to write a function int BitSwapReqd(int A, int B);
>
> --
> Richa Gupta
> (IT-BHU,India)
>
> >
>

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

[algogeeks] Re: exact solution to this recursion equation

[pramod]

It seems T(n) = 4/3*n^2.
You can verify this by substitution.

On Apr 1, 2:42 am, Arunachalam  wrote:
> What is the base value of this recursion? Without a base value the recursion
> is not solvable?
>
> There should be some base value like T(x) = 1 where x <= 1.
>
> regards,
> Arun.
>
>
>
> On Mon, Mar 30, 2009 at 12:35 AM, nikoo  wrote:
>
> > Hello everybody
>
> > I need the solution to the following recursion equation
>
> > T(n) = 2 T (n/2) - 4 T (n/4) + n^2
>
> > does anybody know how to solve this equation?
> > I appreciate any help
>
> > thanks
> > nikoo
>
> --
> ===
> want to know more about me
> http"//ww.livejournal.com/users/arunachalam
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

[algogeeks] Re: splay tree

[Pramod Negi]

provide some good pointer to me also

On Wed, Oct 1, 2008 at 8:40 PM, Nuda LU <[EMAIL PROTECTED]> wrote:

> any one familiar with splay tree? I am kind of confused why bother to have
> such complicated step like zig-zig, zag-zag, zig-zag or zag-zig to have the
> Amortized time 3 log{W/w(i)}+ 1. In my opinion, the zig-zig is made of two
> steps of zig, zag is made of two steps of zag. Is it the same amortized time
> if I replace the zig-zig with two zig? Hope anyone can help.
>
> >
>

--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Enumerating trees

[pramod]

Geoff,

How did you arrive at the V(V+1)/2 figure?

On May 15, 1:21 am, Geoffrey Summerhayes <[EMAIL PROTECTED]> wrote:
> On May 14, 12:41 pm, "Bruno Avila" <[EMAIL PROTECTED]> wrote:
>
> > (reformatting last email)
>
> > These are good questions. In my problem, a binary tree is different if
> > the set of nodes are different. For example:
>
> >  a We have 9 different binary trees: {a}, {b}, {c},
> >   \ {a,b}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}. It does
> >   b not matter the number of different binary trees
> >  /  \   that can be formed by each of these sets. The
> > d - c set {b,c,d} can not be considered because it would
> > for a cycle, so it would not be a tree.
>
> > My initial question was not well specified. Sorry.
>
> That's an unusual set of conditions for a subgraph.
>
> Ok, that would make the minimum  V(V+1)/2, which
> would be exact for a linear graph a-b-c-d-... as well as any
> complete one (more than two nodes automatically have a
> cycle).
>
> Maximum might be a ring structure, that would be V*(V-1)
> when V>=3. No guarantee on that one though.
>
> ---
> Geoff
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Enumerating trees

[pramod]

Let's say we have E number of edges and V number of vertices.
Any subgraph which is a tree with V vertices will have V-1 edges. So
we need to retain V-1 edges and eliminate the rest E-(V-1). So in a
brute force manner if we retain any set of V-1 edges and see if the
resultant graph is indeed a tree or not. So we need to test for E C
(V-1) such cases. This is definitely an upper bound.
We may optimize the above exponential algorithm by not considering
those edges which are not part of any cycles since they can't be
removed. And in the middle of removing the edges if we encounter an
edge with vertex having a degree of only 1 then we can't remove that
edge.

On May 13, 10:51 pm, "Bruno Avila" <[EMAIL PROTECTED]> wrote:
> Yes, you're right. It depends on the topology of the graph. Do you
> have any references for the upper or lower bound? Or even an
> asymptotic of form O(2^k)?
>
> Bruno
>
> On Tue, May 13, 2008 at 12:28 PM, Geoffrey Summerhayes
>
> <[EMAIL PROTECTED]> wrote:
>
> >  On May 12, 8:20 pm, brunotavila <[EMAIL PROTECTED]> wrote:
> >  > Hi people,
>
> >  > How to calculate the number of binary trees that are subgraphs of a
> >  > given connected, undirected, unweighted and simple (no parallel edges
> >  > nor loops) graph?
>
> >  Haven't given it too much thought, but I believe the number is
> >  dependant on the actual topology of the graph. It should be possible
> >  to calculate an upper and lower bound, but for an accurate number for
> >  a given graph I think you're stuck with counting them.
>
> >  ---
> >  Geoff
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: selection problem.....

[Pramod Negi]

make a partition about media as a pivot element

On 4/22/08, Varun S V <[EMAIL PROTECTED]> wrote:
>
> Hi Dave,
>
> Can you kindly eloborate your algorithm?
> How can we modify a single array in O(n) time, such that the median comes
> to become the n/2th element and smaller elements comes to the left side and
> larger elements comes to the right side? Kindly explain in detail.
>
> 2008/4/22 Pramod Negi <[EMAIL PROTECTED]>:
>
> > i didnt get what u want to so say (the bold lines)
> >
> >  On 4/21/08, Dave <[EMAIL PROTECTED]> wrote:
> >
> > >
> > > Use a divide-and-conquer algorithm to find the median, rearranging the
> > > array so that the values less than the median precede it in the array
> > > and the values greater than the median follow it. So the median is
> > > a(n/
> > > 2).* Now use the divide-and-conquer algorithm twice more to locate the
> > > (n/2-k)th and (n/2+k)th elements*. Finally, march out both directions
> > > from n/2, selecting the closest elements to a(n/2). Each of these
> > > operations can be done in O(n), so the total algorithm is O(n).
> > >
> > > Dave
> > >
> > > On Apr 21, 9:35 am, Algo <[EMAIL PROTECTED]> wrote:
> > > > hi this is prob 9-3.7 of CLRS , anybody having a clue???
> > > >
> > > > Describe an O(n)-time algorithm that, given a set S of n distinct
> > > > numbers and a positive
> > > > integer k ≤ n, determines the k numbers in S that are closest to the
> > > > median of S
> > > >
> > > > 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: selection problem.....

[Pramod Negi]

i didnt get what u want to so say (the bold lines)

On 4/21/08, Dave <[EMAIL PROTECTED]> wrote:
>
>
> Use a divide-and-conquer algorithm to find the median, rearranging the
> array so that the values less than the median precede it in the array
> and the values greater than the median follow it. So the median is a(n/
> 2).* Now use the divide-and-conquer algorithm twice more to locate the
> (n/2-k)th and (n/2+k)th elements*. Finally, march out both directions
> from n/2, selecting the closest elements to a(n/2). Each of these
> operations can be done in O(n), so the total algorithm is O(n).
>
> Dave
>
> On Apr 21, 9:35 am, Algo <[EMAIL PROTECTED]> wrote:
> > hi this is prob 9-3.7 of CLRS , anybody having a clue???
> >
> > Describe an O(n)-time algorithm that, given a set S of n distinct
> > numbers and a positive
> > integer k ≤ n, determines the k numbers in S that are closest to the
> > median of S
> >
> > 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Discussion on unique-elements-in-an-array

[Pramod Negi]

i think if array of n elements is given and to make a heap out of it we need
O(n) space.
heap sort will surely take constant amount of auxially space if heap is
already build.

isn't it?
correct me if i m wrong..

On 11/9/07, Andrey <[EMAIL PROTECTED]> wrote:
>
>
> Heapsort http://en.wikipedia.org/wiki/Heapsort#Comparison_with_other_sorts
>
> On Nov 9, 3:54 pm, "Pramod Negi" <[EMAIL PROTECTED]> wrote:
> > which algo sort array in O(N lgN) without extra space??
> >
> > On 11/6/07, Andrey <[EMAIL PROTECTED]> wrote:
> >
> >
> >
> > > dor is absolutely right
> >
> > > > O(N*log(N)) is straightforward.. sort the array in O(N*log(N)) and
> > > > then remove duplicates in linear time.
> >
> > > it doesn't need any extra memory.
>
>
> >
>

--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Discussion on unique-elements-in-an-array

[Pramod Negi]

which algo sort array in O(N lgN) without extra space??

On 11/6/07, Andrey <[EMAIL PROTECTED]> wrote:
>
>
> dor is absolutely right
>
> > O(N*log(N)) is straightforward.. sort the array in O(N*log(N)) and
> > then remove duplicates in linear time.
>
> it doesn't need any extra memory.
>
>
> >
>

--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Removing a set of characters from a given string

[Pramod Negi]

Use bit array rather using array of size 26

On 9/15/07, Deva R <[EMAIL PROTECTED]> wrote:
>
>
>
> a linear solution.
>
> - initialize an array of 26 (count for each character) with zeros.
> - scan pattern array and toggle equivalent alphabet's occurance field
> - scan subject string and skip occured alphabets
>
> sample program:
>
>
> alphabets_occurance[26]={0,0,0,...}
>
> void fun(char *subject,char *pattern)
> {
>
> //toggle dirty alphabets occured in pattern string
>for(int i =0;subject[i] !='\0';i++)
>{
>  alphabets_occurance[subject[i] - 'a'] = 1;
>}
>
>//have two indexs to traverse the subject array and skip dirty
> alphabets
>int curr_count=0,forward_count=0;
>for(int i =0;pattern[i]!='\0';i++)
>{
>  if(alphabets_occurance[pattern[forward_count] - 'a'] !=1)
>  {
> //not a dirty alphabet - include in output
> pattern[curr_count]=pattern[forward_count];
> curr_count++;
>  }
>  forward_count++;
>}
>   //terminate output string
>   pattern[curr_count]='\0';
> }
>
>
> costs time at  o(strlen(pattern)+strlen(subject)) and mem 26 bytes..
>
>
>
> On 8/12/07, Peeyush Bishnoi <[EMAIL PROTECTED]> wrote:
> >
> > One solution to this problem is that :
> >
> > char s[]="abracadbra";
> > char p[]="bca";
> > char temp[];
> >
> > 1. First Remove element b of array p from array s .
> >   Compare b of array p with with characters of array s .
> >   if b is not matched with characters of array s
> >  insert those characters of s into new temp array .
> >  continue this till s reaches '\0';
> >now again reassign the reduced characters of temp array back into
> > array s;
> >
> > continuously repeat the step 1 for another characters in p till p become
> > or reaches '\0' ;
> >
> > finally you have an array which doesn't have characters which are there
> > in p array;
> >
> >
> > I think it only need an extra temporary array , but at each interation
> > array size is getting reduced & as well no. of time to compare elements is
> > also get reduced .
> >
> > If any one have questions please ask;
> >
> > Thank you ,
> >
> > ---
> > Regards
> > Peeyush Bishnoi
> >
> > On 8/7/07, Arulanandan P < [EMAIL PROTECTED]> wrote:
> > >
> > > You have to write a function whose prototype is given bellow. this
> > > function will accept two char * named subject and pattern. for example
> > > subject="abracadbra"
> > > and pattern="bca".now it should check occurrences of all chars of
> > > string pattern in subject . If any match occurs then it will remove that
> > > char from subject . so finally , as in our example
> > > at end subject ="rdr"
> > >
> > > void fun(char *subject,char *pattern)
> > > {
> > > // write your code here
> > > }
> > >
> > >
> > >
> >
> >
> > --
> > 
> > Peeyush Bishnoi
> >
> >
> >
>
> >
>

--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: fatest algorithm to find suqre root of a big number of 1000 didgits

[Pramod Bhatotia]

How about using newton raphson method ?

On 8/10/07, Alfredo Cruz <[EMAIL PROTECTED]> wrote:
>
>
> pradeep reguri wrote:
> > hi friends can any one help in finding square root of a big algebraic
> > number of 1000 digits
> >
> > >
> >
> >
> I think that maybe Newton method could help you... But if you want to
> see serious Numerical Analysis algorithms and their implementation you
> should
> check SciLab's sources trying to figure out how they calculate square
> roots... If their method is not the fastest it is one of them...
> http://www.scilab.org
>
> Good Luck
>
> Alfredo Cruz
>
> >
>


-- 
"Go Bears!"

--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: what is total number of permutation

[pramod]

Mike,

At least for me, I am interested in knowing how you arrived at that.
Can you elaborate more on this? Is this catalan number?


On Jul 19, 2:15 am, Mike <[EMAIL PROTECTED]> wrote:
> Hi Rupesh,
>
> Despite the fact that the answer may not help you, my colleagues and I
> worked on this problem today.  The closed-form solution for two lists
> of size n is as follows:
>
> The number of possible permutations, following your original
> instructions, are:
>
> P(n) = (2*n)! / (n!)^2 - (2*n)! / [(n-2)!*(n+2)!] = (2*n)nCr(n) -
> (2*n)nCr(n-2)
>
> In practice, this number gets very large very quickly.  For example,
> the result for n={1,2,...14} is
> P(n) = {1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
> 742900, 2674440}
>
> The reasons for this are complicated, but contact me if you're
> interested and I'd be glad to elaborate.
>
> Mike
>
> On Jul 17, 11:04 pm, "Rupesh Bhochhi" <[EMAIL PROTECTED]> wrote:
>
> > Thank you Karthik for your effort. I figure out lately that My
> > question is not that much logical. Actually there will be only one
> > possible combination that we can easily get as we have already got the
> > sorted lists.
>
> > On 7/17/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote:
>
> > > Hi,
> > >   Although, I cannot give you a complete solution right now..I will give 
> > > you
> > > the following relations (I am not sure If they are correct.discussions
> > > welcome)
>
> > > T(0, x) = 1
> > > T(x, 0) = 1
> > > T(1, x) = (x+1)
> > >  T(x, 1) = (x+1)
> > > T(n, m) = Sum[i=0..n] { T(n-i, m-2) * (i+1) }
>
> > > If you are looking for a program, then you can code this up...If you are
> > > looking for a closed form solution, this needs to be tidied up.
>
> > --
> > Rupesh Bhochhibhoya, [EMAIL PROTECTED]
> > Oklahoma State University
> > Stillwater, OK 74075


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: graph theory

[pramod]

For DAGs I don't think there's a unique path from a start vertex to
each vertex reachable from it. There could be many paths.

One way to solve this problem is to topologically sort the DAG and
start from the end and move backwards till the start vertex and keep
track of the longest path.
The last vertex has no paths from it to anywhere so the longest path
is of zero length.
The vertex before this will have longest path of 1 if it has an edge
to the last vertex.
So in general, when we encounter a vertex u then we check each edge
from it (u, v) and if vertex v has a longest path of length l then the
vertex u has a path of length l+1. We just need to find the longest of
these.
When we come to the start vertex, we get the required answer. The
while thing is linear time work.

Let me know if this is wrong.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: graph problem : i need help

[pramod]

Here's the code.


void NumPathsint **a, int v) //a is the adjacency matrix and v is the
number of vertices
{
int **t1 = new int*[v];
int **t2 = new int*[v];
for(int i = 0; i < v; ++i)
{
t1[i] = new int[v];
t2[i] = new int[v];
for(int j = 0; j < v; ++j)
t1[i][j] = a[i][j];
}

int **p1 = t1, **p2 = t2, **t;
for(int k = 0; k < v; ++k)
{
for(int i = 0; i < v; ++i)
for(int j = 0; j < v; ++j)
p2[i][j] = p1[i][j] + (p1[i][k] * p1[k][j]); 
//to count the number
of paths

//swap p1, p2
t = p1; p1 = p2; p2 = t;
}

//if p1[i][i] != 0, then there is a path from i to i itself which is
a loop so there are infinite paths from i to j if there's one path
from i to j
for(int i = 0; i < v; ++i)
{
if (p1[i][i] != 0)
{
p1[i][i] = -1; //-1 means loop and hence infinite paths
for(int j = 0; j < v; ++j)
p1[i][j] = p1[i][j] ? -1 : p1[i][j];
}
}

for(int i = 0; i < v; ++i)
for(int j = 0; j < v; ++j)
a[i][j] = p1[i][j];

//now 'a' contains the required results
}



--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: graph problem : i need help

[pramod]

Here's the code.

void Closure(int **a, int v) //a is the given adjacency matrix and v
is the number of vertices
{
int **t1 = new int*[v];
int **t2 = new int*[v];
for(int i = 0; i < v; ++i)
{
t1[i] = new int[v];
t2[i] = new int[v];
for(int j = 0; j < v; ++j)
t1[i][j] = a[i][j];
}

int **p1 = t1, **p2 = t2, **t;
for(int k = 0; k < v; ++k)
{
for(int i = 0; i < v; ++i)
for(int j = 0; j < v; ++j)
p2[i][j] = p1[i][j] + (p1[i][k] * p1[k][j]); 
//to count the number
of paths

//swap p1, p2
t = p1; p1 = p2; p2 = t;
}

//if p1[i][i] != 0, then there is a path from i to i itself which is
a loop so there are infinite paths from i to j if there's one path
from i to j
for(int i = 0; i < v; ++i)
{
if (p1[i][i] != 0)
{
p1[i][i] = -1; //-1 means loop and hence infinite paths
for(int j = 0; j < v; ++j)
p1[i][j] = p1[i][j] ? -1 : p1[i][j];
}
}

for(int i = 0; i < v; ++i)
for(int j = 0; j < v; ++j)
a[i][j] = p1[i][j];

   //array a now has the number of paths
}


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: graph problem : i need help

[pramod]

Not sure about what's wrong with your code is but the answer to the
problem is Warshall's algorithm for graph closure.
Just to brief, say we are given the adjacency matrix A[1] where A[1][i]
[j] = 1 if there's an edge from i to j.
Let A[k][i][j] be the the number of paths from i to j passing through
only vertices numbered from 1..k.
Then note that A[k][i][j] = A[k-1][i][j] + A[k-1][i][k] * A[k-1][k]
[j]. i.e., the number of paths from i to j passing through only
vertices numbered 1...k is equal to number of paths from i to k
passing through vertices numbered 1...k-1 PLUS number of paths from i
to k (with vertices 1...k-1) and k to j (with vertices 1..k-1).
What we want is the A[n] matrix which has the number of paths between
every pair of vertices.
But by any chance A[n][i][i] > 0 for any 'i' that means there's a loop
and i is a part of that loop. So this means there are infinite ways to
reach i from i and hence infinite ways to reach from i to j if there's
a way to reach from i to j.
Hope that helps.
I will paste the code once I am done with it.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Graph Problem

[pramod]

We must keep doing that repeatedly of course till no improvements can
be made.

On May 18, 1:58 am, billdoors <[EMAIL PROTECTED]> wrote:
> When will your algorithm stop ?
> It is unlikely to reverse only once and get the optimal.
>
> On May 17, 4:07 am, pramod <[EMAIL PROTECTED]> wrote:
>
> > Ohh, sorry to have missed that information. Consider minimizing the
> > maximum out-degree.
>
> > On May 16, 5:04 pm, "Rajiv Mathews" <[EMAIL PROTECTED]> wrote:
>
> > > Could you please explain the question.
>
> > > Typically in a directed graph we talk of in-degree and out-degree for
> > > a vertex. So is the question then to minimize the maximum of these in
> > > all vertices of the graph? If so what operations are permitted?
>
> > > On 5/16/07, pramod <[EMAIL PROTECTED]> wrote:
>
> > > > Here's a graph problem.
>
> > > > We are given a directed graph. We are allowed to change the directions
> > > > of the edges.
> > > > Our aim is to minimize the maximum degree in the graph.
> > > > How do we achieve this?
>
> > > > One way is to take the vertex with maximum degree, and take another
> > > > vertex with least degree reachable from this max-degree vertex and
> > > > then reverse all the edges' direction along the path. Now the
> > > > questions with this approach are (1) how do we prove that this will
> > > > lead to the optimal-graph in the sense, can we get a graph such that
> > > > it's maximum degree is the best possible?
> > > > (2) What's the time complexity, is it bound tightly?
> > > > (3) Is there any better way?
>
> > > > Thanks
>
> > > --
>
> > > Regards,
> > > Rajiv Mathews


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Graph Problem

[pramod]

Ohh, sorry to have missed that information. Consider minimizing the
maximum out-degree.


On May 16, 5:04 pm, "Rajiv Mathews" <[EMAIL PROTECTED]> wrote:
> Could you please explain the question.
>
> Typically in a directed graph we talk of in-degree and out-degree for
> a vertex. So is the question then to minimize the maximum of these in
> all vertices of the graph? If so what operations are permitted?
>
> On 5/16/07, pramod <[EMAIL PROTECTED]> wrote:
>
>
>
>
>
> > Here's a graph problem.
>
> > We are given a directed graph. We are allowed to change the directions
> > of the edges.
> > Our aim is to minimize the maximum degree in the graph.
> > How do we achieve this?
>
> > One way is to take the vertex with maximum degree, and take another
> > vertex with least degree reachable from this max-degree vertex and
> > then reverse all the edges' direction along the path. Now the
> > questions with this approach are (1) how do we prove that this will
> > lead to the optimal-graph in the sense, can we get a graph such that
> > it's maximum degree is the best possible?
> > (2) What's the time complexity, is it bound tightly?
> > (3) Is there any better way?
>
> > Thanks
>
> --
>
> Regards,
> Rajiv Mathews


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Graph Problem

[pramod]

Here's a graph problem.

We are given a directed graph. We are allowed to change the directions
of the edges.
Our aim is to minimize the maximum degree in the graph.
How do we achieve this?

One way is to take the vertex with maximum degree, and take another
vertex with least degree reachable from this max-degree vertex and
then reverse all the edges' direction along the path. Now the
questions with this approach are (1) how do we prove that this will
lead to the optimal-graph in the sense, can we get a graph such that
it's maximum degree is the best possible?
(2) What's the time complexity, is it bound tightly?
(3) Is there any better way?

Thanks


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Find the original array

[pramod]

Instead of arrays we can use BST to store the numbers, in which case
this problem can be solved in O(n log n).
Garcia, your algo is not O(n) as deleting an element in the array
itself is O(n) and you are deleting n-1 array elements.
I think better than O(n logn) is not possible but can't think of a
proof.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Sets having sum equal to N

[pramod]

If I understand correctly this is subset-sum problem and is NP-
Complete.

On Apr 30, 9:04 am, Cool_Happy <[EMAIL PROTECTED]> wrote:
> Suppose u r given a positive number N.
> How will we find a set of distinct positive numbers having sum equal
> to N.
> There could be multiple such sets so what is the algo to find all
> those sets.
>
> TIA
> Negi


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: how to tell honest people

[pramod]

OK, it's a long time for me too.
So let's see.
If we start with odd number of people, then we'll be left out with one
who won't be carried out in the next iteration.
Only when we found out at the end who the one truth teller is that we
ask the truth teller whether the left out single person is a liar or
truth teller.
So in this case only one question is needed for this person which is
what was needed otherwise too.

Hope it's clear. Take an example of odd numbered case and it should be
apparent.

On Apr 29, 4:48 pm, me13013 <[EMAIL PROTECTED]> wrote:
> (sorry to reply so late, I only discovered this thread yesterday)
>
> back on Mar/9 pramod wrote:
>
> > Say there are 'a' number of "tt" groups, 'b' number of "ll" who answer
> > "yy", 'c' number of "tl" and 'd' number of "ll" whose answer has a
> > "no" in it.
> >   ...
> > Hence proved.
>
> The proof given is only valid when the number of people you start
> with, in every round, is even.  How do you handle the odd case?
>
> Bob H


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Height of a binary tree

[pramod negi]

I think this always return height 1. isn't it

On 4/17/07, BiGYaN <[EMAIL PROTECTED]> wrote:
>
>
> We will be calling the function like :
> height = getheight(root);
>
> and here's the function defination :
> int getheight ( node *p )
> {
>if ( p==NULL )
>return 0;
>else
>rh = getheight ( p->right );
>lh = getheight ( p->left );
>return ( (lh>rh ? lh : rh)+1 );
> }
>
>
> >
>

--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Sum of subsets

[pramod]

Dor,

Yes, you are right and your method works.


On Apr 3, 1:05 pm, "dor" <[EMAIL PROTECTED]> wrote:
> Yes, you do know S. The problem statements says find the *subset* of S
> that sums to k, if any.
> Not knowing S does not make any sense anyway. S and k are an instance
> of SUBSET-SUM.
>
> On Apr 2, 8:41 am, "pramod" <[EMAIL PROTECTED]> wrote:
>
> > Dor,
>
> > If I understand the problem correctly, we don't know what are all the
> > elements in S (that's what we need to find).
> > So how are you going to pick 'k' first and how do you know of 'x'
> > belonging to S?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Sum of subsets

[pramod]

Peeyush,
I believe u misunderstood the problem. The problem does not ask for
finding two numbers whose sum is K.
Read the problem statement again.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Sum of subsets

[pramod]

Dor,

If I understand the problem correctly, we don't know what are all the
elements in S (that's what we need to find).
So how are you going to pick 'k' first and how do you know of 'x'
belonging to S?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: BST represented in array

[pramod]

Karthik,

Sorry for this but I still can't understand your program.
Can you describe it for me or give an example of how it works.
Will it work even in the case of non-complete BST, I mean for every
BST?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: BST represented in array

[pramod]

Karthik,

Can you please explain what your algorithm is doing?
If I am not wrong, we are given a BST in an array form meaning 'i'th
element has children at indices '2i' and '2i+1' right?
Does a unique BST exist for such an array (I believe it does), how to
prove?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: how to tell honest people

[pramod]

I think I made a mistake.
After we found out the truth teller, we need 2 questions for each of
the "tl" and "ll" groups.
This is because we know at least one of them is a liar and nothing
else. Say the answer is "yn" then the group could be "tl" or "ll".
Similarly if the answer is "nn" then also the group could be "tl" or
"ll". We need two questions to tell who's who and not one.
So my previous argument was wrong.

Here's another argument.
Say there are 'a' number of "tt" groups, 'b' number of "ll" who answer
"yy", 'c' number of "tl" and 'd' number of "ll" whose answer has a
"no" in it. Then total number of questions asked so far for grouping
is 2(a+b+c+d) = N the number of people we started with.
Now with induction we'll prove that for 'p' people we need at most
2p-2 questions.
In the next iteration we have a+b people so we need at most 2(a+b)-2
questions to identify all the truth tellers and liars among a+b.
Once we have that we need 2 questions each for c,d groups so we need
to ask 2(c+d) questions.
So total questions asked are 2(a+b+c+d) + 2(a+b) -2 + 2(c+d) = 4(a+b+c
+d)-2 = 2N-2.
Hence proved.
For 100 people we need at most 198. The "-2" is coming from the fact
that for the case of N=2 we don't need to ask any questions as both
have to be truth tellers.

I hope I am right this time.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: how to tell honest people

[pramod]

I think you are right. Let me put it in a formal way so that my
understanding is clear.
So we are grouping in "tt", "tl" and "ll" groups. If there are p
"tl"/"ll" groups whose answer include a "no" then we put them aside at
the end after we found out one truth teller and then with 'p'
questions can figure out all the truth tellers/liar in those groups.
So one "tl"/"ll" group having a "NO" answer will at end contribute one
question.
But instead if it was a group which answered "Yes/Yes" then one person
(say P) from it would have gone to second iteration. P would have been
paired up with someone and asked one question at least. So the
original group in which P was present will contribute one question
anyway.
This implies that total questions will be 198 only.

Let me know if I went wrong somewhere.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: removing redundant edges in a DAG

[pramod]

What do u mean by redundant?
If you mean those edges removing which any pair of vertices have same
connectivity as before, then DFS will do.
Note that you need to traverse all the edges and all the vertices and
DFS is linear in these terms so that looks best to me.

On Mar 6, 2:55 am, "Abid" <[EMAIL PROTECTED]> wrote:
> I am trying to remove redundant edges in a Direct Acyclic Graph (DAG).
> Is their any efficent approach to do it? I am using depth first search
> along critical path criteria  but its very slow for large graphs.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: how to tell honest people

[pramod]

Kathik,

I don't think backtracking will work.
Imagine at the end we have "lttt" i.e., one liar and 3 truth tellers.
After 4 questions, we have "tt" and "tl" groups. And we can identify
the "tt" group easily by seeing which group gives "yy" answer.
But the "tl" group may give answer "nn" both saying the other is the
liar.
In this case even though we know 2 truth tellers we need at least one
more question to be able to tell who is the truth teller.
You are removing all the "tl" groups from consideration but to tell in
each "tl" who is the truth teller we need one question in the worst
case of their answer being "nn".
So in the worst case we may need to ask 49 more questions in addition
to 198.
Am I right?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: how to tell honest people

[pramod]

Karthik,

How come the first round needs only 50 questions?
Since we are asking 2 questions for every group (x,y) viz. Is y
honest, Is X honest. Total questions are 100 for the first round.
Clarify please.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: spiral matrix..

[pramod negi]

The way u print a matrix in spiral order, same logic u can use to form the
matrix from given input PROVIDED the order of matrix is given ...
and this can be done in O(m x n) complexity...

--Negi

--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: the sum of two unsigned integers

[pramod negi]

>
>
>
> i think


 to check whethere the result is overflowed or not

check if ((A+B) -A is not equal to  B)
   printf("Overflow");


correct in if i m wrong

--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: (need help) How to solve this random number generatioin problem?

[pramod]

Why can't we simply take the 1..5 random number, multiply by 7 and
divide by 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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Finding the distance between two permutations of a string of length N

[pramod]

Isn't this same as permuting <1,2,...,n> to get  ?
Using an auxiliary array of bools we can find out the number of
permutations in O(n) time right?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Finding cycles in a Linked List

[pramod]

OK. I got this on the net. Too good. Time complexity is also O(n).

findloophead(x, y) {
  a = x
  b = y
  while (next(a) != b) {  /* while b is not loop head */
t = midpoint(a, b)
if (find(next(y), t, b)) {  /* if t is in the loop */
b = t
else
a = t
  }
  return(b)
}


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Finding cycles in a Linked List

[pramod]

But how do you detect where the cycle starts (or ends) ?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Counting Sort

[pramod]

It's hard to understand the code. I will appreciate if you can give
some verbal explanation of these algorithms.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Chord Intersection

[pramod]

Dhyanesh:
I am failing to see your point.
Imagine a circle with origin as the center. You can very well imagine
two chords parallel to x-axis. Say one is diameter and the other is
some chord little above the diameter. These two don't intersect. How
can two parallel chords in a circle intersect?

Karas: Can you please explain your code?

By the way, this problem was supposed to use Balanced Binary Search
Tree. Any ideas?
More over I think your algos are also finding which pairs intersect.
Remember that in the worst case of all chords being diameters, every
pair intersects to the answer is n(n-1)/2 which is O(n^2). How can you
find all the O(n^2) intersections in O(n log(n) time?
The question does not ask to find all the pairs but just to "count"
them.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Counting Sort

[pramod]

Can we change counting sort to sort inplace only using O(k) space where
the numbers range from 1...k?
The problem precisely is to design a sorting algorithm to sort 'n'
records whose keys range from 1...k in O(n) time using only an
auxiliary array of size k. The algorithm should sort be stable and
should sort in-place. Remember that the original array is an array of
records with integer keys. So simply copying the numbers won't do, we
need to indeed swap the records.
I know one place algo based on counting sort but it's not stable.
Any solutions ?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Chord Intersection

[pramod]

I don't think this will work.
Suppose we have two chords which are parallel and both on the one side
of the circle. i.e., say draw a diameter parallel to X and say the
chords are above this parallel to each other.
In that case, your answer will be 1 but they are not intersecting at
all. I think your statement "if you get another start point it means
there is an intersection" is not correct.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Chord Intersection

[pramod]

I don't get this, can you explain it?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Chord Intersection

[pramod]

There are 'n' chords of a circle. How to find the number of pairs of
the chords which are intersecting in O(n log(n)) time. All the end
points of the chords are unique.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: right-convertible tree

[pramod]

Yes, I agree. In fact we can take the simple example here. T1's root is
2, left of root 1 and right of root 3. Let T2's root be 3, left of root
1 and right of 1 be 2. There's no way we can get T2 from T1 using right
rotations.
But if given that T1 with 'n' nodes can be converted to T2, in the
worst case how many such right-rotations are needed. The answer is
supposed to be O(n^2) but I couldn't prove it.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] right-convertible tree

[pramod]

Hi All, this one is from CLR.
A binary search tree T1 can be "right-converted" to another binary
search tree T2 (made from the same keys) if there exist a series of
"right-rotations" applying which T1 becomes T2. Given T1, is T1
right-convertible to all possible T2s? If T1 can be right-converted to
T2, how many right-rotations are needed?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Some problems

[pramod]

Certainly not. Both are from CLR. Moreover I am not student anymore.
BTW any solutions?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: check string A and B isPermutation ?

[pramod]

Something on the lines of counting sort will do. Make an array
Count[26] where Count[1] will have the number of a's etc. While reading
string A, keep note of the count of the characters in Count and while
reading B, just check if the same number of characters occur.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Some problems

[pramod]

Hi All,
Please try to provide solutions to the below problems.

1) For any given polynomial algorithm A for a decision problem, we can
associate a language L = { x | A(x) = 1 } i.e., all such inputs. If P
is the set of all such languages (remember polynomial time of A), is P
closed under Kleene Star? Note that P is closed under union,
intersection, complement and concatenation.

2) Task scheduling. We are given N tasks. Task Ai takes Ti amount of
time and has a deadline Di finishing the task within deadline leads to
a profit of Pi. We want to schedule the tasks so that there is maximum
profit. Will greedy approach in this case? If all the numbers involved
are integers then can we dynamic programming to solve this polynomial
time? If the numbers are real, prove that the problem is NP-C.

Thanks.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Balanced tree building

[pramod]

Malay, I think your solution gives wrong results. Can you please verify
and explain us.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Balanced tree building

[pramod]

But this will require O(N) space anyway. The problem asks for O(log(n))
space.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Balanced tree building

[pramod]

Madan, yours will take O(n) space.
I could think of an algo which takes O(nlogn) time and O(logn) space.
We first traverse till the middle of the original BST and make it the
root. We also make the till now traversed portion of the tree to be the
right child of this root and then we recursively solve the problem.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: need help help n help!!!

[pramod]

That's true Dhyanesh, thanks. Any prose explanation for SPX2's pseudo
code?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: may be greedy approach

[pramod]

This problem is actually NP-Complete and is same as set-cover problem.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: optimal assignnment of program to tapes.

[pramod]

Yes, this is NP-Complete and is called Partition problem or Subset-sum
problem. But I still fail to understand how Karthik's algo works.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: need help help n help!!!

[pramod]

Isn't third problem solved by sorting where comparison function is
replaced by the equivalence tester? After sorting we just run through
the array to see if there n/2 repetitions.

ajay mishra wrote:
> @stefan  , ur idea seems correct to me.
>
> On 3/8/06, SPX2 <[EMAIL PROTECTED]> wrote:
> >
> >
> > ajay what do you think of what i wrote ?
> >
> >
> >
> >
>
>
> --
> Ajay kr. Mishra
> http://ajay.mishra19.googlepages.com
> IIT KGP
>
> --=_Part_1256_15286189.1141885069996
> Content-Type: text/html; charset=ISO-8859-1
> Content-Transfer-Encoding: quoted-printable
> X-Google-AttachSize: 554
>
> @stefan  , ur idea seems correct to me. class="gmail_quote">On 3/8/06, SPX2 < href="mailto:[EMAIL PROTECTED]">[EMAIL PROTECTED]> 
> wrote:
> -- Ajay kr. 
> Mishra href="http://ajay.mishra19.googlepages.com";>http://ajay.mishra19.googlepages.comIIT
>  KGP
> 
> --=_Part_1256_15286189.1141885069996--


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: may be greedy approach

[pramod]

How about dynamic programming solution to this problem?

The nth entry may be chosen or may not be chosen. If it is chosen then
the sub problem to be solved is that of all those entries whose start
times are after the end time of the nth entry.

C(N,S) = 1+C(N',S') where S' = S U {n} and N' = those members of N
whose start time is after the end time of nth entry.
Originally, S is empty and N = { 1, 2, ..., n }

if nth entry is not considered, then we need to find all such edges
which overlap with nth entry and for each of those entries, we solve
the sub problem. Whichever gives the minimum result, that's the answer.

C(N,S) = 1 + min over p { C(N',S'), where N' = N - {n} - {p}, S' = S U
{p} } where 'p' is an entry which overlaps with nth entry.

So, if we make a table of n X 2^n whose columns are power set of
{1,2,...,N} and whose rows are 1,2,...n. and keep filling it row-wise.

Let me know your opinions.

SPX2 wrote:
> its actually called backtracking


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: optimal assignnment of program to tapes.

[pramod]

I am afraid, I don't understand your solution Karthik. When the loop is
run for program P1, Arr[0] = 1 and Arr[P1] = 1, when program P2 is
considered Arr[P0]=1, Arr[P2]=1 and Arr[P1+P2]=1 etc
After considering Pn, we have Arr[P1+...+Pn]=1, so how does this help
solve the problem?
Can you explain your solution more in depth?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: C++ question.

[pramod]

you can have function objects, i.e., objects which behave like
functions with overloading the () operator. Define a base class like
"base_functor" and for each different function pointer, define a new
class which will store this function pointer and whose operator () will
take the same parameters as the function pointer and call the function
thru the stored pointer. the map can be of declared like
map. Try it out.

struct base_functor
{
 void operator () (void) { };
};

#define int (*FP)(int, char);

struct one_functor : base_functor {
 one_functor(): fp(NULL) {}
 one_functor(Fp f) : fp(f) {}
 int operator (int a, char b) {
return fp(a,b);
 }
 private:
  FP fp;
};

and so on

map myMap;

int foo(int a, char b)
{
  //does something
}

one_functor of(foo);

myMap["one"] = of;

etc

Will this solve your problem ?


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: a tree problem

[pramod]

Shouldn't there be "+1" in your step?
min_map[p] = min_step + 1, since 1 step is needed to get to that
optimal child.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Automaton

[pramod]

I don't think so. Let the odd number be AnAn-1An-2...A3A2A1.
This number can be odd, if AnAn-1...A3A2 is odd and A1 is even (0/2) OR
AnAn-1...A3A2 is even and A1 is odd (1). So this clearly gives a simple
DFA.

let Qs be the start state and Qe is the state DFA enters when an even
number is seen so far and Qo be the state DFA enters when an odd number
is seen so far.

(Qs,0/2) --> Qe
(Qs,1) --> Qo
(Qe,0/2) --> Qe
(Qe,1) --> Qo
(Qo,0/2) --> Qo
(Qo,1) --> Qe

Here were are entering the digits from most significant first.
So the set of odd numbers is regular in both notations.

Any other ideas?

[algogeeks] Automaton

[pramod]

I have simple problem involving finite automaton.
Let 'A' be some (infinite) language which is a subset of natural
numbers.
Let B(A) the the language over the alphabet {0,1} such that B(A)
contains all (and only) the members of A in binary form.
Similarly let C(A) contain all (and only) the members of A in base 3.

For example, let A = { 3 , 5 } then
B(A) = { 11, 101 } and C(A) = { 10, 12 }. Here I used finite A but A is
actually infinite.

Now the problem is to find an A such that B(A) is regular language (an
NFA exists for this) but C(A) is not regular.

Thanks

[algogeeks] Re: Sum of sub array

[pramod]

The problem is not clear to me. How can an algo exist that takes O(n)
space but only O(log n) time? Even just to access the O(n) memory, we
need O(n) time. For example in the above algo, if i = 1 and j = n, then
how can the sum be obtained in O(log n) time?

[algogeeks] Re: Cashbox withdrawal

[pramod]

This can be solved by Dynamic Programming.
Let the denominations be d1,d2,...,dn and their corresponding numbers
be P1,P2,...,Pn. Let C(n,S) be the matrix which tells us if the amount
S can be obtained by using coins d1,...,dn.
Then C(n,S) = C(n-1,S) if denomination dn is not used, else
C(n,S) = C(n,S-Pn), Pn = Pn-1 --> if Pn > 0
else = C(n-1,S) if Pn == 0
Also note that C(a,A) = 1 if A is a multiple of dp and A < dp * Pa.
So the matrix C can be filled up column wise. So C(n,S) = 1 if C(n-1,S)
= 1
else C(n,S) = C(n,S-Pn) if Pn > 0 else C(n,S) =
If C[S] is 1 at the end, then the sum S can be obtained else it can't
be.

[algogeeks] Re: Finding duplicate

[pramod]

Hi Varadha,
Could you present your logic please?

[algogeeks] Partition problem

[pramod]

I came across this problem:
Given N positive integers, partition these into two disjoint subsets
with the same sum of their elements (of course, the problem does not
always have a solution).  Design an exhaustive search algorithm for
this problem.  Try to minimize the number of subsets the algorithm
needs to generate.

[algogeeks] Re: Comparing two mathematical expressions

[pramod]

I think it's better to come up with an algorithm regardless of the
complexity. I will be happy if someone can provide an NP solution to
this.

[algogeeks] Re: Comparing two mathematical expressions

[pramod]

Vijay,
Your algo is not clear to me.
Let's take the original example given by moop.
(a+b)*(c-d) whose lexicographic sorting will give (a+b)*(c-d)
and second expression is (c-d)/(1/(b+a)) whose lexicographic sorting
will give
(c-d)/(1/(a+b))
These two are not the same, so what you propose to do?

[algogeeks] Re: inorder sucessor and predecessor

[pramod]

I think it's better if you present your logic first before giving the
code.

[algogeeks] Re: Couple of more questions

[pramod]

For the 4th question, we can consult the oracle log(n) times only. If
we test the program, it can loop forever and we have no way of knowing
that.

[algogeeks] Couple of more questions

[pramod]

Here are some more questoins:

1) A magic square is a 3 x 3 array of numbers with the property that
you get the same total if you sum up any row, any column, or even any
diagonal. I have a 3 x 3 array of empty boxes, and some coins. I want
to put the coins into the boxes in such a way that the total amount of
money in each box forms a magic square. I have 5 quarters, 8 dimes, and
13 nickles.
a) Give me a way to do this that uses all the coins
b) Give me a way to do this using as few coins as possible (but at
least one)

2) A square picture is cut into 16 squares and they are shuffled. Write
a program to rearrange the 16 squares to get the original big square.

3) The numbers 1 to  (decimal base) were written on a paper. Then
the paper was partially eaten by worms. It happened that just those
parts of paper with digit "0" were eaten. Consequently the numbers 1200
and 3450 appear as 12 and 345 respectively, whilst the number 6078
appears as two separate numbers 6 and 78. What is the sum of the
numbers appearing on the worm-eaten paper?

4) You are given n programs p1 ... pn, each of which take an ASCII
string as input. Each program will either output an ACCEPT signal, or a
REJECT signal, or will loop forever. You are also given n strings s1
... sn, each affiliated with a respective program. Your task is to
write a meta-program that determines which of the N program-string
pairs output an ACCEPT. To assist you in this task, your meta-program
is allowed to query an oracle, a black box that takes a program and a
string as inputs, and immediately tells you if the computation ACCEPTs,
REJECTs, or loops forever. However, you can only query the oracle log n
times.

[algogeeks] Re: Finding duplicate

[pramod]

But Dhyanesh, don't forget the condition that we are given that exactly
one number is repeated twice. What you said is true for the general
case. How do you prove that for this special, there's no algorithm that
takes less than O(nlogn)? If such an algorithm exists and we give an
input consisting of several repititions (or no repititions at all), it
might give us wrong result since the pre-condition of running the algo
has failed. Let me explain to you this way:
input --> Algo --> output
Here input must satisfy the condition that exactly one number is
repeated twice, in which case, Algo guarantees that output will consist
of the two indices of that repeated number.
But if we give input not satisfying this condition, Algo is not liable
work correctly and it can and might give wrong results.
Let me know your thoughts on this.

[algogeeks] Re: Fastest way to find arbitary element in linked list?

[pramod]

Use two pointers, one 5 elements ahead of the other. Now move both
pointers ahead together by one element until the first one hits the
end, the second pointer will point to the fifth element from the last.

[algogeeks] Re: Design an algorithm

[pramod]

In my algo, this O(N) space restriction is not violated. Each computer
uses O(N) space only. But overall, all the N computers use O(N^2) space.

[algogeeks] Re: Finding duplicate

[pramod]

I agree with Dhyanesh. This "counting" sort routine prescribed by Adak
fails when the numbers can be random.
Dhyanesh, I searched for "element uniqueness" and that problem is more
generic. It says to find if all the numbers are unique. But in my
problem it is known that exactly one number is duplicated (and exactly
once). So I am still hoping for a better solution than O(n log(n) ).