Should be reading more and writing less, but well...

Friday, September 24, 2004


solution to set theory question

Marvel at Richard Karp's creativity.....

The black box algorithm finds one set of subsets among the given set of subsets so that their union gives the main set and they are pairwise disjoint. Now, somehow we need to make sure that it returns a set of subsets whose size is K.

The solution is to add K new distinct elements to the main set (change the main set). Say the new elements are X1, X2, X3.....Xk. Add X1 to all the given M subsets and get new subsets. Add X2 to all the subsets and get another set of new subsets, and so on.....to get M*K new subsets. Now feed the changed main set and the new set of M*K subsets to the blackbox algorithm (just once).

You can verify this solution quite easily.

Comments: Post a Comment

<< Home


February 2004   July 2004   August 2004   September 2004   October 2004   November 2004   December 2004   January 2005   February 2005   March 2005   April 2005   May 2005   June 2005   July 2005   August 2005   September 2005   October 2005   November 2005   December 2005   January 2006   February 2006   March 2006   April 2006   May 2006   June 2006   July 2006   August 2006   September 2006   October 2006   November 2006   January 2007   April 2007   May 2007   June 2007   November 2007   December 2007   January 2008   March 2008   June 2008   February 2009   June 2009   February 2010   November 2010  

Quick index to blog-posts I like (from my personal website)

This page is powered by Blogger. Isn't yours? Statscounter is generating statistics of this page