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!