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.

Your solution to this homework will also be marked on code quality. This means some part of the marks will be given for good functional decomposition, variable/function naming, and commenting. The marks for code quality are distinct from those for functionality; to gain full marks, your submission must be both functional and readable.

Practical information#

The assignment is due at 9.00am on Monday the 3rd of May. 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 9). In the lab, your tutor will ask you some questions about your solution, 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 fail to show up for the discussion with the tutor, you will receive zero marks for this assignment. If you do not submit a solution, you may still get partial marks for the discussion with the tutor.

The homework is individual. You must write your own solution, and you are expected to be able to explain every aspect of it.

As usual, you should have followed last week’s lectures and worked through the exercises in lab 4 and lab 5 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.
• You may import the math module if you wish. You should not import any other modules.

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

Testing#

To use the testing program, you must first download the file:

• homework_five_tests.py

Save it in the same directory as the file interpolate.py. To run the testing program, you just need to run homework_five_tests.py. The testing program will read the file interpolate.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.

Please also be aware that the test cases for this final homework are deliberately incomplete. You should consider adding additional test cases of your own to the test file.

Remember that the testing program will test the file named interpolate.py which is located in the same directory.

Remember that you may define additional functions (for example, to break the problem up into smaller subproblems) in your solution file.

Marking#

Code quality

In this homework (like the last two) we will also be marking your submission for its code quality. This includes aspects such as:

• Using good function, parameter and variable names. The names of some functions in the homework are fixed, but if you define additional functions (to decompose the problem) then they should be given descriptive names.

• Appropriate use of comments and docstrings.

  This means not too little comments but also not too much. Comments should be accurate, relevant, and readable. A docstring should appear as the first statement in every function definition.

• Good code organisation.

  This includes appropriate use of functions to decompose a problem and avoid code repetition.

What to submit

You should edit the skeleton file interpolate.py, then upload only this file with your implementations of the function using the assignment submission link on wattle.

Remember that you must upload a single python code file. Do NOT zip it or convert it to another format.

The file that you submit must meet the following requirements:

• It must be syntatically correct python code.
• It must be named interpolate.py.
• Like the file you downloaded, it should contain only function definitions, comments and docstrings.

As mentioned above, you must also attend the following lab 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)?
• 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? If so, can you point it out?
• Does your implementation pass all the tests run by the unmodified testing function?
• Is your implementation of the function correct for any valid arguments?
• Does your function always return a value of the correct type?
• Did you think of any other test cases that should be used to test the function, in addition to or in place of those provided? Why do you think these test cases are useful. What situations or inputs are not covered by the existing test cases?
• What is the difference between the print function and the return statement?

In marking this assignment we will consider the following:

• Does your submitted file satisfy the requirements specified above?
• Does your implementation compute the correct value for all valid arguments?
• The quality of your submitted python code, including its organisation, naming and documentation (with docstrings and comments).
• Your ability to use the tools (e.g., the IDE or python interpreter), your understanding of python’s error messages, and your understanding of the solution, as demonstrated in your discussion with the tutor.

The assignment is worth 4% of your final mark. 2 marks are based on the functionality of your submission, and 2 mark on the quality and readability of your code.