Programming Assignment I

Due on Monday, February 11, 2019 @ 11pm

50 points

Please note the change of due date/time.

This is a warm-up simple programming assignment using only Unix system calls fork(), wait() and exit().

Running Four Independent Processes

Write a program that takes four positive integers m, n, r and s from its commend line arguments, creates four child processes, waits for them to complete, and exits. The first process computes the n-th Fibonacci number fn using recursion, the second process finds the solution of Buffon's needle problem by throwing a needle r times, the third process computes the integration of function sin(x) between 0 and π, and the fourth uses a simple expression to compute an approximation of e = 2.71828..., the Euler's number of Napier's constant. Here are the details:
  1. The n-th Fibonacci number is defined recursively as follows:
    f1 = f2 = 1
    fn = fn-1 + fn-2    if n > 2
    Use THIS recursive formula to compute the n-th Fibonacci number.
  2. The Buffon's Needle Problem. The problem was first stated by the French naturalist and mathematician George-Louis Leclerc, Comte de Buffon in 1733, and reproduced with solution by Buffon in 1777. Suppose the floor is divided into infinite number of parallel lines with a constant gap G. If we throw a needle of length L to the floor randomly, what is the probability of the needle crossing a dividing line? The answer is (2/π)*(L/G), where π is 3.1415926....

    We may use a program to simulate this needle throwing process. For simplicity, let L = G = 1.

    We need two random numbers:

    1. d, a random number in [0,1), represents the distance from one (fixed) tip of the needle to the lower dividing line.
    2. a, a random number in [0,2*π), represents the angle between the needle and a dividing line.
    Thus, if d + L×sin(a) is less than 0 or larger than G, the needle crosses a dividing line.

    In this way, your program loops r times. In each iteration, your program uses the above formula to throw a needle, and checks whether the needle crosses a dividing line. If the needle crosses a dividing line t times, t/r is an approximation of the exact probability. In fact, if r is very large, the simulated result would be very close to the exact result. In our case, since L = G = 1, the result for large r should be close to 2/π = 0.63661..... You may use acos(-1.0) to obtain the value of π.

  3. You learned in your calculus class the following integration:

    This means the area between the sin(x) function and the x-axis is 2. This area is completely enclosed in a rectangular area with length π and height 1 as shown in the figure below. The area of this rectangle is π×1 = π.

    If we randomly pick s points in the rectangle and find out t of them in the area of the sin(x) function, then the ratio t/s suggests that the area under sin(x) is t/s of the rectangle. Therefore, (t/s)×π should be close to 2. Here is what your program must do.

    1. Generate two random numbers a and b where 0 ≤ a < π and 0 ≤ b < 1. This (a,b) represents a point in the rectangle.
    2. If b ≤ sin(a), point (a,b) is in the area between sin(x) and the x-axis.
    3. Let the total number of points in the area between sin(x) and the x-axis be t.
    4. Then, (t/s)×π should be close to 2, the desired result. This is especially true for very large s.
  4. Bernoulli's Approximation of e: You perhaps learned the following from your calculus course:

    In this component, you are to write a program to find the value of e based on the above formula. This is a simple program. You just follow the steps below:

    1. Let n be the highest possible of exponent to be used.
    2. Let i start with 1 and be doubled in every iteration. For each i use the expression below to calculate an approximation of e:

      However, your program must print the results of the first 10 values for i = 1, 2, 3, ..., 10. Therefore, the possible values of i should be 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 32, 64, 128, 256, ....

    3. If the current valus of i is larger than n, this loop stops.

Program Specification

Write a program prog1.c in C to perform the following tasks
  1. It reads in four command line arguments and converts them to four integers. This means prog1.c is run with the following command line
    ./prog1 m n r s
    where m, n, r and s are four positive integers. You can only assume that your program will be compiled in the C89 standard.
  2. Then, the main program forks four child processes, waits for their completion, and exits.
  3. The first child process computes the n-th Fibonacci number fn with recursion. (Yes, you must use recursion to kill time!) This process does its task in the following order:
    1. Prints the value of n
    2. Uses recursion to compute fn
    3. Prints the result.
    Use long for computation.
  4. The second child process simulates throwing a needle r times and estimates an approximation of the exact probability. This process does this simulation in the following order:
    1. Prints the value of r
    2. Iterates r times. Note that L = G = 1.
    3. Prints the computed result.
    Since rand() only generates random integers in the range from 0 to RAND_MAX, you should convert an integer random number to a real one in the range of 0 and 1 using (float rand())/RAND_MAX. If necessary, you may scale this real random number to other range. You may find the largest value of RAND_MAX on any system in C's header file <limits.h>.
  5. The third child process simulates the calculation of the integration of the sin(x) function as given earlier. This process does the following work:
    1. Prints the value of s.
    2. Iterates s times and count the number of points in the area between sin(x) and the x-axis.
    3. Prints the computed area.
  6. The fourth child process uses Bernoulli's method to compute an approximation of e. This process does the following work.
    1. Prints the value of m, the maximum exponent to be used in your computation.
    2. For each possible value of i as stated earlier, computes and possibly prints out the intermediate value using the expression below:

    Use double precision for the computation of e.

