CS1101C Lab 4 (Even Week)

Set Intersection

The name of your C program file must be called setintersect.c, files with any other name will not be marked.

Background

Look at the following set:

A = {0, 5, 17}

A is a set containing three elements: 0, 5, and 17.

Consider another set:

B = {5, 17, 0}

We say that B = A because the order of the elements in the set does not matter.

Consider a third set:

C = {5, 0, 17, 0, 5, 5, 0}

We ignore all duplicate elements in a set. Since the order of elements in the set does not matter, A = B = C.

For the purposes of this lab, when we display a set, we want to display the set with duplicate elements removed, and sorted in ascending order. That means the correct way to display the above equivalent sets is shown in set A.

Objective

It is possible to have an empty set, i.e. a set with no elements. This is denoted by {}.

The number of elements in a set is the number of unique members in a set.

Using "N" for intersect:

{1, 2, 3} N {4, 5, 6} = {}

{1, 2, 3} N {3, 4, 5} = {3}

{1, 2, 3} N {} = {}

{5, 3, 53, 64, 83, 2, 3, 9, 64, 3, 51} N {4, 1, 3, 83, 10, 6} = {3, 83}

Data File

The name of the data file is always sets2.txt. The following is a sample data file:

5 3 53 64 83 2 3 9 64 3 51 -1
4 1 3 83 10 6 -1

Each set contains zero or more non-negative integers. The end of a set is indicated by a negative number. You may assume that the maximum possible size of A and B is 100 elements each. What is the maximum possible size of set C? Remember to cater for empty sets.

The following is the sample output for the above sample input file. Follow it precisely else marks will be deducted.

Number of elements in A: 8
A = {2, 3, 5, 9, 51, 53, 64, 83}

Number of elements in B: 6
B = {1, 3, 4, 6, 10, 83}

C = A intersect B.

Number of elements in C: 2
C = {3, 83}

The above is only a sample data file. Your program must work for different data files.

Take Note

• For simplicity, we assume that the data file has no errors and contains only integers in the range of -1000000 to 1000000 inclusive.
• Do not use any two-dimensional arrays in your program. One-dimensional arrays are fine; in fact, you are required to use one-dimensional arrays.
• Be very careful with array index out-of-bounds errors. The compiler will not notify you of such problems; you may get the run-time errors "Segmentation Fault", "Bus Error", or other strange logic errors. Understand exactly what your code is doing before compiling!
• Plan your program carefully, using well thought-out functions to complete smaller tasks. Your main function should not be too long.

A total of 7 different hosts have accessed this document in the last 445 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 10 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.