Homework 5

This is the fifth and final homework assignment. Your goal in this assignment is to implement a solution to the common problem of approximating an unknown function based on a sample of function values. For this homework we provide you with a testing framework, which will run tests of your function. It is important that you learn to use the testing program effectively, since we will be using this kind of automated testing also for the programming exam at the end of the course.

Practical information#

The assignment is due on Sunday the 22nd of April, at 6pm. To submit your solution, you will upload a single python file via wattle. Here is the assignment submission link.

In addition to submitting your solution, you must attend the following lab (in week 8). In the lab, your tutor will ask you some questions about your submission, and give you feedback if there is anything you need to improve. This discussion with the tutor is also part of the assessment. If you do not show up for the discussion with the tutor, you will not receive any marks for this assignment. If you do not submit a solution, you may still get the marks that are based on the tutor’s assessment of your understanding.

The assignment can be done together in pairs, but not in a group of more than two students. You may, of course, also do the assignment on your own if you prefer.

If you work in a pair, both students must submit solution files, and both students must attend the following lab and answer the tutors questions. In your solution file, write a comment (using python comment syntax) to say who you worked together with - you should write their ANU id. Both of you must be able to explain every part of your submitted solution. The tutor will choose who to address each question to, and only the student addressed may answer. It is not acceptable to divide the assignment up so that one student does half and the other student the other half.

As usual, you should have followed previous week’s lectures and worked through the exercises in the labs before starting on the assignment. The assignment should not take more than one or two hours to complete.

The problem#

Linear interpolation is a method of computing the approximate value of a function in one argument, given only samples of the function at a set of points. This is commonly used where the values of a function are difficult or expensive to obtain. For example, we may have to carry out a physical experiment, or a time-consuming simulation, to find the function value for a given argument. As an example, think of “deformation of the vehicle passenger compartment in a head-on collision as a function of speed” - to sample the function for a given speed value, we may need do a crash test!

Suppose we know the function value at a set of points y_i = f(x_i), for i = 1…n. To approximate the function at a new point x’, we find the closest known points below and above, say x_below < x’ and x_above > x’, draw a straight line between (x_below, y_below) and (x_above, y_above), and take the value y’ where this line is at x’.

The general form of the straight line is a * x + b, where a = (y_above - y_below) / (x_above - x_below) and b = y_below - a * x_below. Using this, we can calculate y’ = a * x’ + b

Example:

Suppose we have the sample points f(1) = 1, f(3) = 9 and f(5) = 25.

If we want to compute an approximation of the value of f at x’ = 2 using linear interpolation, we would find the closest sample point that is less than 2 (namely 1) and the closest sample point that is greater than 2 (namely 3), and draw a straight line between the known points (1, 1) and (3, 9). The line equation becomes 4 * x - 3, from which we get the answer 4 * 2 - 3 = 5.

If we wanted to approximate the value of f at 4, the closes sample point below is 3 and the closes sample point above is 5, from which we get the line 8 * x - 15 and the answer 17. The following figure illustrates how both values were calculated:

Task:

Your task is to implement a function interpolate(x, y, x_test) that computes the linear interpolation of the unknown function f at a new point x_test. The sample is given in the form of two sequences x and y. Both sequences have the same length, and their elements are numbers. The x sequence contains the points where the function has been sampled, and the y sequence contains the function value at the corresponding point. In other words, y[i] = f(x[i]).

Assumptions and restrictions:

• You can assume that the arguments are as described: that is, x and y are sequences, both have the same length, and their elements are numbers.

• You should NOT make any assumption about what type of sequence the x and y arguments are.

• You can assume that the values in x are ordered in increasing order, and that they are unique (that is, there are no repeated x-values).

• You can assume that x_test is a number, and it is between two values in the x sequence, or possibly equal to a value in the sequence. If x_test is equal to a sample value (a value in the input x sequence), your function should simply return the corresponding function value from y.

• Your function must return a number.

• The scipy library has a whole module, scipy.interpolate which performs various kinds of interpolation, including linear interpolation as described above. Obviously, you may not use this module, or any other module that provides a ready-made solution to the problem, since the goal of the assignment is for you to demonstrate that you can implement the function yourself. You can of course use the scipy interpolation function as a reference to test your implementation.

As a starting point, we provide you with a skeleton code file: homework5.py. Download this file and write in it your implementation of the function.

Using the testing program#

To use the testing program, you must first download these two files:

• test_hw5.py
• testing.py

Save both of them in the same directory as the file homework5.py. To run the testing program, you just need to run test_hw5.py. The testing program will read the file homework5.py and test the function interpolate defined in that file, and print out results of the tests. If your function fails any of the tests, the program will print a detailed error message and stop.

Remember that the testing program will test the file named homework5.py which is located in the same directory. If you change the name of the file with your implementation, you must also change the file name on the last line in the testing program to test the right file.

For the testing program to work, your code file must meet certain requirements. These requirements also apply to the file that you submit.

• It must be syntatically correct python code.
• It must contain only function definitions and comments.
• It must define a function called interpolate that takes 3 arguments.

Your function definitions may contain docstrings (as shown in the week 2 lecture), but it is not permitted to use docstrings in place of comments anywhere other than on the first line inside a function suite (the function docstring can span several lines, of course). Any other comments should be written using python’s comment syntax (# comment).

Marking#

Upload the file homework5.py with your implementation.

Remember that you must upload a single python code file. The name of the file does not matter, except that it must end with the extension .py. Do NOT zip it or convert it to another format.

As mentioned above, you must also attend the following lab (in week 8) and answer your tutor’s questions about your solution. This discussion is part of the assessment. You should be prepared to answer or demonstrate to the following questions:

• Can you download the file that you submitted from wattle?
• Can you run that file in the python interpreter (using an IDE of your choice) on the CSIT lab computer?
• If the file has syntax errors, can you use the error messages from the interpreter or IDE to identify where the syntax errors are?
• Does your submitted file meet the requirements stated above? Does it contain anything that is not a function definition, an import statement, or a comment? If so, can you point it out?
• Can you download and run the testing program?
• Does your implementation pass all the tests run by the testing program?
• Does your implementation of the function return the correct value for all valid arguments, not just the test cases run by the testing program?
• In order to find the position of the nearest smaller and larger x-value in the input, you needed to iterate over the elements of the sequence (or you used some function or method that does). How did you accomplish this? Is there any other way it could have been done? How many times does your solution iterate through the sequence? What is the smallest number of iterations over the sequence that is necessary to find the position of the two closest x-values?
• Did you use any function provided by an imported module? If so, can you explain how you would write code to do what those functions do, if you had to produce a solution without using them?
• Did you implement your solution with just one function, or divide it into several functions? Does the functional abstraction make your code easier to read and understand?
• Are the functions in your submitted file documented? (with docstrings and/or comments?). Does the function documentation adequatly describe what the function does and what its assumptions and limitations are? Are your comments at an appropriate level of detail? Are the names of variables, parameters and auxiliary functions descriptive of their purpose?

The marking scale for this assignment is as follows:

• The submitted file is syntactically correct and meets the submission requirements: 0.5 marks.
• The implementation of the interpolate function returns correct values for all valid arguments: 1 mark.
• The submitted code has readable and informative documentation and commenting at the right level of detail: 1 mark.
• Your ability to use the tools (including the testing program) and your understanding of possible solutions to the problem, as demonstrated in your discussion with the tutor: up to 2.5 marks.

The assignment is worth 5% of your final mark.