Programming Assignment 1

Due date: 21 Jan 2004, 6pm

Your first assignment will test your ability to edit a program, compile the program, get the expected answer, and then submit the program into the departmental dropbox. This assignment will not have the same point value as any of the other assignments, but it will have some point value. You cannot get credit for assignments that you can't get submitted, so this is your chance to practice the process and get credit for your effort.

First, create a program01 directory in your home directory on some unix machine.

Go to the sample programs directory, right click on the sample01 link, and download the sample program. Then right click on the makefile link, and download the makefile.

Move the downloaded sample program and the makefile into your new program01 directory. (Trust me--you will want to do each programming assignment in a different directory just to keep things neat and tidy.)

You should now be able to compile and run the sample program. All you need to do now is to edit out my name from the program and insert your name so that your name gets printed instead of mine, and change the code so that you compute the square root of 20.25 instead of the square root of 64.0. (The correct square root is 4.5.)

Now use the CSE departmental dropbox to send your program and the makefile (do not forget the makefile) for grading.

Programming Assignment 2

Due date: 5 Feb 2004, 6:00 pm

You are to write a program that will

1. Read in lines of triples of values from a file. Each line of the file will have three floating point numbers in it. The last line of the file should contain the three sentinel values
   -9999.99 -9999.99 -9999.99
   that will cause your program to terminate normally.
2. You should interpret the three input values as a, b, and c in a quadratic polynomial
   a x**2 + b x + c
   
3. If the value of a is zero, then skip all three values, print a message that you are skipping the values (make sure you print the values themselves so you will know why you are skipping them), and go on to the next line.
4. Use the quadratic formula to compute the two roots of the quadratic polynomial.
5. Except that if the radicand of which you would take the square root is negative, then you can't take the square root. In this case, print the coefficient values and the value of the radicand, say that you are skipping on to the next line, and then skip to the next line.
6. Assuming that you have managed to get this far, print a message with the three coefficients and the two roots.

You may cannibalise liberally from the cosine law program that was used as an example. The only changes you should need to make to the cosine law program are to change the use of the cosine law to the use of the quadratic formula and to change the tests for what sorts of things to skip.

Programming Assignment 3

Due date: 20 Feb 2004, 6pm

(This is not the third assignment that used to be posted on the web site. Also, the due date has been changed.)

This programming assignment is essentially the same as programming assignment 17 on page 251 of the text, EXCEPT that the means by which the numbers are read and counted differs from what is in the text.

Write a program to read a set of numbers and calculate the mean, variance, and standard deviation of the set of numbers. The mean and variance of numbers can be calculated using the formulas in the text. The standard deviation is the square root of the variance.

Input data for your program should be in the following format: One integer n that is the number of actual data items to be read, followed by the n floating point data items. The number n and the data items should appear one number per input line.

Your output should include an echo of the numbers and the mean, variance, and deviation. Your output format should ensure that a meaningful result is printed regardless of the values in the set of numbers.

Programming Assignment 4

Due date: 6:00 pm, Friday, 27 February 2004

You are to write a program that will approximate the value of pi by a Monte Carlo method.

Consider a circle in the plane, centered at (0,0) and with radius 1. This circle has area equal to pi. The area of the upper-right quadrant is, therefore, pi/4.

Run a random number generator and get two random numbers, both between 0.0 and 1.0, and use the first for the x-coordinate and the second for the y-coordinate of a point in the upper-right quadrant of the plane.

If this point has SQRT(x**2 + y**2) <= 1.0, then the point lies inside the circle. If not, it lies outside the circle but inside the square of area 1.0 whose corners are at ( 0.0,0,0), ( 0.0,1,0), ( 1.0,1,0), and ( 1.0,0,0).

Run a loop up to some large number, generating points in the plane. Count the number of points that lie inside the circle and the number of points that lie outside the circle but inside the square.

