CS240 Fall 2009 - Project 3
Sets Calculation

Goal

In this project you will write a program that performs operations and relations on sets (union, intersection, difference, inclusion, cartesian product). You are NOT allowed to use the array operator [] at any place, or you will get an automatically zero, and please use pointer arithmetics to calculate the results of the operations.

Background

So far you have learned that a pointer simply ``points'' to an address in the computer's memory, and that pointers are closely related to arrays. In fact, such a relationship is so strong that both are simultaneously discussed in your C textbook! For now, you need to keep in mind that a pointer is just the base address of an array, and furthermore, that any operation that can be achieved by array subscripting can also be done with pointers.

You are probably familiar with the basics of set theory. For this project we only need to remember the following:

• We can think of a set as an unordered collection of objects.
• Sets can be defined by intension or by extension. For example, we can define $C$ to be the set of the integer numbers that are greater than zero and less than five (by intension), or we can define $C$ as: $C = \left\{1, 2, 3, 4\right\}$ (by extension).
• Membership: If an object $a$ is in a set $C$ we denote it as $a \in C$ . In the example above, $4 \in C$ and $5 \notin C$ .
• Operations: Let $A$ , $B$ be two sets.
  • Union: The union of $A$ and $B$ , denoted as $A \cup B$ , is defined as the set of those elements that are in $A$ or are in $B$ . This is, $A \cup B = \left\{ x : (x \in A) \vee (x \in B) \right\}$ .
  • Intersection: The intersection of $A$ and $B$ , denoted as $A \cap B$ , is defined as the set of those elements that are in both $A$ and $B$ . This is, $A \cap B = \left\{ x : (x \in A) \wedge (x \in B) \right\}$ .
  • Difference: The difference of $A$ and $B$, denoted as A-B , is defined as the set of those elements that are members of $A$ but are not members of $B$.
  • Cartesian product: The cartesian product of A and B, denoted as , is defined as the set of all possible ordered pairs whose first component is a member of A and whose second component is a member of B .

     

• Relations: Let $A$ , $B$ be two sets.
  • Inclusion: We say that $A$ is included in $B$ (or that $A$ is a subset of $B$ ) if every element that is in $A$ is also in $B$ , and we denote it as $A \subseteq B$ . This is, $A \subseteq B \Leftrightarrow \left\{ \forall_{x} : (x \in A) \Rightarrow (x \in B) \right\}$ .

Project Detail

Write a program that, given two sets $A$ and $B$ , and an operation/relation, will perform the operation on or determine the relation between the two sets. Although a set can theoretically hold any kind of element, for this project you can assume that the elements of the sets will be integers.

Input

Your program must prompt an interface for the user. It should be like this:

***************Set Calculation*********************
Options:
A. Input Set A
B. Input Set B
C. Cartesian product
D. Difference
I. Inclusion
U. Union
N. Intersection
H. Help
Q. Quit
***************************************************

Then, the user will be able to choose an option from these 9 options (A, B, C, D, I, U, N, H, Q). Invalid inputs should be detected and prompt a warning message -- "Invalid option!". By selecting option
A and option B, the user should be able to input the set A and set B. Since each element in these two sets should be an interger. Invalid input should also be detected and under this condition, the content of the corresponding set should be set to empty.

If the operation is Union, Intersection, or Difference, you have to print the resulting set in an ascending order when the operation is applied on $A$ and $B$ . If the operation is Cartesian product, you should print the corresponding results in an ascending order with respect to A and B. If the relation is Inclusion, then you have to print TRUE if $A \subseteq B$ , and FALSE otherwise.

It is possible that the input sets $A$ and $B$ may have repeated elements. For example, the following set is allowed: A={23, 56, 87, 23}. It may be the case that there are elements in $A$ that are also in $B$ . For example, $A = \left\{ 3, 6, 8, 9 \right\}$ and $B = \left\{ 5, 3, 4 \right\}$ . However, the output of your program cannot have any repeated element. So, in this case, the union of the two sets is , but should not be: . It may be possible that A={23, 23}, and B={23, 76}. Then, if the user choose I(Inclusion), the program should prompt "Yes. Set A is included in Set B.".

