Algorithms
Unit 1
Writing Algorithms
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Unit ILOs
Student will:
1. Learn the fundamentals of Algorithms
2. Learn the steps of software development
3. Learn the different types of Algorithms
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
M.A. Eljinini, PhD
Writing Algorithms
igning Solutions to Computer Based Probl
In this unit of work, you will learn how to design programs
that make a computer perform some simple tasks (or
solve some simple problems).
If you sit down in front of a computer and try to write a
program to solve a problem, you will be trying to do four
out of five things at once. These are :
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
M.A. Eljinini, PhD
Writing Algorithms
The Problem-Solving Steps
1. ANALYSE THE PROBLEM
1. Understand the problem (Define Requirements)
2. What are the Inputs, Processes, and Outputs?
2. DESIGN A SOLUTION/PROGRAM
1. Write the Algorithm (stepping, looping, and choosing)
2. I/O Screens, data files, network, etc.
3. CODE/ENTER THE PROGRAM
1. Write the source code
2. Compile and run the program (Implementation)
4. TEST THE PROGRAM
Debugging (Syntax error, Logical errors, run-time errors)
5. EVALUATE THE SOLUTION
(Ensure the solution is correct)
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
M.A. Eljinini, PhD
Writing Algorithms
1. ANALYSE THE PROBLEM
When you analyze a problem, you look at the problem in front of
you and decide what you need to do to solve the problem.
We need to define the problem:
What is the Output?
What is the Input?
What is the Processes?
Input -> Process -> Output
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
M.A. Eljinini, PhD
Writing Algorithms
[Link] A SOLUTION/PROGRAM
Program design is the most important part in producing a
computer program. This is the stage where you decide how your
program will work to meet the decisions you made during
analysis.
Program design does not require the use of a computer -
you will carry out your design using pencil and paper.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
M.A. Eljinini, PhD
Writing Algorithms
In your design, you will use a method called:
TOP DOWN DESIGN.
In using this method, you simply write down the steps in the correct
order, that you are required to perform, to solve the problem.
When all these steps are put together you have what is called an
ALGORITHM.
Algorithm:
A step-by-step set of instructions for solving a
problem in a limited number of steps. The
instructions for each step are exact and precise and
can be carried out by a computer.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
M.A. Eljinini, PhD
Writing Algorithms
Creating an Algorithm
To begin with we will look at three methods
used in creating an algorithm, these are
STEPPING, LOOPING and CHOOSING.
STEPPING OUT
First of all we will look at a method of creating an algorithm called
STEPPING.
This is where all the instructions needed to solve our problem are set
out one after the other. Here are some examples.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
M.A. Eljinini, PhD
Writing Algorithms
Input -> Process -> Output
PROBLEM1:
Find the sum of two numbers.
ALGORITHM:
1 Get two numbers (Input)
2 Add the two numbers together (Process)
3 W rite down the answer (Output)
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
M.A. Eljinini, PhD
Writing Algorithms
Input -> Process -> Output
PROBLEM2:
Change the temperature in Fahrenheit to Centigrade.
ALGORITHM:
1. Get temperature in Fahrenheit
[Link] 32
3 . M ultiply the result in (2) by 5
4. D ivide the result in (3) by 9
5 . W rite down the answer.
Both of these examples list the algorithm in an ordered set of steps.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Assignment #1: Stepping
Write down an algorithm for each of the following problems:-
[Link] the average of four numbers.
2. Change the time in seconds to minutes.
3. Find the product of two numbers (this means to multiply the two numbers).
4. Change a volume in pints to liters (there are 2.2 pints in every liter).
5. Find the difference between two numbers.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
More Complicated Problems
All of the problems you have just worked on are fairly simple.
Now we will look at some slightly more complicated problems.
To write an algorithm to solve a more complicated problem we will have to use a
bit more brain power.
We will need to have a bit of knowledge and may have to find out some more
information.
This information may be found from a few different sources, for example a
textbook, the library or from your teacher.
•As an example, let's work through a problem together:-
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
PROBLEM: Find the volume of a cone given its diameter and height.
The Input:
1. The diameter () لاــقطر
2. The height ( ) اـالرتـفاـعof the cone
The Output:
The volume ( ) لاــحجمof the cone.
To solve this problem, we must find out the mathematical formula that allows us to calculate
the volume of the cone.
Where could we find this formula if we don't already know it?
We could look in a mathematics textbook or we could even try asking our Mr. Google
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
M.A. Eljinini, PhD
Writing Algorithms
From Google - The Volume of Cone is: .
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
In Computer Form:
Volume = 3.14 × radius × radius × height ÷ 3
We still have a bit of a problem here, we don't know how to find the radius of the cone,
so again we ask google who tells us that the radius is half of the diameter.
So given this information we can now write our algorithm:-
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
THE ALGORITHM:
1. Enter diameter and height
2. divide the diameter by 2 to get the radius
3. multiply 3.14 by the radius
4. multiply the result in (3) by the radius
5. multiply the result in (4) by the height
6. divide the result in (5) by 3 to get the volume
7. write down the answer.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Another PROBLEM: Heat up a can of soup
ALGORITHM:
1. open can using can opener
2. pour contents of can into saucepan
3. place saucepan on ring of cooker
4. turn on correct cooker ring
5. stir soup until warm
This may seem a bit of a silly example, but it does show us that the order
of the events is important since we cannot pour the contents of the can
into the saucepan before we open the can.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
EXERCISES:
Write an algorithm for each of the following problems (remember you
may not have all of the knowledge you need to solve some of these
problems ~ ask for help):-
1) Find the average speed of a car given the journey time and the
distance travelled.
2) Find the volume of a cube given the length of a side.
3) Find the volume of a pyramid, given the length and breadth of its
base and its height
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
‰ GOING LOOPY ! [LOOPING]
To repeat an instruction or a set of instructions a number of times
to find the solution.
We will look at three different types of loops:-
i. the REPEAT UNTIL loop (do-while)
ii. the WHILE loop
iii. the FOR loop
now we will look at each of these a little closer....
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
i. REPEAT UNTIL LOOP
This type of loop keeps on carrying out a command or commands
UNTIL a given condition is satisfied, the condition is given with
the UNTIL command, for example:-
PROBLEM: To wash a car
ALGORITHM:
1 REPEAT
2 wash with warm soapy water
3 UNTIL the whole car is clean
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Write down an algorithm for each of the following problems
(All of these problems can be solved by using REPEAT UNTIL loops):-
1) To keep delivering newspapers until your paper bag is empty
2) To paint a wall
3) To complete a set of multiple choice questions
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
ii. While LOOP
In this type of loop the condition is given along with the WHILE
command and the loop keeps on carrying out a command or
commands until an END WHILE command is given, for example:-
PROBLEM:
To ask for a number more than 10, then stop when such a number
is given
ALGORITHM:
1 WHILE number given is less than 10
2 ask for a number more than 10
3 END WHILE
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Write down an algorithm for each of the following problems
(All of these problems can be solved by using WHILE loops):-
1. Keep asking for a number less than 5 and stop when a number less than 5
is given.
2. Keep asking for a password, and to give the message "accepted" when
the correct password is given.
3. Ask for the length of one side of a square, then keep asking for guesses
for the area of the square until the correct area is given (think about
stepping and looping).
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
iii. For LOOP
A FOR loop keeps on carrying out a command or commands, FOR a
given number of times. In this type of loop the number of times it
is repeated must be known. The commands to be repeated are
sandwiched between the FOR and END FOR commands, for
example :-
PROBLEM: To print the numbers from 10 to 20
ALGORITHM:
1 FOR number = 10 to 20
2 Print number
3 END FOR
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
NOTE:
In this loop, the value of number starts at 1 and goes up to 11. Its value increases by
one each time it goes through the loop until it reaches 11. Since the value of number
changes or varies, number is called a variable. A variable can be given any name provided
the name remains the same throughout your program. We will use the word variable
many times in this work.
VARIABLE :
A quantity or thing, which throughout a calculation, will change in value. Its
name should describe what it is representing e.g. number or liter or weight etc.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Another example is:-
PROBLEM: To print the 13 times table from 1 x 13 to 10 x 13
ALGORITHM:
1 FOR z = 1 to 10
2 Print 13 x z
3 END FOR
In this loop our variable is z, who’s value starts at one and then increases in value by 1
each time through the loop until z has the value of 10.
Line (2) of this algorithm prints the value of the variable z multiplied by 13.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Write down an algorithm for each of the following problems: (All of these
problems can be solved by using FOR loops):-
1) To print the 9 times table from 1 x 9 to 12 x 9.
2) To print a message of your choice 4 times.
3) To print a table giving the price of petrol from 1 liter to 25 liters, given
that the price of petrol is 69.5p per liter.
4) To print the values of a number squared from 2 to 20.
5) To print a table showing the area of circles with radii from 10cm to 20cm
(ask if you are not sure how to find the area of a circle).
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
‰ CHOOSING ! [IFs, THENs AND ELSEs]
So far we have come across the method of stepping commands
and looping commands. Now we will look at a method for making a
choice or a decision.
This technique is called CHOOSING, and uses the commands IF,
THEN and sometimes (but not always) ELSE.
With this type of command a condition is given with the IF
command followed by an action to be taken. If the condition is
satisfied, we follow it by the THEN command.
All a bit complicated? Well here are a couple of examples which
should make things a little clearer:-
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
PROBLEM: To decide if a fire alarm should be sounded
ALGORITHM:
1 IF fire is detected condition
2 THEN sound fire alarm action
Another example is:-
PROBLEM: To decide whether or not to go to school
ALGORITHM:
1 IF it is a weekday AND it is not a holiday
2 THEN go to school
3 ELSE stay at home
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
In your jotters write down an algorithm for each of the following problems
(All of these problems can be solved by using the choosing method):-
1) To decide whether or not to wash your hands.
2) To decide whether or not it is time to make lunch.
3) To print the largest of two given numbers.
4) To decide if a number is between 10 and 15, if it is print the number.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
‰ All together Now !
When you are programming you will find very few problems
that can be solved using just stepping, looping or choosing. In
fact, most problems will probably need a combination of all
three techniques. These examples combine STEPPING,
LOOPING and CHOOSING to find a solution to the problems
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
PROBLEM: To find the biggest number in a large set of numbers.
ALGORITHM:
1. Largest = 0
2. WHILE still number to check
3. Read number
Stepping 4. IF number is bigger than largest Choosing Looping
5. THEN largest = number
6. END WHILE
7. Print Largest
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
PROBLEM: To count the number of red boxes in a set of red, white
and blue boxes.
ALGORITHM:
1. number = 0
2. WHILE still boxes to check
3. Read color
4. IF color is red
5. THEN number = number + 1
6. ELSE number = number
7. END WHILE
8. Print number
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Write down an algorithm for each of the following problems (Stepping, looping
and choosing will have to be used in different combinations for each problem):-
1) To print the smallest number in a large set of numbers.
2) To print the average of a large set of numbers.
3) To check a list of job applicants and reject all those who either smoke or
drink.
4) To ask for a number, less than 50, and then keep adding 1 to it until 50 is
reached.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
PROBLEMS PROBLEMS PROBLEMS ! !
If you are asked to find a solution to a major problem, it can
sometimes be very difficult to deal with the complete problem all
at the same time. For example building a car is a major problem
and no-one knows how to make every single part of a car. A
number of different people are involved in building a car, each
responsible for their own bit of the car’s manufacture. The
problem of making the car is thus broken down into smaller
manageable tasks. Each task can then be further broken down
until we are left with a number of step-by-step sets of
instructions in a limited number of steps. The instructions for
each step are exact and precise.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
PROBLEMS PROBLEMS PROBLEMS ! !
Top Down Design uses the same method to break a programming
problem down into manageable steps.
First of all we break the problem down into smaller steps and
then produce a Top Down Design for each step.
In this way sub-problems are produced which can be refined into
manageable steps.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
An example of this is:-
PROBLEM: Ask for the length, breadth and height of a room.
Then calculate and display the volume of the room.
ALGORITHM:
1 ask for the dimensions
2 calculate the volume
3 display the volume
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Step 1: Refinement:
1. Ask for the dimensions
1.1 get the length
1.2 get the breadth
1.3 get the height
Step 2: Refinement:
2. Calculate the volume
2.1 volume = length x breadth x height
Step 3: Does not need any further refinement, so the design is
now complete
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
This was a straightforward problem and design. Another, slightly
more complicated example of Top Down Design is explained
below:-
PROBLEM: To repair a puncture on a bike wheel.
ALGORITHM:
1. remove the tire
2. repair the puncture
3. replace the tire
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Step 1: 1. Remove the tire
Refinement: 1.1 turn bike upside down
1.2 lever off one side of the tire
1.3 remove the tube from inside the tire
Step 2: 2. Repair the puncture
Refinement: 2.1 find the position of the hole in the tube
2.2 clean the area around the hole
2.3 apply glue and patch
Step 3: 3. Replace the tire
Refinement: 3.1 push tube back inside tire
3.2 replace tire back onto wheel
3.3 blow up tire
3.4 turn bike correct way up
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
Sometimes refinements may be required to some of the sub-problems,
for example, if we cannot find the hole in the tube, the following
refinement can be made to 2.1:-
Step 2.1: 2.1 Find the position of the hole in the tube
Refinement: 2.1.1 WHILE hole cannot be found
2.1.2 Dip tube in water
2.1.3 END WHILE
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
If we now put all of these refined steps together, we are left with
the complete algorithm needed to solve our problem.
1. Remove the tire
2. Repair the puncture
3. Replace the tire
1. Remove the tire
1.1 turn bike upside down
1.2 lever off one side of the tire
1.3 remove the tube from inside the tire
2. Repair the puncture 3. Replace the tire
2.1 find the position of the hole in the tube 3.1 push tube back inside tire
2.1.1 WHILE hole cannot be found 3.2 replace tire back onto wheel
2.1.2 Dip tube in water 3.3 blow up tire
2.1.3 END WHILE 3.4 turn bike correct way up
2.2 clean the area around the hole
2.3 apply glue and patch
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini
Writing Algorithms
In your jotters write down a Top Down Design for each of the following problems (Show your
initial algorithm and refined sub-problems as shown in the above example):-
1) To make a butter and jam sandwich.
2) To ask for the length of all the walls in a room, ask for the height of the room, calculate and
then display the total area of the room.
3) To calculate an employee’s wages using these conditions:
Ask for the employee’s name and how many hours they worked.
Up to 40 hours are paid at £4.00 per hour,
all hours over 40 hours are paid at “time and a half”
Display the employee’s name, their basic rate pay, their overtime pay and their total pay.
Algorithms Design Unit 1 Dr. Mohammad Ali H. Eljinini