Problems , Algorithm And Flowchart

Module1
Before we can even think about algorithms, we need to think about why we might
need algorithms. Well, we use algorithms to solve problems. So the first question
we need to address is, what is a problem?
Of course, we all encounter problems in our lives, whether we need to find a job,
retrieve keys from down the back of the sofa, or retrieve a document from a
remote computer.
But in computing, the kinds of problems we care about must be addressable by a
computer. We need to feed computers with data and ask appropriate questions.
The underlying language we use needs to be mathematical, no matter what
programming language you use. It would be ridiculous to ask a computer, should I
take a holiday, without any context at all, even if we all know that the answer is
yes. The computer needs each idea to be translated into a mathematical concept,
whether this is a number or a truth value, such as true or false.
There is a separate issue about what kinds of data can be addressed by a
computer, and we will discuss this.
Now we can take our example question and be a bit more methodical. Say you
have a work contract that gives you x days of holiday a year, where x is some
integer number, and you have used up y days, another integer number.
Now I can feed this information into my computer and ask if your contract allows
you to take more holidays. This corresponds to the mathematical question, is x >
y? Which will return true if x >y or false if y > x.
Okay, that's nice. But the output true or false is not so useful for planning your
holiday. A more useful answer would be to give the number of days of holiday
left. That is( x – y). Note that if this difference is positive, it implies true, and if it is
negative, it implies false to the original question. So an integral part of any
problem is the kind of answer we want.
In this case, whether we want to know if we can take holiday or how much
holiday we can take. In computing terminology, my problem has a well-defined
mathematical input, which in this case is x and y, where x and y can be integers.
And it also has a well-defined mathematical output. A problem, then, poses a
question about the input, so as to give an answer in the form of the output.
So here is a problem. Does x 2=2 have a solution if x is an integer? True or false?
So the input here is hidden somewhat in the problem. It's not the equation x 2=2 ,
it is the number 2. We are now asking about the property of the number 2.
In particular, whether its square root is an integer. And the output will either be
true or false. In principle, a computer can now attempt to solve this problem. One
way to do this is by calculating the square root of 2 to see if it is an integer.
Spoiler alert, it isn't.
Another way of solving this problem is to start generating all the squares of
integers from 1 onwards and ask if 2 is there. And you either generate 2 and
output true, or as soon as you generate a number larger than 2, you output false.
An important observation now is that problems can be solved in multiple ways. In
our example, we could solve the problem by calculating the square root of 2 or by
methodically listing square numbers.
Which is the best method if both give the right answer? In this module, we are
looking at what makes a good solution method. And to compare different
methods we need to formalize them as algorithms. So what is an algorithm?
In the broadest terms, an algorithm is a general and simple set of step-by-step
instructions, which if followed, solve a problem. So to unpack this a little, we want
that, firstly, the outputs of an algorithm is the correct solution to a problem.
Secondly, the algorithm can be described in terms of steps of basic instructions.
Perhaps in terms of basic arithmetic, such as addition, multiplication, subtraction
and division. Or simple logical operations, for example, if-then statements that
can be easily checked using basic arithmetic.
So let's return to our example of the problem. Does x 2=2 have a solution if x is an
integer? We had two solutions to this problem.
Can we describe them in terms of an algorithm? In the first solution, the first step
is to calculate the square root of 2. And then the second step is to check if it is an
integer. If it is, output true, otherwise, output false. This looks like an algorithm,
but calculating the square root is not one of our basic arithmetic operations. So
we need to describe an algorithm for this, put everything together, and then
we're done.
So let's look at our second solution. The first step takes the square of 1, which
equals 1, and then checks if this equals or is greater than 2. It does not, so the
second step takes the square of 2 and checks if it is greater or equal to 2. It is
greater than 2, so it outputs false.
So now we see that our second solution method is a fully functional algorithm in
its current form. But now imagine a new version of this problem. Does x 2=1601
have a solution if x is an integer? This is similar to our original problem. The only
thing that's changed is the right-hand side. Can we adapt our previous two
solutions? Well, in the first case, we now need to take the square root of 1601.
And in the second case, we just need to calculate a possibly larger number of
square integers. So if we can give an algorithm for calculating the square root that
works for all numbers, then we have two completely general solutions to our
general problem of asking, does x 2= y have a solution if both x and y are integers?
It is highly desirable to have a general all-purpose algorithm that can handle many
instances of a problem, but which is the better approach? In this module, we will
address questions like this, and hopefully by the end you can give me a good
answer. We have described two central concepts, a problem in computer science
and an algorithm. In summary, a problem consists of an input and a question that
tells us the form of the expected answer or output. An algorithm is a step-by-step
method for generating the correct output. In the Forum, can you come up with a
problem that could be solved by an algorithm?