The area of the pie-shaped piece that is the part of the circle in the upper right quadrant can be approximated by
(number of points inside the circle)/(total number of points).
Thus the constant pi itself can be approximated by 4.0 times this fraction. (In this case, the computation is easier because the box has area equal to 1.0. If this area were different, we'd have to normalise.)

This is called a Monte Carlo computation due to the use of random numbers as a way of simulating reality.

You should use three different random number generators (RNGs). One is the built in function RAND(.) for random number generation. The second is the Unix irand(.) function. The third is an implementation I will provide of a random number generator by Knuth. I will also give you an alternative function that might give slightly different results. Run your computation up to 1 000 000 points total. Every 10 000 points you should print out one line of output that has

• the number of points
• the number of points inside the circle for RNG one
• the difference pi - pi_approx for RNG one
• the number of points inside the circle for RNG two
• the difference pi - pi_approx for RNG two
• the number of points inside the circle for RNG three
• the difference pi - pi_approx for RNG three
• an integer 1, 2, or 3 according as that random number generator is the closest approximation to the actual value of pi.

This program is not the way in which you would test a RNG, but it does have several characteristics of programs you might want to write. It requires you to run a loop and print values. You must keep track of the best of three options and the number of times each of the three options is the best And you need, in the middle of a loop, to decide whether or not one of the currently computed values is in fact "really good."

Programming Assignment 5

Due date: 6:00 pm, Friday, 05 March 2004

One of the standard exercises in a freshman calculus class is that a projectile fired into the air travels the greatest horizontal distance when the angle at which it is fired is 45 degrees to the horizontal.

You are to write a program to demonstrate this computationally.

The physics of the problem is this. If a projectile is fired at an angle of alpha up from the horizontal with a velocity of V meters per second, then the initial (and continual) horizontal velocity is Vx = V * cos(alpha). Since there are no forces acting horizontally, this is the constant horizontal velocity for the duration of the flight of the projectile.

The initial vertical velocity is Vy = V * sin(alpha) upward, but that velocity is acted upon by gravity at 9.8 meters per second per second downward. The vertical acceleration is thus
-9.8
and the vertical velocity is
-9.8 * t + Vy.

Given an initial velocity V, we can solve for the time t at which the velocity becomes zero. This will be the point at which the projectile stops rising and begins falling. Due to the symmetry of the trajectory, this time t is exactly halfway into the total flight, and the projectile will have travelled exactly halfway along its horizontal path at this point.

Input to your program should be the initial velocity and the number of intervals at which you are to compute the flight time and the distance travelled. (If four intervals, then compute these values for
1*(pi/2)/4 = pi/8,
2*(pi/2)/4 = pi/4,
3*(pi/2)/4 = 3*pi/8,
and
4*(pi/2)/4 = pi/2.)

Your program should compute and print the interval subscript (the 1, 2, 3, 4 above), the angle of elevation (the four angles above), the total flight time, the total height reached, and the total horizontal distance travelled. Your program should keep track of the point at which the longest horizontal distance is reached and should print this out at the end of your loop.

Once again, this is a computation that is actually better done as a calculus exercise. On the other hand, it can be the case that you have to solve an optimisation problem and that you cannot compute the "closed form" solution that is possible for the projectile problem. In that case, a computational solution may be your only answer.

Programming Assignment 6

Due date: midnight, Friday, 19 March 2004

Your assignment is to implement a bubble sort on an array of real numbers and then to compute some order statistics on the array of data.

A bubble sort works as follows. Let us assume you have N items to sort and that they are stored in an array as elements x(i) . A bubble sort takes two nested loops. The outer loop runs on a subscript i from 1 up to N-1 . In the inner loop, you compare the i -th element x(i) with all the elements of subscript larger than i . If any of these elements x(j) is smaller than the x(i) -th element, then x(j) should be exchanged with x(i) so that as you progress through the inner loop, the current value of x(i) is the i -th smallest of all the values encountered in that iteraion of the inner loop.

When you have finished with the i -th iteration of the outer loop, then all the elements from x(1) through x(i) are in sorted order.

Your arrays should be dimensioned so as to permit arrays of up to 100 elements (floating point numbers) to be sorted.

Once you have sorted your array, you should now compute some statistics. Compute the mean, variance, and standard deviation of the array. Then print out the subscript and value of the element closest to the mean, the subscript and value of the elements closest to the mean plus one standard deviation, and the subscript and value of the elements closest to the mean minus one standard deviation.

(If you have studied probability or statistics, then you will remember that if you have lots of data, and that data follows a normal distribution and thus forms a bell curve, then determining the steepness or flatness of the bell curve is essentially the same problem as determining how close to the mean lie the points within which lie the data within one standard deviation of the mean.)

Programming Assignment 7

Due date: midnight, Friday, 26 March 2004

You are to write a program to do Lagrange interpolation.

Input to the program will be the following:

1. one line containing an integer n, the degree of the polynomial f(x) generating the test data.
2. n+1 lines each containing the floating point coefficients of f(x) in increasing degree order. Thus the first of these is the coefficient of x**0, the second is the coefficient of x**1, and so forth.
3. n+1 lines each containing the floating point values of the x-coordinates of the data points used to create the polynomial.
4. one line with a single floating point number that is the x-coordinate of the point at which to interpolate the function.

Ordinarily, of course, you wouldn't get the data of (2) above. You'd get the (x,y)-coordinates of the data and have to generate the interpolating polynomial from that. But then how would you debug your program to know you're getting the right answer?

So we'll do it this way. Read in the coefficients of a polynomial. Assume for the purpose of dimensioning arrays that the polynomial is of degree no higher than 10. Remember that this requires 11 and not 10 coefficients to be stored, so this is a good example of why having a zero-up subscripting option is useful. Then read in the x-coordinates of (3) and use the polynomial to generate the y-coordinates. This should be done by having a function for evaluating the polynomial, and you should be passing in the degree of the polynomial and the coefficients to that function.

At this point you will have arrays of x-coordinates and of y-coordinates, just as if you had read them in.

Read in the point at which to interpolate (item (4)). Compute the exact value of f(x) using the function.

Then call a function that does a Lagrange interpolation using the (x,y) data points.

Your interpolated value should be close to the exact value. It won't be identical, probably, due to roundoff error, but it should be quite close.

And now, if you had to, you could use the Lagrange function to interpolate for other sets of data points as well.

In this case, since it would be assumed that you would be incorporating the Lagrange function into another program later, you must make this function an external function so as to make sure you aren't using any variables from the main program that might not be there in some other main program you would be using.

Programming Assignment 8

Due date: midnight, Friday, 9 April 2004

You are to write a program using linked lists and structures to multiply two polynomials together.

Input for the program should consist of something like the following:

• one line of input that has an integer n1 , that is the number of nonzero coefficients of polynomial P1 ;
• n1 lines each of which has a pair of integers that are the degree of the term and the coefficient of that degree of the polynomial P1 (you may assume integer coefficients to make the problem simpler);
• one line of input that has an integer n2 , that is the number of nonzero coefficients of polynomial P2 ;
• n2 lines each of which has a pair of integers that are the degree of the term and the coefficient of that degree of the polynomial P2 .

You may assume that the coefficients are presented in increasing order of degree.

Your program should then multiply the polynomials together to get a third polynomial P3 = P1 * P2 and then print the three polynomials.

Rules of the game.

• You may assume that the polynomials P1 and P2 have degrees less than or equal to 6, so the product has degree less than or equal to 12, and thus you may dimension arrays so as to accommodate polynomials of only up to these degrees.
• You should use a structure to represent the nodes in a linked list.
• You may copy any of my code that handles structures and/or linked lists.
• Do not forget that coefficients can disappear, as in multiplying (x + 1) * (x - 1) .
• There are two ways to do this kind of program. You can do the multiplication and consolidate entries (as with the disappearing coefficients above) all in one step, or you can do the multiplication, link in all the entries, and then go through the list afterward to compress. Note that if you start with polynomials as a degree-increasing linked list, and you multiply them in the obvious way, then you will be inserting nodes into your list in increasing order, so if you do it right the two nodes above with coefficients +1 and -1 would be adjacent. This makes programming easier.

Advice.

• I believe it would be to your advantage to write the program initially using arrays and not a linked list, so that you can test your program against lots of input data. This will probably also help you in figuring out the logic of adding the exponents to know where to put the correct data. (That is, treat this program in two parts. First get the polynomial multiplication part correct, which is a "make the exponents and subscripts right" task. Then translate that into a linked-list problem, which involves getting the pointers right.

Programming Assignment 9

Due date: midnight, Monday, 19 April 2004

This is a program aimed to give you experience reading and writing records, using a structure, from a file too big to sift through by hand. The data file is at xtestdata

The data file consists of "some number" of records, one record per line. The record format is

• label, 16 characters long, written with A16 format
• x, floating point, written with F10.6 format
• y, floating point, written with F10.6 format
• mean, floating point, written with F10.4 format
• pertinence, integer, written with I4 format
• irrelevance, integer, written with I4 format
• calibration, one character, written with A1 format
• obfuscation, floating point, written with F12.2 format

You are to write a program to read this file, using a structure for the record. There may be records (lines) in which the data are not in the correct format, so your program will have to trap those errors. You will also have to catch end of file. As you read, you should be counting the number of records that have been read and the number of records that have been read without error.

Open the file, read the entire file, and find the maximum and minimum absolute values of the mean.

Then close the file. Compute a tolerance value that is 1% of the absolute value of the maximum value of the mean. Now reopen the file (you may REWIND instead if you choose instead of opening and closing, but I recommend opening and closing just for the sake of clarity), and read and print in formatted fashion. You should now be printing exactly those records for which the absolute value of the mean in the record is within tolerance of the absolute value of the maximum mean. Sample output can be found at xtestout Note that I have also printed out the successive min and max values as they have been computed.

Note also that you need to label the columns and to put in some extra spaces that aren't in the original data, and that your output should indicate the absolute record number R and the "good" record number G.

Programming Assignment 10

Due date: noon, Wednesday, 28 April 2004

This assignment is for extra credit in the following sense: The grade for this assignment will replace the lowest grade you have received for some other programming assignment.

You are to write a program to perform Gauss-Seidel iteration to solve a system of linear equations.

The input system will be a square system of n rows and columns; your code should handle systems for n as large as 20. You may dimension the arrays statically at size 20 and just waste space if the input system happens to be smaller.

Several input systems will be available for testing; look for them at the bottom of the list of sample programs. You are responsible for verifying that you are getting correct answers for these sample systems.

Your code should terminate on the absolute error condition that for all the variables updated in iteration k we have abs(newx - oldx) lessequal tolerance

Input to your code should be the following.

• The first line should have the single integer value n.
• The second line should have the absolute error tolerance.
• There should then follow n lines of data, each with the row data for that row of the matrix.
• There should then follow n entries of the constant vector.
• The last line should contain the n entries of the initial solution.

Make sure that you output the number of iterations necessary for convergence.

Make sure that you have your own termination condition (in terms of the number of iterations) in case Gauss-Seidel doesn't converge for the system to be solved.

Make sure that your program checks and outputs the answer to whether or not the matrix satisfies the diagonal dominance condition.

Make sure that your program checks the putative solution with the original matrix and outputs a statement about absolute.