wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> dynamic-set operation 
        
(Message started by: nks on Jan 28^th, 2009, 1:19am)

Title: dynamic-set operation
Post by nks on Jan 28^th, 2009, 1:19am

Question from book of H.Cormen.

The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The sets S1 and S2 are usually destroyed by the operation.
How to support UNION in O(1) time using a suitable list data structure ?

Can anybody explain the question?

Title: Re: dynamic-set operation
Post by towr on Jan 28^th, 2009, 1:34am

on 01/28/09 at 01:19:25, nks wrote:

The sets S1 and S2 are usually destroyed by the operation.
[..]
Can anybody explain the question?

"Destroying" the input means that you can't depend on it being the same before and after the operation. The operation may change the datastructure it is given as input, and use it for the datastructure of the output; for example what an inplace sort does (there the original input-array is destroyed, in that that the original order is destroyed).

[hide]If they're disjoint, you can just join the two lists. L1.last()->next=L2.first();
It may be inconvenient for other operations, though.[/hide]

Title: Re: dynamic-set operation
Post by nks on Jan 28^th, 2009, 2:06am

Is it like how to disjoint the union set after destroying the S1 and S2 ?

Title: Re: dynamic-set operation
Post by towr on Jan 28^th, 2009, 2:51am

on 01/28/09 at 02:06:24, nks wrote:

Is it like how to disjoint the union set after destroying the S1 and S2 ?

I don't understand that sentence; can you rephrase it?

Title: Re: dynamic-set operation
Post by Grimbal on Jan 28^th, 2009, 6:33am

I think the question is simply: how to compute the union of 2 sets.
You are asked to describe what list structure is suitable for the task.
You are not requested to preserve the original lists, which means you can take break apart the original lists and reassemble the union from that.

Title: Re: dynamic-set operation
Post by nks on Jan 28^th, 2009, 10:52pm

I think question is making union of 2 sets using these sets so original can be destroyed .

So once union is done it should not depend on original set s1 and s2.