You can assume that the integers in a set will range from 0 to $999$ , and you can also assume that the largest number of elements in A or B is 50.

Example Input (The lines marked in red denote the user input):

lore 10 % ls
Makefile project3.c
lore 11 % make
gcc project3.c -o project3.out
lore 12 % project3.out
***************Set Calculation*********************
  Options:
  A. Input Set A
  B. Input Set B
  C. Cartesian product
  D. Difference
  I. Inclusion
  U. Union
  N. Intersection
  H. Help
  Q. Quit
*************************************************** 

Please choose an option:
A
Please input Set A
23 46 98 79 23 46
Please choose an option:
B
Please input set B
90 23 76 13 65 43 46
Please choose an option:
C
The cartesian product of A and B is:
(23, 13) (23, 23) (23, 43) (23, 46) (23, 65) (23, 76) (23, 90) (46, 13) (46, 23) (46, 43) (46, 46) (46, 65) (46, 76) (46, 90) (79, 13) (79, 23) (79, 43) (79, 46) (79, 65) (79, 76) (79, 90) (98, 13) (98, 23) (98, 43) (98, 46) (98, 65) (98, 76) (98, 90)
Please choose an option:
U
A U B equals: 
13 23 43 46 65 76 79 90 98
Please choose an option:
N
A N B equals: 23 46
Please choose an option:
D
A - B equals: 79 98
Please choose an option:
I
No. Set A is not included in Set B
Please choose an option:
H
***************Set Calculation*********************
Options:
A. Input Set A
B. Input Set B
C. Cartesian product
D. Difference
I. Inclusion 
U. Union
N. Intersection
H. Help
Q. Quit
*************************************************** 
Please choose an option:
A
Please input set A
23 76 23
Please choose an option:
B
Please input set B
87 we3
Invalid Input!
Please choose an option:
U
A U B equals: 23 76
Please choose an option:
B
Please input set B
90 65 23 76 98 98
Please choose an option:
I
Yes. Set A is included in Set B
Please choose an option:
W
Invalide Option!
Please choose an option:
Q
lore 12 %

Tips and Hints

• Again, you are only allowed to use the getchar() function to get the input.
• You can NOT use the array subscripting operator [] in any part of your program. Using such operation will automatically result in a 0 mark. For instance, you can NOT use this operator when you are storing the elements of the input sets to their corresponding arrays, and also not when you are calculating the operations/relations on the sets. Use pointer arithmetics instead.
• You can use the Bubble Sort to sort the results.
• You can use malloc(), free() to deal with the memory manipulation. But please don't forget to release the memory space after you do not want to use it.
• You may find memcpy() and memset() useful.

Turnin

When you are satisfied that your program works correctly (or you run out of time), please do the following.

1. Create a directory named project3

2. Copy all program files ( *.c and *.h ) and your Makefile to the directory created in step 1.

3. Goto the parent directory of project3 and type the following command into the terminal:

   turnin -c cs240=XXXX -p project3 project3

   where XXXX represents your lab section number.

   The turnin section should be as follows:

   Section	Time	TA
   0201	Thursday 15:30-17:20	Dan Zhang
   0301	Friday 09:30-11:20	Suli Xi
   0401	Friday 13:30-15:20	Youhan Fang
   0501	Thursday 09:30-11:20	J.C.Chin

   Make sure turnin reports that your project was submitted for grading. You can check the files you have submitted by running the following command:

   turnin -c cs240=XXXX -v -p project3

4. Submit often to make sure that you did not try to submit after turnin has been turned off.

Grading Breakdown

5 points	Makefile created and submitted
5 points	Program can quit successfully
10 points	Interface, Error Detection
80 points	10 test cases