The discipline of computer science has it roots in mathematics. Early developments were made by people who would be considered to be mathematicians. It's probably true to say that the computer was used by mathematicians and, of course, scientists and engineers, as a way to speed-up calculations. In this manner very sophisticated software has been produced to help solve a wide variety of practical problems.


A particularly important problem lies right on the border of mathematics and computer science. This problem concerns the algorithms used in computer software, the algorithms themselves comprise mathematical statements. The crucial point concerts the efficiency of these algorithms. A simple expression of efficiency is the number of steps required to obtain an answer in terms of the size of the input data. Put simply like this it couldn't seem to be a particularly difficult problem. However, quite the opposite is the case and this problem, known as P vs NP, is one of the seven Clay Institute Millennium Problems for each of which the person solving the problem may claim $1,000,000 prize.



SECONDARY: the difference between solving a problem and verifying a solution. Efficiency of algorithms. An introduction to complexity theorem. ‘Hard’ and ‘easy’ problems. Big O notation, polynomial and exponential time. Sorting algorithms.


SIXTH FORM: plus proof of big O results. P, NP and NPC classes.


Copyright Maths Discovery 2015