You must use recursion to compute fn. Moreover, the parent and its four child processes must run concurrently. Violating these rules you will receive zero point for this programming assignment.

Input and Output

The input to your program should be taken from command line arguments. Your source program must be named as prog1.c. The command line looks like the following:
./prog1  m n r s
Here, m, n, r and s are four positive integers. There are always four arguments and they are always correct. Moreover, m, r and s are usually very large.

Suppose the command line is

./prog1  73000000000000000 10 100000 200000
Then, your program should (1) compute the 10-th Fibonacci number, (2) simulate throwing a needle 100000 times, (3) use 200000 points to compute the area between the sin(x) function and the x-axis in the range of 0 and π. and (4) use 73000000000000000 as the maximum possible exponent in the computation of Euler's number.

The Fibonacci process should have its output as follows:

Fibonacci Process Started
Input Number 10
Fibonacci Number f(10) is 55
Fibonacci Process Exits
All output from this process starts on column 7 (i.e., 6 leading spaces). Since the computed Fibonacci number may be very large, use %ld to print the computed result.

The Buffon's Needle process should have its output as follows:

Buffon's Needle Process Started
Input Number 100000
Estimated Probability is 0.63607
Buffon's Needle Process Exits
Since the output value is always in the range of 0 and 1, use 5 positions after the decimal point for printing. All output from this process starts on column 10 (i.e., 9 leading spaces).

The integration (i.e. third) process should have its output as follows:

Integration Process Started
Input Number 200000
Total Hit 127498
Estimated Area is 2.0027339
Integration Process Exits
All output from this process starts on column 13 (i.e., 12 leading spaces).

Note that the results of Buffon's Needle problem and the integration problem may be slightly different from the output shown here even with the same r and s because random numbers are used.

The Euler's number computation process should have its output as follows:

Approximation of e Process Started
Maximum of the Exponent 73000000000000000
                   1    2.000000000000000    0.718281828459045
                   2    2.250000000000000    0.468281828459045
                   3    2.370370370370370    0.347911458088675
                   4    2.441406250000000    0.276875578459045
                   5    2.488319999999999    0.229961828459046
                   6    2.521626371742113    0.196655456716932
                   7    2.546499697040712    0.171782131418333
                   8    2.565784513950348    0.152497314508697
                   9    2.581174791713198    0.137107036745847
                  10    2.593742460100002    0.124539368359043
                  16    2.637928497366600    0.080353331092445
                  32    2.676990129378183    0.041291699080862
                  64    2.697344952565099    0.020936875893946
                 128    2.707739019688021    0.010542808771024
                 256    2.712991624253434    0.005290204205611
                 512    2.715632000168991    0.002649828290054
                1024    2.716955729466436    0.001326098992609
                2048    2.717618482336880    0.000663346122165
                4096    2.717950081189666    0.000331747269379
                8192    2.718115936265797    0.000165892193248
               16384    2.718198877721971    0.000082950737074
               32768    2.718240351930294    0.000041476528751
               65536    2.718261089904603    0.000020738554442
              131072    2.718271459109306    0.000010369349739
              262144    2.718276643766046    0.000005184692999
              524288    2.718279236108013    0.000002592351032
             1048576    2.718280532282396    0.000001296176649
             2097152    2.718281180370437    0.000000648088608
             4194304    2.718281504414671    0.000000324044374
             8388608    2.718281666436840    0.000000162022205
            16777216    2.718281747447938    0.000000081011107
            33554432    2.718281787953491    0.000000040505554
            67108864    2.718281808206268    0.000000020252777
           134217728    2.718281818332656    0.000000010126389
           268435456    2.718281823395851    0.000000005063194
           536870912    2.718281825927448    0.000000002531597
          1073741824    2.718281827193247    0.000000001265799
          2147483648    2.718281827826146    0.000000000632899
          4294967296    2.718281828142596    0.000000000316450
          8589934592    2.718281828300821    0.000000000158225
         17179869184    2.718281828379933    0.000000000079112
         34359738368    2.718281828419489    0.000000000039556
         68719476736    2.718281828439267    0.000000000019778
        137438953472    2.718281828449156    0.000000000009889
        274877906944    2.718281828454101    0.000000000004944
        549755813888    2.718281828456573    0.000000000002472
       1099511627776    2.718281828457809    0.000000000001236
       2199023255552    2.718281828458427    0.000000000000618
       4398046511104    2.718281828458736    0.000000000000309
       8796093022208    2.718281828458891    0.000000000000155
      17592186044416    2.718281828458968    0.000000000000077
      35184372088832    2.718281828459006    0.000000000000039
      70368744177664    2.718281828459026    0.000000000000019
     140737488355328    2.718281828459036    0.000000000000009
     281474976710656    2.718281828459040    0.000000000000005
     562949953421312    2.718281828459043    0.000000000000002
    1125899906842624    2.718281828459044    0.000000000000001
    2251799813685248    2.718281828459045    0.000000000000000
    4503599627370496    2.718281828459045    0.000000000000000
    9007199254740992    1.000000000000000    1.718281828459045
   18014398509481984    1.000000000000000    1.718281828459045
   36028797018963968    1.000000000000000    1.718281828459045
   72057594037927936    1.000000000000000    1.718281828459045
