Introduction to Computational Thinking#

In this notebook we will discuss the process of solving mathematical problems aided by computation. This process is often referred to as computational thinking and is something we will be doing quite a lot during the course of this module.

When to compute?#

Our first step, when beginning to tackle a problem, is to decide if computation is the best approach or a helpful tactic. We are typically hoping to use computation to take some of the leg-work out of an otherwise lengthy, complex or difficult procedure.

Consider the definite integral,

\[ \int_a^bf(x)dx, \]

in the case where \(f(x)\) is not easily integrated directly, for instance \(f(x)=\frac{1}{\ln(x)}.\)

We might resort to textbooks in the first instance to check whether we are simply unaware of the required technique or result. We might then try an internet search; perhaps if we’re smart we might use a tool like Wolfram Alpha to quickly find out about the integral. In some respects this is the beginning of our computaional thinking!

The first step in our process might be

  • What is the problem and can computing help?

How to compute?#

Perhaps a simple search on Wolfram Alpha will give us enough information to solve our problem, however, having found out that this integral has no simple closed-form solution we might now wish to have our own method to compute its value, rather than relying on the black-box of a software package. In this case we can make use of well known numerical approximations to approximate the integral by the composite midpoint rectangle rule, i.e.

\[ \int_a^bf(x)dx \approx h\sum_{i=0}^{N-1}f\left(\frac{x_i+x_{i+1}}{2}\right). \]

It is perfectly possible to perform this midpoint rule calculation by hand, however it is rather onerous, especially if we want to take large \(N\) and obtain an accurate result. So, having a bit of Python behind us, we can easily compute this sum automatically for various choices of \(N,\,a,\,b\) or even a different \(f(x)\) if we write our code well. For example:

import numpy as np

def f(x):
    return 1/np.log(x)

def midpoint_integral(a,b,N,f):
    h = (b-a)/(N-1)
    x = np.linspace(a,b,N)
    
    return h*np.sum(f(0.5*(x[0:-1]+x[1:])))

midpoint_integral(2,3,1000,f)

1.1184247826314846

In this case why we use a computer to obtain this result is abundantly clear; we need to speed up an otherwise routine lengthy set of calculations.

However what if \(f(x)=x^2?\) A computational solution to this problem would not be appropriate as the solution is easily written down with minimal effort.

Tip

In some cases the automation of a set of calculations could be so advantageous so as to render the impossible possible. For instance, it would probably take centuries of person time to perform the calculations embedded within the simulation of the atmosphere to generate your weather forecast (see here for more).

This brings us to the next part of our computational thinking process

  • Express our problem in a form accessible to a computer (abstraction)

  • Implement the abstracted version of the problem in the required programming language or software package

For the purposes of this module, the implementation step is in Python, but the skills you learn here are readily transferred to other languages (e.g. Julia, R, C++) or software packages (e.g. MATLAB, Octave, Mathematica).

Abstraction#

This abstratction is worthy of additional discussion. In the example above, the process of converting the integral into something accessible to the computer actually involved some numerical analysis when formulating the midpoint rule. A numerical approach is often the way to proceed when tackling problems in applied mathematics where a complex physical problem is being considered and an approximate solution is the only option (even though a solution might be formally approximate, it might be very good and highly useful!).

In other areas of mathematical computing this abstraction step can contain the application of different techniques or methods in that area.

In statistics, the problem is often one involving the analysis or modelling of real-world data which contains uncertainty and the abstraction might require the user to determine an appropriate model for the data which accounts for errors or stochasticity. Most of statistics can be considered part of an abstraction process to enable meaningful conclusions to be drawn from data.

In pure mathematics, the abstraction step could involve the development of a new algorithm. For instance it might be possible to formulate a program to test, by brute force, or prove by exhaustion, all the cases in a finite problem. Computer-assisted proofs have solved problems in graph theory and enabled ever larger prime numbers to be computed.

Pseudocode#

To assist with abstraction when a complicated code is required we can make use of pseudocode to bridge the gap between the stated problem and the implemented program. Pseudocode is a representation of the algorithm or program written in (relatively) plain English but containing the important steps of logic and mathematical operations required. There are no hard-and-fast rules for creating pseudocode but it should not be code and it should be easily read by a human user.

For the example of the midpoint rule above our pseudocode might have looked something like

Pseudocode

  • Define \(f(x)\)

  • Set \(a,\,b\) and \(N\)

  • Compute \(h = (b-a)/(N-1)\)

  • Set a grid of points \(x_0=a,\, x_1=a+h,\,\dots,\,x_N=b\)

  • Sum over all subintervals \([x_{i-1},x_i]\) the function evaluated at its midpoint, \(\frac{x_{i-1}+x_i}{2}\) and multiply by h

  • Return the result

Pseudocode is useful for keeping track of the process when you come to the implementation step, and can serve as a useful form of documentation of what you have done.

What did we compute??#

It might be tempting to think once we complete step 3 above we are done, but we are not!

The final part of the process is to interpret our results and consider:

  • Are the results correct? (validate and debug)

This is arguably the checkpoint to determine whether you are really finished with the implementation step! In most cases there are simple ways by which we can check our code is producing the correct results. For instance with the integration example above, how can we be sure that 1.118... is the right value? One approach might be to test the midpoint rule on an easily integrated function first to make sure our implementation is correct. For instance \(g(x) = 3x^2\) then \(\int_2^3g(x)dx = 19.\)

def g(x):
    return 3*x**2

midpoint_integral(2,3,1000,g)

18.99999974949925

Debugging#