Al-Khwarizim And Euclid

We have discussed in broad strokes what an algorithm is. It is a general set of
step-by-step instructions, which if followed solve a problem. Note that this
description does not mention the word computer.
This is because algorithms can be defined independently of computers and indeed
predate the digital computer by hundreds of years.
The Persian polymath Al-Khwarizmi is considered the father of algebra and
altered the book 'The Compendious Book on Calculation by Completion and
Balancing' between 813 and 833 AD.
Al-Khwarizmi was written in Latin as algorithmi and from this latinised name we
get the word algorithm.
In Al-Khwarizmi's book he gives the first systematic methods of solving linear and
quadratic equations. You might recall the solution to the quadratic equation
obtained from completing the squares. This was first described in his book.

Going even further back to the ancient Greeks, Euclid gave a procedure for
computing the greatest common divisor of two numbers.
That is, given two whole numbers A and B, what is the largest whole number C
that perfectly divides both of them? In other words, leaving no remainders. Euclid
developed one of the first algorithms for finding a solution, called Euclid's
algorithm in his honour, dating from around 300 BC.
So the first algorithms even predate the word algorithm. All of this is to say that
the concept of an algorithm predates the development of digital computers. Any
one of us could perform the algorithm by following the simple step-by-step
instructions.
But we could find this tedious and time-consuming. A digital computer is then
well suited to these repetitive tasks and luckily, due to the transistor, can do each
simple task very quickly and reliably. Because of this naturally when we talk about
algorithms, the first thing we think of is a computer.
So what is the connection? Well, a computer program is a set of instructions
telling a computer what to do. So it resembles an algorithm, indeed a program
can implement a particular algorithm, when we translate our algorithm into a
programming language that a computer can interpret and understand.
In summary then, an algorithm is a mathematical concept that can be instantiated
as a computer program. So it is a more general concept. It is independent of
whatever programming language or machine code that we are using. But in this
course, we want to translate this concept, which is abstract from its abstraction
into a programming language.
In the Forum, I would like you to look for examples in the media where an
algorithm is mentioned. In particular, consider online newspaper articles and
perhaps news videos aimed at a general audience.

Mathematics To Digital computers

So how do we begin to translate algorithms into actual computer programs? Well,
before we start programming, we need to be able to actually describe the
algorithm. We'll do this in the next video. Even before we think of how to
concretely describe an algorithm, so that we can convert this description into a
program, we need to consider how you would write the input into a computer.