All output from this process starts on column 4 (i.e., 3 leading spaces).

The first column shows the value of i, the second has the value of (1+1/i)i, and the third shows the absolute difference between the calculated value of e and the actual value of e. You can always get a true value of e with the C math function exp(1.0) The above sample output has m being 73000000000000000. Because the value of n can be very large, the first column used %18lu, meaning n is a unsigned long integer. The second and third columns should allow the printing of at least 7 to 15 digits, meaning floating point calculations are done in double. You may use your own format, but keep in mind that the output must be readable as shown above. You may find the largest value of unsigned long on any system in C's header file <limits.h>.

If you examine the above result, you should be able to see that the approximation is getting closer to 2.71828 with a small error. However, the approximation number suddenly dropped to 1. Why is this problem? Be prepared to answer this in your README.

The main program should print the following output:

Main Process Started
Fibonacci Number 10
Buffon's Needle Iterations = 100000
Integration Iterations     = 200000
Approx. e Iterations       = 73000000000000000
Fibonacci Process Created
Buffon's Needle Process Created
Integration Process Created
Approximation of e Process Created
Main Process Waits
Main Process Exits
All output line from the main process should start on column 1 (i.e., no leading spaces).

It is very important to remember the following.

All processes must run concurrently and may print their output lines in an unpredictable order. As a result, the output lines from a process may mix with output lines from other processes. This is the reason that proper indentation is required to know who prints what. Also make sure that each line will not contain the output from different processes.

Submission Guidelines

General Rules

  1. All programs must be written in C.
  2. Use the submit command to submit your work. You may submit as many times as you want, but only the last on-time one will be graded.
  3. Your program should be named as prog1.c. Since Unix filename is case sensitive, PROG1.c, prog1.C, pROG1.c, etc are not acceptable.
  4. We will use the following approach to compile and test your programs:
    gcc  prog1.c -lm -o prog1                    <-- compile your program
    ./prog1 73000000000000000 10 100000 200000   <-- test your program
    
    This procedure may be repeated a number of times with different input to see if your program works correctly.

    You must use the above command lines to compile and run your program. Otherwise, our grader may not be able to grade your program, and you will risk a low or even a 0 score.

    By default, CS lab machines use C89, and our grader uses C89 for grading. Therefore, if you use C90 to write this program, your program may not compile using CS lab machines. If this happens, you will receive a 0 because your program does not compile.

  5. Your implementation should fulfill the program specification as stated. Any deviation from the specification will cause you to receive zero point.
  6. A README file is always required.
  7. No late submission will be graded.
  8. Programs submitted to wrong class and/or wrong section will not be graded.

Compiling and Running Your Programs

This is about the way of compiling and running your program. If we cannot compile your program due to any syntax errors, wrong file names, etc, we cannot test your program, and, as a result, you receive 0 point. If your program compiles successfully but fails to run, we cannot test your program, and, again, you receive 0 point. Therefore, before submitting your work, make sure your program can compile and run properly.
  1. Not-compile programs receive 0 point. By not-compile, I mean any reason that could cause an unsuccessful compilation, including missing files, incorrect filenames, syntax errors in your programs, and so on. Double check your files before you submit, since I will not change your program. Note again: Unix filenames are case sensitive.
  2. Compile-but-not-run programs receive 0 point. Compile-but-not-run usually means you have attempted to solve the problem to some degree but you failed to make it working properly.
  3. A meaningless or vague program receives 0 point even though it compiles successfully. This usually means your program does not solve the problem but serves as a placeholder or template just making it to compile and run.

Program Style and Documentation

