|
|
|
Lecture 1 |
|
Introduction To Programming & Algorithms |
|
|
|
|
|
A solution can be found for most problems. |
|
Often a solution is “ad-hoc”. |
|
For example, you come to your front door and it
is locked. What do you do? |
|
You fish out your key, unlock the door, then
enter. |
|
Larger problems may need more work |
|
Solution may take longer to create |
|
Solution may be Complex |
|
If complex, solution may need to be written
down. |
|
|
|
|
|
|
Algorithm, A prescribed set of well-defined
rules or instructions for the solution of a problem. |
|
Source:
Oxford Dictionary of Computing |
|
|
|
An algorithm is a precise set of
instructions which specifies how a task is to be done. If carried out in the exact sequence
given, then the task will be done successfully. |
|
Source: Richard Foley - Introduction To
Programming Principles: |
|
Turbo Pascal |
|
|
|
|
|
An algorithm can therefore be thought of as a
formal solution to a problem. |
|
|
|
|
|
|
|
We all use algorithms regularly in our life: |
|
Cooking Recipes |
|
B&Q Flat Pack instructions |
|
Instructions on programming a VCR |
|
|
|
|
Understand the Problem! |
|
|
|
Before a solution can be created, the problem
must be understood. |
|
If you don’t understand the problem – how can
you create a solution? |
|
Complete the following Fibonacci series: |
|
1 1 ? ? ? ? ? |
|
|
|
|
How many of you completed the series? |
|
How many of you didn’t know what a Fibonacci
series was? |
|
To complete the series, you must know what a
Fibonacci series is |
|
Answer: 1 1 2 3 5 8 |
|
(add previous 2 numbers to get the next) |
|
|
|
|
The key to creating an algorithm is therefore: |
|
|
|
Understanding the Problem |
|
|
|
In a programming context, this often means that
some research may be needed. |
|
|
|
|
|
Designing a Solution |
|
Problem solutions – algorithms – are often set
down in a prescribed formal manner. |
|
Why? |
|
If the solutions to various problems are all
written in a similar manner … |
|
Then those who have to interpret the solution
will be more likely to understand the solution as placed before them. |
|
|
|
|
|
|
Numbering The Stages |
|
As most solutions require several steps, it is
good practice to number each step sequentially. |
|
|
|
Problem: Enter house via locked door |
|
Solution: 1. Fish out key |
|
2.
Unlock door |
|
3.
Enter house |
|
|
|
|
Functional Decomposition |
|
Some steps in our solution may be complex. |
|
It may be necessary to split one of the steps in
our solution into several “sub-steps” |
|
Imagine someone from a Nomadic tribe with no
concept of door locks. He may say: “How
do you unlock a door?” |
|
|
|
|
Here, we split stage 2 of our solution into its
various “sub-stages”. |
|
|
|
2. Unlock Door |
|
2.1 Place key in keyhole |
|
2.2 Turn key clock wise until lock opens |
|
2.3 Remove key from keyhole |
|
|
|
|
Algorithm Numbering |
|
The original series of steps for our solution,
called the Top Level Solution were numbered in sequence. (1 to 3 in our
example) |
|
In our second stage, the “sub-steps” were
numbered in such a way that their position in the algorithm is clear. (As
they were sub-steps of step 2, they were numbered 2.1, 2.2 etc.) |
|
Further levels of decomposition are possible,
for example if we split stage 2.1 up, they would be numbered 2.1.1, 2.1.2
etc. |
|
|
|
|
|
For this weeks lab, create numbered
algorithms to complete the following tasks: |
|
|
|
Make a cup of tea |
|
Boil and egg |
|
|
|
For each of the above, create a Top Level
Solution decomposing where appropriate to a second level. Do not go any further down than a second
level. |
|
Notes