Intermediate C Programming

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

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

. For any constant p > 1, the following statement is true:

342 Intermediate C Programming

lim

n→∞

= ∞. (21.1)

This means that the exponential function eventually grows faster than any polynomial.

There is always a value of n such that 2

is larger than n

, 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 ﬁnding 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 ﬁle. After reading the data from the

ﬁle, 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 ﬁrst calculates the number of possible subsets. If a set has n elements, then there

are 2

subsets including the empty set. If each subset is given a number, then the subsets

are numbers between 0 and 2

− 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

− 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

2 a

3 a

+ a

4 a

5 a

+ a

6 a

+ a

7 a

+ a

8 a

− 1 a

+ a

+ ... + a

The test generator is restricted to at most 31 elements so that 2

can ﬁt 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

// 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 ﬁle.

// 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

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

int numInt = 0; // how many integers5

int value ;6

while ( fscanf ( fptr , " %d" , & value ) == 1)7

numInt ++;9

}10

return numInt ;11

}12

The function subsetSum counts the number of subsets:

Previous Chapter

21. Parallel Programming Using Threads (1/5)

Next Chapter

21. Parallel Programming Using Threads (3/5)

Table of Contents for Intermediate C Programming

Table of Contents for
Intermediate C Programming