Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

How do you cover an entire set?

Posted on 2011-02-26
Medium Priority
356 Views
Hey,

I had a question that kept bugging me after my last algorithms class.  My professor asked us to come up with an algorithm that will select as few subsets as possible to re-make the original set.  And I came up with this:

We would take the largest subset with the most elements that are present in the original set, and then cancel out the elements in the original set, and then we would repeat this process till all the elements in the original set are cancelled out.

But he said that it wasn't the optimal solution... and didn't give me a good enough explanation...

I don't understand why this solution isn't the most optimal one... because even if you had a set S = {1, 2, 3, 4, 5}, and subsets S1 = {1, 2}, S2 = {2, 3, 4}, S3 = {1}, S4 = {5}.  With my algorithm you would select S2, S3, and S5... right?  Which would remake the original set.

Could someone help me understand this?
0
Question by:errang
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 4

Assisted Solution

LAMASE earned 664 total points
ID: 34989187
if you have

SET: {1,2,3,4,5,6}
SUBSETS: {1,3,5}, {1,2}, {3,4}, {4,5}, {5,6}

You algorithm will take the first subset, because it is the biggest, and then fail.
0

LVL 37

Accepted Solution

TommySzalapski earned 668 total points
ID: 34989212
If you don't already know this, then the set cover problem is NP-Complete which means there is no known optimal solution that's much faster than just checking every possible subset, so your professor is either trying to make that point or just trying to mess with you.
As LAMASE pointed out, your solution fails any time the large subset is not in the optimal solution.
0

LVL 84

Assisted Solution

ozo earned 668 total points
ID: 34989214
if you had a set S = {1, 2, 3, 4,  5,6,7,8, 9,10,11,12},
and subsets  S1 = {1, 2,3,4}, S2 = {5,6,7,8},
S3 = {1,5,9}, S4 = {2,6,10}, S5 = {3,7,11}, S6={4,8,12}.
With your algorithm you would select S1,S2,S3,S4,S5,S6
but the optimal solution is S3,S4,S5,S6
0

LVL 37

Expert Comment

ID: 34989215
Should read "checking every possible combination of subsets"
0

Author Closing Comment

ID: 34989362
Ah... sweet, thanks a lot!
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
This course is ideal for IT System Administrators working with VMware vSphere and its associated products in their company infrastructure. This course teaches you how to install and maintain this virtualization technology to store data, prevent vuln…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses
Course of the Month8 days, 11 hours left to enroll