That is, how do we instantiate the input data which forms part of your problem?
Is it always possible to input arbitrary data into a computer? Let's consider the
following well-defined problem. For x 2+ 2 πx=π 2 what is x? Where π is the constant
we all know and love, that gives us the area of a circle from the radius.
We could use one of Al-Khwarizmi's algorithms to obtain the two solutions, x
equals the square
root of two minus one, all timesed by pi, or x equals minus one plus square root
of two, all timesed by pi. This is pretty straightforward
to solve for you and me, but now if we wish to plug
this equation into a computer, we have the variable x and
the numbers two and pi. A computer can understand
whole numbers like two, perhaps by storing this number in a finite amount of
memory. Since the computer is a
finite object that can store only a finite amount of information, this is all fine. So
any whole number can
be stored in a computer, and any rational
number can as well, since a rational number can be represented as a fraction
of two whole numbers, each being stored in a
finite amount of memory. The fraction is then
the simple application of a division on this data. The problem is with
the other number, pi. Pi is irrational. In fact, it is transcendental, and cannot be
written as a
fraction of two whole numbers. There is no way of storing pi in a finite amount of
memory
in any number system. This is why we use
the special symbol, pi, when talking about them. But we can resolve this by
allowing for
approximation of numbers. That is, any non-rational real number can be
approximated
by a rational number, where the difference between the two can be as small as
we like. For example, any
calculator display has some fixed number
of decimal points. So we can choose this difference, or the error in our
calculations,
to be much smaller than the fraction representing that last decimal point
in the calculator. This difference can
be interpreted as the precision of our calculation. The smaller it is, the more
precisely correct the computer handles the
input to our problem. Naturally, since the
input to a computer approximates the data of
our original problem, any algorithm producing an answer might give an
approximate answer. Ideally though,
the answer differs from the ideal answer
by a small amount, comparable to the difference
of the two inputs. So let's return to
historical algorithms to expand on this issue of
approximation even further. Let's revisit our problem
from the last video. Does x squared equal two have
an integer solution for x? Remember that we
had two algorithms, one that calculated
the square root, and another that looked
at squares of integers. Now, imagine a modified
version of this problem, which is the following:
x squared equals two, give x in decimal form. There are no irrational numbers in
the statement of the problem, but we know that
the square root of two is an irrational number, and so the correct solution
to this problem cannot be written into a finite amount
of memory on any computer. That is, we may need to produce an output to a
problem that
is also an approximation. What's really fascinating in
the history of algorithms, is that this issue of
approximation came up long before digital computers. The Egyptian-Greek
mathematician,
Heron of Alexandria, gave an algorithm for calculating an approximation of the
square root of a number. The algorithm, called Heron's
method, is very elegant. I will give you an
overview of how it works in the case of
the square root of two. So let's describe Heron's method. First, let's look at our
problem: of x squared equals two, give x to one decimal place. Well, we have
some
useful information here. We know that x must be
between one and two. Since x squared is equal to two, then x must be less than
two, and since x squared is two, then x must be greater than one, because one
squared equals one. So what we're going to do,
is we're going to take the mean of these two numbers, one and two, to get a
candidate solution for
our initial problem. So let's call the candidate x_g while the mean of
one and two is 1.5. So here we have the
x_g equals 1.5. So if x_g equals 1.5, then x_g squared
equals nine over four. Just by squaring three over
two which is equal to 1.5. Now, we see that nine over
four is greater than two, because two is equal
to eight over four. So we have the
following information: two over x equals x, remembering that x is
the square root of two. And we have that x_g, which was our candidate from
before,
is greater than x, because x_g squared
was greater than two. So if two over x
is less than x_g, we have that two over
x_g is less than x. So if two over x_g
is less than x, then we look at two over x_g, which is equal
to four over three, which is represented
as 1.3 recurring. We have that four over
three is less than x. So now, we have two numbers where we know x is
inbetween. We have four over three, which is two over x_g, and we have the
mean of one and two, which is three over two. So x must be between four over
three and three over two. So now, as we took the
mean of one and two, we can take the mean of four over three and three over
two. When you calculate that, you get 17 over 12, which is
equal to 1.416 recurring. It turns out to
one decimal place, this is as good as the
square root of two. If we wanted to go a bit further, and we wanted something
that was correct to more decimal places, we'd have to then consider
this new candidate x_g prime, which was equal to
17 over 12 squared. When we look at 17
over 12 squared, we find that this is
again greater than two. Thus two over x equals x, where x is the square
root of two, is going to be less than x_g prime, which implies that two
divided by x_g prime is less than x using the
same logic as before. So when we come to
calculate 17 over 12, and two divided by 17 over 12, we have these two numbers.
We have 24 divided by 17, and 17 over 12, and I've given the two
numbers in decimal form here. So we see that these
two numbers don't agree with each other in
the second decimal place. Because when I round
up 24 over 17, I have 1.41, whereas when I round up 17 over 12, I have 1.42. So in
order to get the square root of two
to two decimal places, I will then have to take the mean of these
two numbers again, which were 24 divided by
17 and 17 divided by 12. In this way, I keep reiterating
the process of taking the mean to get better
and better accuracy of the square root of two. Now, can you take this
process that I've just described and generalise it to the square root
of any integer? Also, how do we know when to stop for a particular precision?
Have a think about
these questions. In this section, we have given some background on
algorithms as something that exists independently of
modern digital computers. We have also discussed
what is special about digital computers when we
think about algorithms. In particular, we have covered approximation as a useful
tool when translating numbers from maths
into something that a computer can store,
manipulate and compute. As an example, we
have encountered our first algorithm,
Heron's method. Thanks to this discussion, we can qualify our notion of problems
in computer science. The input data and the
answer to a problem have to be stored in a finite
amount of computer memory. Therefore, irrational numbers in any number
system
must be approximated. We've now laid down
the groundwork in formally saying what
an algorithm is. We will next move on to
actually describing them.