This section is about program style and documentation.
  1. For each file, the first piece should be a program header to identify yourself like this:
    /* ----------------------------------------------------------- */
    /* NAME : John Smith                         User ID: xxxxxxxx */
    /* DUE DATE : mm/dd/yyyy                                       */
    /* PROGRAM ASSIGNMENT #                                        */
    /* FILE NAME : xxxx.yyyy.zzzz (your unix file name)            */
    /* PROGRAM PURPOSE :                                           */
    /*    A couple of lines describing your program briefly        */
    /* ----------------------------------------------------------- */
    

    Here, User ID is the one you use to login. It is not your social security number nor your M number.

    For each function in your program, include a simple description like this:

    /* ----------------------------------------------------------- */
    /* FUNCTION  xxyyzz : (function name)                          */
    /*     the purpose of this function                            */
    /* PARAMETER USAGE :                                           */
    /*    a list of all parameters and their meaning               */
    /* FUNCTION CALLED :                                           */
    /*    a list of functions that are called by this one          */
    /* ----------------------------------------------------------- */
    
  2. Your programs must contain enough concise and to-the-point comments. Do not write a novel!
  3. Your program should have good indentation.
  4. Do not use global variables!

Program Specification

Your program must follow exactly the requirements of this programming assignment. Otherwise, you receive 0 point even though your program runs and produces correct output. The following is a list of potential problems.
  1. Your program does not use the indicated algorithms/methods to solve this problem.
  2. Your program does not follow the structure given in the specification. For example, your program is not divided into functions and files, etc when the specification says you should.
  3. Any other significant violation of the given program specification.
  4. Incorrect output format. This will cost you some points depending on how serious the violations are. The grader will make a decision. Hence, carefully check your program output against the required one.

Program Correctness

If your program compiles and runs, we will check its correctness. We will run your program with at least two sets of input data, one posted on this programming assignment page (the public one) and the other prepared by the grader (the private ones). You program must deliver correct results for all data sets to be considered as a correct one. Depending on the seriousness of the problem(s), significant deduction may be applied. For example, if your program delivers all wrong results for the public data set, you receive 0 point for that component.

The README File

A file named README is required to answer the following questions:
  1. Question: Draw a diagram showing the parent-child relationship if the following program is run with command line argument 4. How many processes are created? Explain step-by-step how these processes are created, especially who is created by whom.
    void main(int argc, char **argv)
    {
         int i, n = atoi(argv[1]);
    
         for (i = 1; i < n; i++)
              if (fork())
                   break;
         printf("Process %ld with parent %ld\n", getpid(), getppid());
         sleep(1);
    }
    
  2. Question: Draw a diagram showing the parent-child relationship if the following program is run with command line argument 4. How many processes are created? Explain step-by-step how these processes are created, especially who is created by whom.
    void main(int argc, char **argv)
    {
         int i, n = atoi(argv[1]);
    
         for (i = 0; i < n; i++)
              if (fork() <= 0)
                   break;
         printf("Process %ld with parent %ld\n", getpid(), getppid());
         sleep(1);
    }
    
  3. Question: Draw a diagram showing the parent-child relationship if the following program is run with command line argument 3. How many processes are created? Explain step-by-step how these processes are created, especially who is created by whom.
    void main(int argc, char **argv)
    {
         int i, n = atoi(argv[1]);
    
         for (i = 0; i < n; i++)
              if (fork() == -1)
                   break;
         printf("Process %ld with parent %ld\n", getpid(), getppid());
         sleep(1);
    }
    
  4. Why does the approximation value of e drop to 1 from a reasonably accurate result when the value of i is very large? Clearly explain your findings. You will not receive any point if your answer is vague and not convincing.

You should elaborate your answer and provide details. When answering the above questions, make sure each answer starts with a new line and has the question number (e.g., Question X:) clearly shown. Separate two answers with a blank line. Also make sure that the diagrams in your README file will PRINT correctly. Do not judge the results on screen.

Note that the filename has to be README rather than readme or Readme. Note also that there is no filename extension, which means a filename such as README.TXT is NOT acceptable.

README must be a plain text file. We do not accept files produced by any word processor. Moreover, watch for very long lines. More precisely, limit the length of each line to no more than 80 characters with the Return/Enter key for line separation. Missing this file, submitting non-text file, file with long lines, or providing incorrect and/or vague answers will cost you many points. Suggestion: Use a Unix text editor to prepare your README rather than a word processor.

Final Notes

  1. Your submission should include two files, namely: prog1.c and README. Please note the way of spelling filenames.
  2. Always start early, because I will not grant any extension if your home machine, network connection, your phone line or the department machines crash in the last minute, etc.
  3. Since the rules are all clearly stated, no leniency will be given and none of the above conditions is negotiable. So, if you have anything in doubt, please ask for clarification.
  4. Click here to see how your program will be graded.