Tayzwi
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.
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.
posted by Tejaswi # 2:57 AM 
Archives
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)
