Assignment 3

Parameterized Array Class(es) and Polynomial Interpolation

Due Date: Friday, October 9, 2009

Required for submitting:

    • Grade Sheet Print this sheet and bring it to class the day the program is due.

    • Bring your UML diagram to class. Note: you've already handed in your very last hand-drawn UML diagram

Purpose:

  • The purpose of this exercise is to give you more practice with the first few items listed below. In addition to these, we will revisit a topic you saw in your Cs 228 course (or equivalent, if you transferred credit). I want you to have some experience coding the necessary constructs using the OOP paradigm for polynomial interpolation. You might recall studying the Lagrange and Newton forms of interpolating polynomials? Ok, maybe not. But you can read; I suggest you start now by refreshing on this topic. We will see in the succeeding assignment that some fairly ingenius mathematics can turn a disasterous interpolant into a much better predictor. Thus, you shall discover in the next two assignments that the simplest, easiest way to do something just isn't necessarily the best way.

      1. templated classes

      2. templated functions

      3. overloading operators

      4. the STL; in particular, the vector class

      5. the concept of possibly implementing algorithms as classes

      6. C++ to "wrap" a data type

      7. Newton form of interpolating polynomials

Resources:

The Concept:

  • Many scientific investigations require the knowledge of function values not known to the investigator. This may be due to the fact that the function represents empirical data or that the function has no known formula. One way out of this pickle is to take a job as a greeter at Wal-Mart where you don't need to know how to spell 'science' let alone do any. Another way out is to derive an interpolating polynomial. An interpolating polynomial is a smooth curve that "connects the dots" of data. They're nice because they are polynomials and evaluating polynomials at any value is easy. Hopefully, the interpolating polynomial you derive closely approximates the function you are trying to emulate. We'll see if this is true. Remember: it takes n+1 data points to create a nth degree polynomial (you know, 2 pts determine a line; 3 points determine a parabola, 4 points determine a cubic thingy, etc.).

    • There are two forms for the interpolating polynomial (for a given data set - remember: they're unique) that you learned about in CS 228. They are called the Lagrange form and the Newton form. We are interested in the Newton form. In order to form the Newton polynomial, you need to build a divided difference table. It is too complex for me to explain here, so I suggest the you dig out your CS 228 book and read up on the topic. I may also discuss it in class. From the divided difference table you will be able to read the coefficients for the polynomial. Once you know the coefficients, you know the polynomial. Then, for any value within the range of the extremes of the data, you can 'interpolate' the true value of the function by evaluating the polynomial you constructed.

    • The interpolating polynomial that you generate for any given set of data will depend on several parameters. The two most important are the number of data points and the spacing of the data points. For this assignment, the data will be generated at uniformly spaced x-values in the interval [-1, 1] from a known function. The function used for this assignment will not be divulged just yet as I would like to instill a sense of wonderment and anticipation of an exciting exercise. Its formula is made known lower on this same page so as not to cause too high a level of anxiety leading to premature death due to heart failure.

Program Specifications:

  • You are to code an implementation of the Newton form of an interpolating polynomial for a set of data in R2 (i.e. the plane). In order to do this, you will need to emulate the divided difference table that gives you the coefficients for the polynomial. This (we) will require an array of arrays. You are required to use your own templated array class to contain the data and the entries in the divided difference table entries. I will leave up to you whether you will use either the STL Vector class or your own array class to contain the aforementioned arrays. If this is unclear, I'm sure I'll have words about Newton polynomials in class; then it should become clear.

    • For your array class, start with the text authors' array class. You decide on the details of the implementation. Make it good: include adequate constructors, overloaded operators, etc. In considering the implementation of the Newton divided difference table, you will have to think about the functionality of your array class also. Your design for generating the div. diff. table and, hence, the polynomial's coefficients, is not going to stray too far from that of the previous assignment. You will represent the process as a class or classes again.

    • Among other considerations for this assignment, you will have to give attention to memory dynamics -- the allocation and use of that very resource. Consider how you will use memory, how you will program your array class, how STL vectors use memory, etc.

    • Again, I want you to have your program read in data from a file. The data to run your program on is: input_dataset3. The format of the file is this: the first number is an integer giving the number of pairs of x- and y-values to follow. Whitespace separates each value. Better use a double precision variable to read into.

    • Use command line arguments (argc and argv[]) to give the user (you and the grader) the ability to pass a file name to the program for reading in data.

    • Your program is to output the following:

      1. The data points used for the interpolation.

      2. The computed coefficients making up the interpolant - x0 coefficient first, xbiggest coefficient last

      3. The values of the interpolant at these x-vlaues:

        1. 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

      4. The values of the function

      5. at the same values as above. Of course, you are asking yourselves, "why ...". Answer: this is the function that produced the data read in.The absolute error in your approximations at the above values

      6. The relative error in your approximations at the above values

Deliverables:

    1. Code: I will test that the code you submit does indeed compile and run. You are to copy all your source code along with a makefile into your cs328 directory. How to do this is explained in Submission procedure.

    2. makefile: Supply the makefile which compiles and builds your program as detailed above. I really suggest that you play around with and use the third of the makefiles I posted.

    3. Your gradesheet and UML (during class).

    4. DO NOT turn in a script printing.