50185. Hitting set, part I

Task Description

We are going to write programs to solve the hitting set problem. The hitting set problem is defined as follows.

Given a set $T$ of subsets of S, we want to find the smallest subset $S'$ of $S$ that intersects every elements in $T$. For example, when $S = \lbrace 1, 2, 3, 4, 5, 6, 7\rbrace $ and $T = \lbrace \lbrace 1, 2\rbrace , \lbrace 2, 4\rbrace , \lbrace 5, 6\rbrace ,\lbrace 6,7\rbrace \rbrace $, the smallest hitting set $S'$ is $\lbrace 2,6\rbrace $.

We first design an object for "sets". You can store any information you need in the struct. We will use initializeSet to initialize the set to be empty. Then we need an intersect function that returns true if the two sets intersect, and false otherwise. Next we need an addElement that adds an element into a set s. Then we need a removeElement function that removes an element from a set s. Finally, we need a printSet function to print the set. The following are the templates of the structure and function APIs in set.h. You should implement the functions in another file set.c.

#include <stdio.h>
#include <stdbool.h>
 
typedef struct set{
        /* design yourself */
}Set;
 
void initializeSet(Set* set, int numberOfElement);
bool intersect(Set set1, Set set2);
void addElement(Set* set, int element);
void removeElement(Set* set, int element);
void printSet(Set set);

Note that the size of sets $n$ is in the range $1 \le n \le 64$, where $S = \lbrace 1 ,2 , 3 ... n\rbrace $..

We recommend that you use bit operations to implement these functions for efficiency. For example, $\lbrace 1,4,5\rbrace $ can be represented as $11001$.

You can use testMain1.c to test your addElement function and use testMain2.c to test your removeElement function, and use testMain3.c to test your intersect function:

This is testMain1.c.

#include <stdio.h>
#include "set.h"
 
int main(){
    Set s;
    int numberOfElement = 5;
    initializeSet(&s, numberOfElement);
    addElement(&s, 1);
    addElement(&s, 2);
    addElement(&s, 5);
    printSet(s);
}

This is testMain2.c.

#include <stdio.h>
#include "set.h"
 
int main(){
    Set s;
    int numberOfElement = 4;
    initializeSet(&s, numberOfElement);
 
    addElement(&s, 1);
    addElement(&s, 2);
    addElement(&s, 4);
 
    removeElement(&s, 1);
 
    printSet(s); 
}

This is testMain3.c.

#include <stdio.h>
#include "set.h"
 
int main(){
    Set s1, s2;
    int numberOfElement = 5;
    initializeSet(&s1, numberOfElement);
    initializeSet(&s2, numberOfElement);
 
    addElement(&s1, 1);
    addElement(&s1, 3);
    addElement(&s2, 1);
    addElement(&s2, 5);
 
    if(intersect(s1, s2)) 
        printf("intersect!\n");
}

Subtask

• 10 points: addElement function testing.
• 10 points: removeElement function testing.
• 10 points: intersect testing.

Sample output of testMain1.c

1 2 5

Sample output of testMain2.c

2 4

Sample output of testMain3.c

intersect!