340 Intermediate C Programming
{29
printf (" %d n" , kval );30
int ind ;31
for ( ind = 0; ind < num ; ind ++)32
{33
printf (" %d n" , arr [ ind ]) ;34
}35
}36
int main ( i n t argc , char ** argv )37
{38
i f ( argc < 4)39
{40
return EXIT _FAILUR E ;41
}42
int numInt = ( in t ) strtol ( argv [1] , NULL , 10) ;43
int isValid = ( in t ) strtol ( argv [2] , NULL , 10) ;44
int hasSol = ( in t ) strtol ( argv [3] , NULL , 10) ;45
i f (( numInt < 3) || ( numInt > 31) )46
{47
return EXIT _FAILUR E ;48
}49
i f (( hasSol != 0) && ( hasSol != 1) )50
{51
return EXIT _FAILUR E ;52
}53
i f (( hasSol != 0) && ( hasSol != 1) )54
{55
return EXIT _FAILUR E ;56
}57
srand ( time ( NULL )) ; // set the seed58
int kval = 0;59
int * arr = malloc ( s i z e o f ( i n t ) * numInt );60
int ind ;61
// the array is increasi n g and all elem e nts are distin c t62
arr [0] = rand () % 100;63
for ( ind = 1; ind < numInt ; ind ++)64
{65
arr [ ind ] = arr [ ind - 1] + ( rand () % 10000) + 1;66
}67
i f ( isValid == 0)68
{69
i f (( rand () % 2) == 0)70
{71
// make two elements the same72
arr [ numInt - 1] = arr [0];73
}74
e l s e75
{76
// make an element negative or zero77
arr [0] = - ( rand () % 10000) ;78
}79
Parallel Programming Using Threads 341
// kval irrelevan t when the array is invalid80
kval = rand () % 10000 + 1;81
}82
e l s e83
{84
for ( ind = 0; ind < numInt ; ind ++)85
{86
i f ( hasSol == 0)87
{88
// kval > sum of all el e ments89
kval += arr [ ind ] + 1;90
}91
e l s e92
{93
i f (( rand () % 3) == 1)94
{95
kval += arr [ ind ];96
}97
}98
}99
i f ( kval == 0) // only if hasSol is 1100
{101
kval = arr [0];102
}103
}104
shuff leArray ( arr , numInt ) ;105
printAr r ay ( arr , numInt , kval );106
free ( arr );107
return EXIT _SUCCES S ;108
}109
It is important to understand the value of a test generator. Writing test generators is
often necessary. Creating test cases by hand is really too much work. The main problem of
hand-generated tests is that only a few cases can be produced. As a result, the tests often
miss some important cases.
21.4.2 Sequential Solution
One obvious solution to the subset sum problem is to enumerate each subset of A and
then check each to see if the sum of the elements is k. This will take exponential time since
a set of size n has 2
n
subsets. The number of possible subsets becomes really large. For
example, a set of size 400 has 2
400
subsets; this is more than the number of atoms in the
observable universe.
There is no known “quick” way of solving the subset sum problem. In computer science,
“quick” usually means that there is a polynomial-time algorithm that solves the problem. A
polynomial-time algorithm is an algorithm whose execution time is bounded by a polynomial
function of the input size. For example, if we are searching a linked list for a given value,
then we may need to traverse the entire list. If the list has n elements (the input data) then
the execution time of the search is bounded by a polynomial function of n. For a polynomial
of degree p, the largest term is n
p
. For any constant p > 1, the following statement is true:
342 Intermediate C Programming
lim
n→∞
2
n
n
p
= ∞. (21.1)
This means that the exponential function eventually grows faster than any polynomial.
There is always a value of n such that 2
n
is larger than n
p
, no matter what p is. This can
be proved by using the L’Hospital’s Rule from calculus.
This section asks you to write a program that counts the number of subsets whose sums
are equal to the given value k. Instead of finding a sophisticated algorithm, the section uses
a simple solution that enumerates all subsets (excluding the empty set). The program must
read the value of k and then the set’s elements from a file. After reading the data from the
file, the program checks whether the set is valid. The set is invalid if any element is zero
or negative, or if two elements have the same value. If the set is invalid, then the program
does not attempt to solve the subset sum problem.
If the set is valid, then the program generates all possible subsets of the given set. This
program first calculates the number of possible subsets. If a set has n elements, then there
are 2
n
subsets including the empty set. If each subset is given a number, then the subsets
are numbers between 0 and 2
n
− 1 inclusively. The empty set is not considered because
k 6= 0, and thus we only need to consider the subsets labeled 1 to 2
n
− 1. Note that since
each number corresponds to a subset, and we will check to total sum of the numbers in that
subset, we have each number corresponding to a subset sum. The following table explains
how the numbers are related to the subset sums:
Value Sum
1 a
1
2 a
2
3 a
1
+ a
2
4 a
3
5 a
1
+ a
3
6 a
2
+ a
3
7 a
1
+ a
2
+ a
3
8 a
4
.
.
.
.
.
.
2
n
− 1 a
1
+ a
2
+ a
3
+ ... + a
n
The test generator is restricted to at most 31 elements so that 2
n
can fit in a four-byte
integer. This following is a sample implementation of the sequential program as described
above. First is the main function:
// main . c1
#in clude < pthread .h >2
#in clude < stdio .h >3
#in clude < stdlib .h >4
#in clude " subset s um .h "5
int main ( i n t argc , char * argv [])6
{7
// read the data from a file8
i f ( argc < 2)9
{10
printf (" Need input file name n" );11
return EXIT _FAILUR E ;12
}13
FILE * fptr = fopen ( argv [1] , "r ");14
Parallel Programming Using Threads 343
i f ( fptr == NULL )15
{16
printf (" fopen fail n ");17
return EXIT _FAILUR E ;18
}19
int numInt = cou ntIntege r ( fptr );20
// go back to the beginning of the file21
fseek ( fptr , 0 , SEEK_SET );22
int kval ; // the value equal to the sum23
i f ( fscanf ( fptr , " %d " , & kval ) != 1)24
{25
printf (" fscanf error n ");26
fclose ( fptr );27
return EXIT _FAILUR E ;28
}29
numInt - -; // kval is not part of the set30
int * setA = malloc ( s i z e o f ( i n t ) * numInt );31
int ind = 0;32
for ( ind = 0; ind < numInt ; ind ++)33
{34
int aval ;35
i f ( fscanf ( fptr , " %d " , & aval ) != 1)36
{37
printf (" fscanf error n ");38
fclose ( fptr );39
return EXIT _FAILUR E ;40
}41
setA [ ind ] = aval ;42
}43
fclose ( fptr );44
i f ( isV alidSet ( setA , numInt ) == 1)45
{46
printf (" There are %d subsets whose sums are % d n" ,47
subsetSum ( setA , numInt , kval ) , kval );48
}49
e l s e50
{51
printf (" Invalid set n" );52
}53
free ( setA ) ;54
return EXIT _SUCCES S ;55
}56
This main function calls several other functions that are declared in this header file.
// subs e tsum . h1
#i f n d e f SUBSETSU M_H2
#d ef in e SUBS E TSUM_H3
#in clude < stdio .h >4
int subsetE qual ( in t * setA , i nt sizeA , int kval ,5
unsigned int code );6
// return 1 if the subset expressed by the code sums to kval7
344 Intermediate C Programming
// return 0 if the sum is d i fferent from kval8
int subsetSum ( i n t * setA , i nt sizeA , in t kval );9
// the number of subsets in setA equal10
int isValidS e t ( i n t * setA , i nt sizeA ) ;11
// valid if el e m ents are posi t i ve and distinc t12
// return 1 if valid , 0 if invalid13
int countI nteger ( FILE * fptr );14
// how many integers in a file15
// fptr must not be NULL , checked by the caller16
#e ndif17
The functions isValid and countInt should be straightforward:
// isvalid .c1
#in clude < stdio .h >2
int isValidS e t ( i n t * setA , i nt sizeA )3
// valid if every element is p o s itive and dist i nct4
// return 1 if valid , 0 if invalid5
{6
int ind1 ;7
int ind2 ;8
for ( ind1 = 0; ind1 < sizeA ; ind1 ++)9
{10
i f ( setA [ ind1 ] <= 0)11
{12
return 0;13
}14
for ( ind2 = ind1 + 1; ind2 < sizeA ; ind2 ++)15
{16
i f ( setA [ ind1 ] == setA [ ind2 ])17
{18
return 0;19
}20
}21
}22
return 1;23
}24
// countin t . c1
#in clude < stdio .h >2
int countI nteger ( FILE * fptr )3
{4
int numInt = 0; // how many integers5
int value ;6
while ( fscanf ( fptr , " %d" , & value ) == 1)7
{8
numInt ++;9
}10
return numInt ;11
}12
The function subsetSum counts the number of subsets:
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.