Develop and test a program that implements the bad microchip problem and a simul
ID: 3740023 • Letter: D
Question
Develop and test a program that implements the bad microchip problem and a simulation based upon probability distributions.
For the first part, the idea is that some batches of chips might not be tested. and the goal is to detect bad batches without testing all the chips in the batch. We will be simulating the process of sampling chips from a collection of batches of chips.
Part 1a: Generate data sets.
Automate creation of what would otherwise be user-specified number of datasets with a user-specified number of batches, batch size, percentage of the datasets containing bad chips, and percentage of bad chips in a dataset.
When the program runs, it will automatically read four (4) configuration files titled c1.txt, c2.txt, c3.txt, and c4.txt, containing specs for each run, simulating how the program would work if it were getting these parameters interactively from the user. These configuration files should have the following values written as integers, one per row:
Generate a dataset from the input specification. The dataset will contain an individual file for each batch of items. Save each file in the dataset as ds1.txt, ds2.txt, ... , dsn.txt. To create an individual file, decide if it has bad items or not. Run a loop for the number of items in the batch. If it is a good batch, just write 'g' to the file (one per line) for the total number of items in the batch. If it is a bad batch, use a random number generator for the input-specified percentage of bad chips: Example - assume the spec is that 10% of chips are bad. Generate datasets by generating random numbers on [0..99] if 0 .. 9 comes up, add a bad chip (write the char 'b' to the file), otherwise, add a good chip to the data set (write a 'g' to the file).
Part 1b: Create the Monte Carlo process to determine which of the chip batches are bad. It should know how many data sets there are, read them one at a time, sample the appropriate number of items, and report good batch or bad batch. Your output should look like the output below. Create a summary report detailing the
Example output:
Running:
Number of batches of items: 100
Number of items in each batch 2000
Percentage of batches containing bad items 24%
Percentage of items that are bad in a bad set 7%
Items sampled from each set 30
Generating data sets:
Create bad set batch # 4, totBad = 133 total = 2000 badpct = 7
Create bad set batch # 8, totBad = 145 total = 2000 badpct = 7
Create bad set batch # 12, totBad = 122 total = 2000 badpct = 7
Create bad set batch # 16, totBad = 142 total = 2000 badpct = 7
Create bad set batch # 20, totBad = 160 total = 2000 badpct = 7
Create bad set batch # 24, totBad = 148 total = 2000 badpct = 7
Create bad set batch # 28, totBad = 166 total = 2000 badpct = 7
Create bad set batch # 32, totBad = 137 total = 2000 badpct = 7
Create bad set batch # 36, totBad = 145 total = 2000 badpct = 7
Create bad set batch # 40, totBad = 123 total = 2000 badpct = 7
Create bad set batch # 44, totBad = 123 total = 2000 badpct = 7
Create bad set batch # 48, totBad = 165 total = 2000 badpct = 7
Create bad set batch # 52, totBad = 142 total = 2000 badpct = 7
Create bad set batch # 56, totBad = 117 total = 2000 badpct = 7
Create bad set batch # 60, totBad = 144 total = 2000 badpct = 7
Create bad set batch # 64, totBad = 124 total = 2000 badpct = 7
Create bad set batch # 68, totBad = 152 total = 2000 badpct = 7
Create bad set batch # 72, totBad = 120 total = 2000 badpct = 7
Create bad set batch # 76, totBad = 141 total = 2000 badpct = 7
Create bad set batch # 80, totBad = 158 total = 2000 badpct = 7
Create bad set batch # 84, totBad = 119 total = 2000 badpct = 7
Create bad set batch # 88, totBad = 144 total = 2000 badpct = 7
Create bad set batch # 92, totBad = 145 total = 2000 badpct = 7
Create bad set batch # 96, totBad = 158 total = 2000 badpct = 7
Total bad sets = 24
Analyzing Data Sets:
batch #0 is bad
batch #4 is bad
batch #12 is bad
batch #16 is bad
batch #20 is bad
batch #24 is bad
batch #28 is bad
batch #32 is bad
batch #36 is bad
batch #40 is bad
batch #44 is bad
batch #48 is bad
batch #52 is bad
batch #60 is bad
batch #64 is bad
batch #68 is bad
batch #72 is bad
batch #76 is bad
batch #80 is bad
batch #84 is bad
batch #88 is bad
batch #92 is bad
Base = 0.930000 exponent = 30
P(failure to detect bad item) = 0.113367
P(batch is good) = 0.886633
Percentage of bad batches detected = 88%
Program must in C language
Specification c1.txt c2.txt c3.txt c4.txt Number of batches of items 100 100 500 500 Number of items in each batch 2000 2000 1000 1000 Percentage of batches containing bad items 24 10 10 1 Percentage of items that are bad in a bad batch 7 10 10 1 Items sampled from each batch 30 50 50 50Explanation / Answer
C language program:
For main
#include<stdio.h>
#include"monteCarlo.h"
int main(void)
{
char cond;
printf("Would you like to convert SimParameters.txt to a binary file? (y/n)");
scanf(" %c", &cond);
if(cond == 'Y' || cond == 'y')
{
txt2Binary();
}
while(1)
{
printf(" "
" Option Choice "
" 1 Implement a Monte Carlo Simulation "
" 2 Implement a Simple Monte Carlo Algorithm "
" 3 Exit Program "
" "
"Please enter an Option: ");
scanf(" %c", &cond);
switch(cond)
{
case '1':
MCSimulation();
break;
case '2':
MCAlgorithm();
break;
case '3':
return 0;
default:
printf("Invalid Option ");
break;
}
}
return 0;
}
For Monte Carlo
#include"monte Carlo.h"
void txt2Binary(void)
{
int i;
FILE *fp = fopen("SimParameters.txt", "r");
FILE *fp2 = fopen("SimParameters.dat", "wb");
while(fp && fscanf(fp, "%d", &i) != EOF )
{
fwrite(&i, sizeof(int),1, fp2);
}
fclose(fp);
fclose(fp2);
}
void MCSimulation(void)
{
int i, j;
int numSim, numCat, numEvent;
int *freqlist = NULL;
FILE *fp;
fp = fopen("SimParameters.dat", "rb");
if(!fp)
{
printf("Unable to open SimParameters.dat!");
exit(1);
}
fread(&numSim, sizeof(int), 1, fp);
for(i = 0; i < numSim; i++)
{
fread(&numCat, sizeof(int), 1 , fp);
freqlist = (int *)realloc(freqlist, numCat * sizeof(int));
for(j = 0; j < numCat; j++)
{
fread(freqlist + j, sizeof(int), 1, fp);
}
fread(&numEvent, sizeof(int), 1, fp);
printf(" Simulation %d ", i+1);
runMCSim(numCat, freqlist, numEvent);
}
fclose(fp);
}
void runMCSim(int numCategories, int frequencyList[], int numEvents)
{
int i;
double expectation = calExpectation(numCategories, frequencyList);
double simExpectation;
int sumFrequencies = 0;
int sumRandEvents = 0;
for(i = 0; i < numCategories; i++)
{
sumFrequencies = sumFrequencies + frequencyList[i];
frequencyList[i] = sumFrequencies;
}
for(i = 0; i < numEvents; i++)
{
sumRandEvents = sumRandEvents + generateRandEvent(numCategories, frequencyList);
}
simExpectation = (double)sumRandEvents/ (double)numEvents;
printSimResults(numEvents, simExpectation, expectation);
}
double calExpectation(int numCategories, int frequencyList[])
{
int i;
double expectation = 0;
int sumFrequencies = 0;
for(i = 0; i< numCategories; i++)
{
sumFrequencies = sumFrequencies + frequencyList[i];
}
for(i = 0; i < numCategories; i++)
{
expectation = expectation + (double)i * (double)(frequencyList[i])/ (double)(sumFrequencies);
}
return expectation;
}
int generateRandEvent(int numCategories, int intervalList[])
{
srand(time(CLOCK_REALTIME));
int i = 0;
int randNum = rand() % intervalList[numCategories - 1];
while(randNum > intervalList[i] && i < numCategories - 1)
{
i++;
}
return i;
}
void printSimResults(int numEvents, double simResult, double expectedResult)
{
double error = (simResult - expectedResult)/expectedResult * 100.0;
if(error < 0)
error = error * -1;
printf(" "
"N: %d "
"Simulated result: %.2lf "
"Expected value: %.2lf "
"Error percent: %.3lf ",
numEvents, simResult, expectedResult, error );
}
void MCAlgorithm(void)
{
int i;
DataSet dataArray[4];
FILE *fp;
char filename[16];
for(i = 0; i < 4; i++)
{
snprintf(filename, sizeof(filename), "filename.txt", i + 1 );
fp = fopen(filename, "r");
readConfig(&dataArray[i], fp);
fclose(fp);
generateDataSets(&dataArray[i]);
//analyzeDataSets(&dataArray[i]);
}
printSummary(dataArray, 4);
}
void readConfig(DataSet *data, FILE *fp)
{
fscanf(fp, "%d", &data->numBatches);
fscanf(fp, "%d", &data->numItems);
fscanf(fp, "%d", &data->perBadBatch);
fscanf(fp, "%d", &data->perBadItem);
fscanf(fp, "%d", &data->sampledItems);
printf("Running: "
" Number of Batches of Items: %4d "
" Number of Items in Each Batch: %4d "
" Percentage of Batches Containing Bad Items: %4d%% "
" Percentage of Items that are bad in a bad set: %4d%% "
" Items Sampled from Each Set: %4d ",
data->numBatches, data->numItems, data->perBadBatch,
data->perBadItem, data->sampledItems);
}
void generateDataSets(DataSet *data)
{
srand(time(NULL));
int i, j;
int randNum;
int badItemCount = 0;//, badBatchCount= 0;
data->simBadBatches = 0;
char filename[32];
FILE *fp;
printf(" "
"Generating Data Sets: ");
for(i = 1; i <= data->numBatches; i++)
{
randNum = rand()%100;
badItemCount = 0;
snprintf(filename, sizeof(filename), "filename.txt", i);
fp = fopen(filename, "w");
if(randNum < data->perBadBatch)//Bad Batch
{
data->simBadBatches++;
for(j = 0; j< data->numItems; j++)
{
randNum = rand()%100;
if(randNum < data->perBadItem) //Bad Item
{
badItemCount++;
fprintf(fp, "b ");
}
else
{
fprintf(fp, "g ");
}
}
printf(" Create Bad Set Batch #%3d, totBad = %4d Total = %5d PercentBad = %.2lf ",
i, badItemCount, data->numItems,
(double)badItemCount/ (double)data->numItems * 100.0);
}
else
{
for(j = 0; j < data->numItems; j++)
{
fprintf(fp, "g ");
}
}
fclose(fp);
}
printf("Total Bad Sets = %3d ", data->simBadBatches);
}
void analyzeDataSets(DataSet *data)
{
data->simBadBatchesDet = 0;
int i, j;
FILE *fp;
char filename[32];
char tmp;
srand(CLOCK_REALTIME);
int randNum;
printf("Analyzing Data Sets: ");
for(i = 0; i < data->numBatches; i++)
{
snprintf(filename, sizeof(filename), "filename.txt", i + 1);
fp = fopen(filename, "r");
for(j = 0; j < data->sampledItems; j++)
{
do
{
randNum = rand() % (data->numItems ); //Multiply by 2 to compensate for newline characters
fseek(fp, randNum * sizeof(char), SEEK_SET);
fread(&tmp, sizeof(char), 1, fp );
}while(tmp == ' ');
if(tmp == 'b')
{
data->simBadBatchesDet++;
printf(" Batch #%3d is Bad ", i + 1);
}
}
}
}
void printSummary(DataSet *data, int size )
{
int i;
double PF;
for(i = 0; i < size; i++)
{
PF = pow(1.0 -(double)(data + i)->perBadItem / 100.0,(data + i)->sampledItems );
printf(" "
"Run %d: "
"Number of Batches of Items: %4d "
"Number of Items in Each Batch: %4d "
"Percentage of Batches Containing Bad Items: %4d "
"Percentage of Items that are Bad in a Bad Set: %4d "
"Items Sampled from Each Set: %4d "
"Base = %.2lf Exponent = %d "
"P(Failure to Detect Bad Item) = %lf "
"P(Batch is Good) = %lf "
"Percentage of Bad Batches Detected = %d%% ",
i, (data + i)->numBatches, (data + i)->numItems, (data + i)->perBadBatch,
(data + i)->perBadItem, (data + i)->sampledItems,
1.0 -(double)(data + i)->perBadItem, (data + i)->sampledItems,
PF, 1.0 - PF, (data +i)->simBadBatchesDet);
}
}
For Monte Carlo.h
#ifndef MONTECARLO_H_
#define MONTECARLO_H_
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<unistd.h>
#include<sys/wait.h>
#include<math.h>
typedef struct Data {
int numBatches;
int numItems;
int perBadBatch;
int perBadItem;
int sampledItems;
int simBadBatches;
int simBadBatchesDet;
}DataSet;
void txt2Binary(void);
void MCSimulation(void);
void runMCSim(int numCategories, int frequencyList[], int numEvents);
double calExpectation(int numCategories, int frequencyList[]);
int generateRandEvent(int numCategories, int intervalList[]);
void printSimResults(int numEvents, double simResult, double expectedResult);
void MCAlgorithm(void);
void readConfig(DataSet *data, FILE *fp);
void generateDataSets(DataSet *data);
void analyzeDataSets(DataSet *data);
void printSummary(DataSet *data, int size );
#endif /* MONTECARLO_H_ */.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.