Suppose the result we obtained from our test was not as expected, or when the code was executed we recieve some warnings or errors. Fixing these issues is known as debugging. Often this is the most time consuming and involved part of the entire computational process and so developing good debugging skills is vital!

In Chapter 1 in the Errors notebook we briefly discussed interpreting error messages. In general Python is quite good at showing you what has gone wrong and where, however when we are starting out we still need to build up our familiarity with the technical terms. A good idea, when an error is not obvious, is to check if there is a better description of the exception online, e.g. here.

Usually syntax errors and runtime errors are relatively easily fixed; once you understand the error message it often just requires some patience to figure out the fix. Harder, and requiring a little more skill to fix, are the so-called semantic errors which occur, not because your code fails to execute, but because the code fails to give the expected result. In such cases there are no error messages to help!

In the Errors notebook we discussed how documenting your code is a useful way to keep track of what you expect your code to do. Part of your documentation might involve the pseudocode we discussed above. If you’re still struggling to find your bug here are a few hints or techniques which might help.

Hint

Simplify

The first thing to do is break your code up into smaller, simpler pieces and try to check each part. This is where having a modular program with good use of functions comes in handy (see section Good practise part 2). Sometimes it is helpful to create a minimal example, i.e. the smallest code snippet which contains the bug; this usually eliminates many possible sources of error.

Output

It’s hard to tell what the internal workings of a program are doing unless we see some output, print() is your best friend when debugging! This is particularly useful if you have some iteration or a long calculation because you might be able to spot the point at which the code fails. Outputs don’t have to be limited to just a print statement, in some cases a plot might help point out where the trouble lies.

Test

This comes back to the validation step referred to earlier. Throughout your debuggging step be on the lookout for simple tests you can put your code through to check it does what you need it to. Sometimes this will also mean thinking about how general your code is. As a simple example, suppose you defined a function involving a term \(x(1+1/x)\) but you didn’t test it near zero so missed the singular behaviour. (Rewriting this line (\(x+1\)) will fix the issue!)

Ask for help

You will, inevitably, have to resort to a more experienced pair of eyes at some point during this module. This is (partly) what the lab sessions are for! We are on hand to help, debugging is a (fun?) part of the process but please don’t struggle in silence. This advice carries over to programming outside of this module; seek help when you need it, the internet has some useful places to ask for help.

Debugging tools

Eventually, it might become necessary (or welcomed!) to turn to some tools to help your bug search. A debugger can help you trace through your code to find out where things are going wrong. This is likely a last resort in this module but if you end up doing a lot of programming in your job or on another module you might find a debugger makes hunting bugs a bit more efficient.

In subsequent sections we will touch on other tips and techniques to help reduce the time spent debugging.

Example#

Here is an example of a bug using the midpoint example, suppose we didn’t have the answer above but had written the following code:

def midpoint_integral(a,b,N,f):
    h = (b-a)/(N-1)
    x = np.linspace(a,b,N)
    
    return h*np.sum(f((x[0:-1]+x[1:])))

midpoint_integral(2,3,1000,f)

0.6273186412227292

On the face of it, there appears to be nothing wrong, we got a sensible looking answer, but is it correct? Well, we should really be diligent and test more thoroughly. Using the test involving \(g(x)\) from above

midpoint_integral(2,3,1000,g)

75.999998997997

Oops, now we are sure there must be an error in the code; but where?

Let’s simplify and output. Here simplification might just mean taking a small \(N,\) examining each component used and checking it is correct.

a = 2
b = 3
N = 6  # choose a smaller value to make outputs easier to read

h = (b-a)/(N-1)
x = np.linspace(a,b,N)

print('h=',h)
print('x=',x)
print('g(x) = ',g((x[0:-1]+x[1:])))

h= 0.2
x= [2.  2.2 2.4 2.6 2.8 3. ]
g(x) =  [ 52.92  63.48  75.    87.48 100.92]

Examining this output carefully we can see that there’s somthing off in the \(g(x)\) function evaluations. We are testing with \(g(x)=3x^2\) so the values we expect should roughly start at \(g(2)=12\) and go to \(g(3)=27.\)

Consulting the code again, and checking with the psuedocode, we can spot that we should be evaluating at midpoints; we missed a factor of \(\frac{1}{2}\)! Before going back and fixing the original function we should first test that this fix will give the required result:

mid_x = 0.5*(x[0:-1]+x[1:])

print('midpoints = ', mid_x)
print('g(mid_x) = ', g(mid_x))
print('integral = ', h*np.sum(g(mid_x)))

midpoints =  [2.1 2.3 2.5 2.7 2.9]
g(mid_x) =  [13.23 15.87 18.75 21.87 25.23]
integral =  18.990000000000002

Notice that the introduction of the variable mid_x storing the midpoints might have made us less likely to make this error in the first place.

Once we are happy that our results are correct, the final part of the computational thinking process is to consider

  • What do the results tell us in the context of the original problem?

We leave this part largely for other modules, or specific examples in the lab exercises or projects; really it comes down to using your computational skills and methods to present the results in the best possible way. This might mean creating plots, figures, tables, or exploring parameter values to draw more general conclusions.

Remember:#

The computational thinking process

  1. Decide: What is the problem and can computing help?

  2. Abstract: Express the problem in a form accessible to a computer.

  3. Implement: Implement the abstracted version of the problem (in Python).

  4. Validate: Are the results correct?

  5. Interpret: What do the results tell us in the context of the original problem?

  6. Done!

If you haven’t already, now watch the video Computational thinking: bisection to see a demonstration of the process in real-time for the bisection method.