SET OPERATIONS IN C, MOST OF THE CODE IS GIVEN, JUST NEED HELP WRITING THE FUNCT
ID: 3871208 • Letter: S
Question
SET OPERATIONS IN C, MOST OF THE CODE IS GIVEN, JUST NEED HELP WRITING THE FUNCTIONS. here is the given code that needs to be completed, under "////////////// YOU WRITE THE FOLLOWING /////////////////"
/* Set operations Dan Ross Original Feb 2013, 32bit extension Sep 2016 Performs set operations. Universe = {Bat, Cat, Chimp, Dog, Fish, Liger, Snake, Turtle} */ #include #include #include #pragma warning( disable : 4996) #pragma warning( disable : 4244) // Start with a small universe char Universe[8][10] = { "Bat", "Cat", "Chimp", "Dog", "Fish", "Liger", "Snake", "Turtle" }; typedef unsigned char set; // a set, by any other name, would smell as sweet. // Then use this big universe char BigUniverse[32][20] = { "Bat", "Cat", "Chimp", "Dog", "Fish", "Liger", "Snake", "Turtle", "Bear", "Dragon", "Horse", "Wolf", "Rat", "Gerbil", "Rabbit", "Monkey", "Donkey", "Llama", "Zebra", "Hippopotamus", "Rhiceros", "Gecko", "Frog", "Sloth", "Deer", "Kangaroo", "Gorilla", "Alligator", "Panda", "Squirrel", "Duck", "Platypus" }; typedef unsigned long int set32; // a set, but bigger /* Prints out a set in set-sequence notation */ void printSet(set A) { printf("{ "); bool commaflag = false; int i = 0; unsigned char mask = 0x80; for (; mask; mask >>= 1, i++) { if (mask & A) { if (commaflag) printf(", "); printf(Universe[i]); commaflag = true; } } printf(" }"); } /* Prints each bit of a byte */ void print8bits(unsigned char x) { for (unsigned char mask = 0x80; mask; mask >>= 1) { if (mask & x) printf("1"); else printf("0"); } } /* Inserts an element of the universe into a set */ void insert(set & A, char str[]) { // First we need to get the Universe index of this string // Use hashing instead of searching - cuz it is faster // than searching, especially for a big universe. // You will have to modify this for the 32bit universe // If you do not know how to hash && do not want to learn now // then modify this to use a loop search lookup with strcmp // get a unique hash for each string int hash = (str[0] + str[2]) % 20; // map unique string hashes back to their Universe indexes // 0 1 2 3 4 5 6 7 8 9 int g[20] = { 6, -1, 0, 1, -1, 4, -1, -1, -1, -1, // 10 11 12 13 14 15 16 17 18 19 -1, 3, 2, -1, -1, -1, -1, -1, 7, 5 }; int index = g[hash]; // make a mask set mask = 0x80 >> index; // insert this element A = A | mask; } /* Calculates base raised to the power exp */ int my_pow(int base, int exp) { int x = 1; for (int i = 0; i < exp; i++) x *= base; return x; } ////////////// YOU WRITE THE FOLLOWING ///////////////// /* Union */ set Union(set A, set B) { // return a dummy value for now return A; } /* Intersection */ set Intersection(set A, set B) { // return a dummy value for now return A; } /* Complement */ set Complement(set A) { // return a dummy value for now return A; } /* Difference */ set Difference(set A, set B) { // return a dummy value for now return A; } /* Cardinality */ int Cardinality(set A) { // return a dummy value for now return 42; } /* PowerSet Algorithm: OriginalSet -> Compress permutationN -> decompress -> print Example: 0010 0001 -> 11 -> 00 -> 0000 0000 -> 01 -> 0000 0001 -> 10 -> 0010 0000 -> 11 -> 0010 0001 Basically, just generate all the 'compressed' subsets B by counting from 0 to (2^|A|) - 1 Then decompress each B by inserting each bit (0 or 1) of the 'compressed' set into the next 'available' uncompressed slot in subA */ void printPowerSet(set A) { /* int CardOfP = my_pow(2, Cardinality(A)); set setB = 0; // a lil 'compressed' set set subA = 0; // some subset of A // generate each "compressed" subset (loop: count on setB from 0 to (2 ^ | A | ) - 1) { // uncompress setB into subA unsigned char Amask = 0x01; // start at decimal value 1 unsigned char Bmask = 0x01; // start at binary value 0000 0001, (You could also start at octal value 1) // use Amask to check for "slots" in original setA (loop: try each bit position from decimal values 1 to 128) // Hint: bit shifting might work here { // use Amask to look for available slots in setA if (this slot is available in original setA) // Hint: bitwise AND might work here { iteration 1 of this conditional would look like this if you worked it out with a pencil setA 0010 0001 & Amask 0000 0001 ___________________ TRUE // use Bmask to check if corresponding element exists in setB if (this element in set B) { iteration 1 of this conditional would look like this if you worked it out with a pencil setB 00 & Bmask 01 ______________ FALSE // use Amask to insert this element into subA. iteration 1 of this insert operation would look like this if you worked it out with a pencil subA 0000 0000 | Amask 0000 0001 ___________________ subA 0000 0001 } // shift Bmask left. } // shift Amask left. Could do that here, or in the loop conditional, depending on how you write the loop } // print subA // reset subA to ZERO // next setB } */ } bool IsSubset(set ASubset, set ASet) { // return a dummy value for now return true; } bool IsProperSubset(set ASubset, set ASet) { // return a dummy value for now return true; } /********************************************************* main - modify as necessary with various test data *********************************************************/ void main(void) { set A = 0; insert(A, "Bat"); insert(A, "Cat"); insert(A, "Chimp"); insert(A, "Snake"); printf("Set A: "); printSet(A); printf(" Cardinality: "); printf("%d", Cardinality(A)); printf(" PowerSet(A): "); printPowerSet(A); set B = 0; insert(B, "Chimp"); insert(B, "Fish"); insert(B, "Liger"); printf(" Set B: "); printSet(B); set C = 0; insert(C, "Chimp"); insert(C, "Fish"); insert(C, "Liger"); printf(" Set C: "); printSet(C); printf(" (A Union B) Inter ~C: "); set D = Intersection(Union(A, B), ~C); printSet(D); if (IsSubset(B, C)) printf(" B is a subset of C"); else printf(" B is NOT a subset of C"); if (IsProperSubset(B, C)) printf(" B is a proper subset of C"); else printf(" B is NOT a proper subset of C"); printf(" "); /* OUTPUT OF ABOVE TESTING Set A: { Bat, Cat, Chimp, Snake } Cardinality: 4 PowerSet(A): { } { Snake } { Chimp } { Chimp, Snake } { Cat } { Cat, Snake } { Cat, Chimp } { Cat, Chimp, Snake } { Bat } { Bat, Snake } { Bat, Chimp } { Bat, Chimp, Snake } { Bat, Cat } { Bat, Cat, Snake } { Bat, Cat, Chimp } { Bat, Cat, Chimp, Snake } Set B: { Chimp, Fish, Liger } Set C: { Chimp, Fish, Liger } (A Union B) Inter ~C: { Bat, Cat, Snake } B is a subset of C B is NOT a proper subset of C */ }
Explanation / Answer
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#pragma warning( disable : 4996)
#pragma warning( disable : 4244)
char Universe[8][10] = {"Bat", "Cat", "Chimp", "Dog", "Fish", "Liger", "Snake", "Turtle"};
typedef unsigned char set;
char BigUniverse[32][20] = {
"Bat", "Cat", "Chimp", "Dog", "Fish", "Liger", "Snake", "Turtle",
"Bear", "Dragon", "Horse", "Wolf", "Rat", "Gerbil", "Rabbit", "Monkey",
"Donkey", "Llama", "Zebra", "Hippopotamus", "Rhiceros", "Gecko", "Frog", "Sloth",
"Deer", "Kangaroo", "Gorilla", "Alligator", "Panda", "Squirrel", "Duck", "Platypus"};
typedef unsigned long int set32;
void printSet(set A)
{
printf("{ ");
bool commaflag = false;
int i = 0;
unsigned char mask = 0x80;
for( ; mask; mask >>= 1, i++) {
if(mask & A)
{
if(commaflag) printf(", ");
printf(Universe[i]);
commaflag = true;
}
}
printf(" }");
}
void print8bits(unsigned char x)
{
for(unsigned char mask = 0x80; mask; mask >>= 1) {
if(mask & x)
printf("1");
else
printf("0");
}
}
void insert(set & A, char str[])
{
int hash = (str[0] + str[2] ) % 20;int g[20] = { 6, -1, 0, 1, -1, 4, -1, -1, -1, -1,
int index = g[hash];
set mask = 0x80 >> index;
A = A | mask;
}
int my_pow(int base, int exp)
{
int x = 1;
for(int i = 0; i < exp; i++)
x *= base;
return x;
}
set Union(set A, set B)
{
set newSet = A | B;
return newSet;
}
set Intersection(set A, set B)
{
set newSet = A & B;
return newSet;
}
set Complement(set A)
{
return (~A);
}
set Difference(set A, set B)
{
set newSet = Intersection(A, ~B);
return newSet;
}
int Cardinality(set A)
{
bool commaflag = false;
int i = 0, j = 0;
unsigned char mask = 0x80;
for (; mask; mask >>= 1, i++) {
if (mask & A)
{
j++;
commaflag = true;
}
}
return (j);
PowerSet
Algorithm:
OriginalSet -> Compress -> permutation0 -> decompress -> print
...
permutationN -> decompress -> print
void printPowerSet(set A)
{
int cardValue = Cardinality(A);
int totalPowerSet = my_pow(2, cardValue);
printf(" Just looking at set A: ");
print8bits(A);
set B = 0;
set subSetA = 0;
int i = 0;
for (B = 0; B < totalPowerSet; B++)
{
printf(" Just looking at set B: ");
print8bits(B);
int Amask = 0x00;
for (Amask = 0x01, i = 0; i < totalPowerSet ; Amask <<= 1, i++)
{
printf(" INSIDE SECOND FOR Just looking at set A: ");
print8bits(A);
printf(" Just looking at 'A mask': ");
print8bits(Amask);
if ( A & Amask )
{
printf(" Just looking at set subSet A: ");
print8bits(subSetA);
int Bmask = 0x01;
if ( B & Bmask )
{
printf(" JUST looking at 'B mask': ");
print8bits(Bmask);
subSetA = subSetA | Amask;
Bmask <<= 1;
}
}
}
printf(" Just looking at set subSet A: ");
print8bits(subSetA);
printf(" ");
printSet(subSetA);
subSetA = 0;
}
}
bool IsSubset(set ASubset, set ASet)
{
if (ASubset == ASet)
{
return true;
}
return false;
}
bool IsProperSubset(set ASubset, set ASet)
{
if (ASubset == ASet)
{
return false;
}
return true;
}
void main(void)
{
set A = 0;
insert(A, "Fish");
insert(A, "Turtle");
printf("Set A: ");
printSet(A);
printf(" Cardinality: ");
printf("%d", Cardinality(A));
printf(" PowerSet(A): ");
printPowerSet(A);
set B = 0;
insert(B, "Chimp");
insert(B, "Fish");
insert(B, "Liger");
printf(" Cardinality: ");
printf("%d", Cardinality(B));
printf(" Set B: ");
printSet(B);
set C = 0;
insert(C, "Chimp");
insert(C, "Fish");
insert(C, "Liger");
printf(" Set C: ");
printSet(C);
TEST IF COMPLEMENT WORKS
printf(" Complement A is: ");
set F = Complement(A);
printSet(F);
TEST IF DIFFERENCE WORKS
set F = Difference(A, B);
printf(" The difference between A and B is: ");
printSet(F);
set D = Intersection(Union(A, B), ~C);
printSet(D);
if(IsSubset(B, C))
printf(" B is a subset of C");
else
printf(" B is NOT a subset of C");
if(IsProperSubset(B, C))
printf(" B is a proper subset of C");
else
printf(" B is NOT a proper subset of C");
printf(" ");
system("pause");
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.