Reading: Apply algorithm structure to give a solution
Apply an algorithm structure to give a solution
Inside this reading:
Introduction to developing algorithms
Analysis—defining the problem
Helpful tools for analysis
Design—defining the solution and creating an algorithm
Example 1: Store discounts algorithm
Using selection statements
Example 2: Test results algorithm
Using arrays
The modular approach
Example 3: Income and tax algorithm
Using objects
Desk-checking the solution
Desk-check example: Marks algorithm
Walk-throughs
Refining the solution
Checklist for refining
Using prototypes
Factors to consider for refinement
Summary
Introduction to developing algorithms
Before we start looking at developing algorithms, think about why we need them. Algorithms in programming/scripting language create a set of instructions for a computer to execute. The whole point of writing computer programs or scripts is to make the computer do work for us. As obvious as it sounds, it is important to understand that the computer doesn’t magically know what we want it to do. We need to create precise instructions.
If you don’t know what you actually want to achieve with an algorithm, or if you don’t accurately describe in the algorithm what you want done, the program written from it won’t do what you need it to do.
So how do we transform a problem into a computer program that executes a solution to that problem?
There are many models used to develop software programs and computer systems. These models work within what is called the software (or systems) development life cycle (SDLC). /More information
Try accessing the site and enter SDLC in the search box. Select either the definition for system design life cycle or systems development life cycle.A concise version of a SDLC can be defined in five steps:
1Analyse: Define the problem.
2Design: Define the solution and create the algorithm.
3Code: Write the instructions in a computer language.
4Test and debug: Ensure the program produces expected results.
5Document: Write user and technical documentation.
This very simple view of the whole process serves as a starting point for understanding how good software programs are developed. The process can be quite complicated, especially for large-scale software development. In this reading we will be focusing on relatively simple algorithms and be concerned mainly with Steps 1 and 2:Analyse and Design.
Analysis—defining the problem
It is vital that before we do anything else we analyse exactly what it is that we need the computer to do.
What is the problem are we are trying to solve or what task do we want to computer to perform?
The most important step in finding the correct solution is to fully understand the problem. Often there is a temptation to start writing the algorithm before the problem is fully understood. Resist this temptation, as it often leads to focusing on implementation issues rather than the functional issues that the problem presents. Implementation issues involve how you will do something while functional issues refers to what it is that you are trying to do.
If you don’t have enough information to solve the problem, try refining the program specifications. Ask:
- where the input comes from (keyboard, file, mouse, other?)
- what format it is in (numbers, text, a combination of both)?
- what the required outputs are and how will they be presented?
Identify the processing that will turn the inputs into the required outputs.
Helpful tools for analysis
Decision tables
Decision tables are a handy tool for refining complex selection constructs. A decision table lists causes and effects. The purpose of the table is to structure logic. Each column in the table represents one unique possible combination of values. These combinations are used to specify actions. A decision table is useful for handling the complexity of multiple courses of actions based upon the values of one or more variables. /Tools on the web
On the Catalyst Development website at a short overview of the history of decision tables.A number of different diagrams are useful in organising information for a clearer idea of the problem to be solved. The Visual Paradigm website shows some good sample diagrams at
Here is a very basic example of a decision table.
MatravilleCollege wish to print out the results of a student English test:
- The result to be printed for a test result under 50 is FAIL.
- The result to be printed for a mark from 50 to under 70 is PASS.
- The result to be printed for a mark from 70 to under 83 is CREDIT.
- The result to be printed for a mark from 83 to 100 is a DISTINCTION.
We could use a decision table to organise this information.
Table 1: Decision table example
Student mark—cause / Result—effectLess than 50 / FAIL
Equal to 50 and less than 70 / PASS
Equal to 70 and less than 83 / CREDIT
Equal to or greater than 83 / DISTINCTION
Design—defining the solution and creating an algorithm
One part of finding a solution is to read the functional specifications of the problem and try to answer the following questions.
- What are the inputs to the algorithm? Where do they come from? What type of input is it, eg numbers or text?
- What is the expected output from the algorithm?
- What program blocks can be recognised (sequence, selection, iteration)?
- How is the solution composed from these blocks, ie how are the blocks sequenced or nested?
- What variables can be recognised? What are their initial and final values?
Example 1: Store discounts algorithm
The Bush Lane clothing store is about to have a sale with all items in store discounted by 10%. In addition to this discount, when a customer spends more than $200 in the store they will receive a further 10% discount. The store manager would like a script to be written to do the calculations for the sales people.
The sales person will enter the total price of the goods purchased by the customer. The program will print the individual discounts, the total discount, and the discounted sale price.
Let’s look at what we need to do to write an algorithm that will do the correct calculations for the problem.
First, can we identify the inputs?
The specification states that that the total price of goods purchased will be entered.
Next, what is the expected output?
We would assume that the discounted total price is what the sales people would most require. But do they need to see any information about the discounts applied? If so, should the total discount be displayed or, when applicable, both discounts (the 10% store-wide and the over $200 discount)?
Let’s assume that the store manager would like sales people to see:
- the original sale price entered
- the store-wide discount amount
- the over $200 discount amount
- the total discount amount
- the discounted total price.
From the inputs and outputs we can start identifying variables that our solution requires.
Input / Original sale priceOutputs / Original sale price, store wide discount amount, over $200 discount amount, total discount amount and total discount price.
Once you are clear on the inputs and outputs needed, you then look at ways to process the input to produce the output. Our first go at the problem breaks it into three general parts:
1accepting inputs
2processing the inputs
3generating the output.
These three stages represent a simple model for computer data processing as shown below:
Inputs →Processing →Outputs
By dividing the problem up into these basic phases, we now have three smaller programming problems to solve.
Start with broad statements, and then refine the code
A good way to start is to use a top-down approach: to start with very broad statements and refine each statement until it is a step that can be easily coded. Let’s begin our algorithm design by using three basic steps of the input-process-output model:
Algorithm 1.0
GET inputs
PROCESS
DISPLAY outputs
We know what inputs and outputs are required, and we can describe the process a little more clearly with the phrase ‘calculate discounts’. Inserting these refinements gives us:
Algorithm 1.1
GET originalSalePrice
CALCULATE discounts
DISPLAY originalSalePrice
DISPLAY storeWideDiscount
DISPLAY over200Discount
DISPLAY totalDiscount
DISPLAY discountSalePrice
Now let’s now turn our attention to what processing needs to be done to calculate the discounts. We need to calculate the store-wide discount, the extra discount for purchases over $200, the total discount, and the discounted sale price. So we will now expand the general ‘calculate discounts’ step with these refined steps:
Algorithm 1.2
GET originalSalePrice
calculate storeWideDiscount
calculate over200discount
calculate totalDiscount
calculate discountSalePrice
DISPLAY originalSalePrice
DISPLAY storeWideDiscount
DISPLAY over200Discount
DISPLAY totalDiscount
DISPLAY discountSalePrice
Firstly, we need to calculate the store-wide discount. This is fairly easy. The storeWideDiscount is 10% of the originalSalePrice. How do we calculate 10% of something? We simply multiply the originalSalePrice by 0.1 (0.1 is 10 divided by 100).
So the store-wide discount is calculated with the statement:
SET storeWideDiscount = originalSalePrice * 0.1
Now let’s see what we need to do to calculate the over200Discountamount. First, we need to see if the originalSalePrice is over $200. If it is, we will set the over200Discount amount to 10% of the originalSalePrice, otherwise we will set it to 0.
Using selection statements
A selection statement can deal with this task. Let’s start with creating the test to determine if the originalSalePrice is greater than $200. We will use the > symbol to indicate a test for ‘greater than’ as it is commonly used in programming and scripting languages to represent this type of test.
IF originalSalePrice > 200 THEN
Now add the statements for when the test evaluates to true:
IF originalSalePrice > 200 THEN
SET over200Discount = originalSalePrice * 0.1
and finally, add the statements to the ELSE part for when the test evaluates to false:
IF originalSalePrice > 200 THEN
SET over200Discount = originalSalePrice * 0.1
ELSE
SET over200Discount = 0
ENDIF
Now that we have calculated both discounts let’s add our refined pseudocode to the right place in our algorithm.
Algorithm 1.3
GET originalSalePrice
SET storeWideDiscount = originalSalePrice * 0.1
IF originalSalePrice > 200 THEN
SET over200Discount = originalSalePrice * 0.1
ELSE
SET over200Discount = 0
ENDIF
calculate totalDiscount
calculate discountSalePrice
DISPLAY originalSalePrice
DISPLAY storeWideDiscount
DISPLAY over200Discount
DISPLAY totalDiscount
DISPLAY discountSalePrice
Would it have mattered if we placed the IF-THEN-ELSE construct before we set the storeWideDiscount?
Not at all. The calculations for the storeWideDiscount and the over200Discount are independent of each other. That is, they do not rely on each other for determining their values. You should always check to see that you have assembled your blocks of code and sequences in the correct order!
The final pieces of processing are to add the two discount amounts to calculate the totalDiscount and to subtract that from the originalSalePrice to determine the discountSalePrice. The final processing steps can be achieved with the following statements:
SET totalDiscount = storeWideDiscount + over200Discount
SET discountSalePrice = originalSalePrice—totalDiscount
Would it matter if we swapped the order of these statements?
It most certainly would! The discountSalePrice depends on both the originalSalePrice and the totalDiscount. If you don’t calculate the totalDiscount first, then the discountSalePrice will not include the discount amounts and would be incorrect.
Let’s now complete the algorithm by inserting these final two statements.
Algorithm 1.4
GET originalSalePrice
SET storeWideDiscount = originalSalePrice * 0.1
IF originalSalePrice > 200 THEN
SET over200Discount = originalSalePrice * 0.1
ELSE
SET over200Discount = 0
ENDIF
SET totalDiscount = storeWideDiscount + over200Discount
SET discountSalePrice = originalSalePrice—totalDiscount
DISPLAY originalSalePrice
DISPLAY storeWideDiscount
DISPLAY over200Discount
DISPLAY totalDiscount
DISPLAY discountSalePrice
Note: We could display each piece of information immediately after we have set the value rather than display it all at the end. It does not really matter—either method would work. To separate processing steps from output steps when it has no bearing on how the solution performs can make it simpler to error check and modify the code later.
Let’s look at another problem, starting with the statement of the problem.
Example 2: Test results algorithm
MatravilleCollege need an algorithm to find the average of five test results. The operator at the keyboard will input the total marks possible for the test followed by the five test results. The college would like to have displayed on the screen: the marks input, the percentage for each test result and the average of the test results as a percentage.
Remember to write a simple version of the algorithm using a few general steps.
Algorithm 2.0
GET inputs
PERFORM calculations
PRINT outputs
Now refine each step adding a few details to each part.
Algorithm 2.0 / Algorithm 2.1GET inputs / GET marks possible
PERFORM calculations / GET test marks
Calculate test mark percentages
Calculate average percentage
DISPLAY outputs / DISPLAY original test marks input
DISPLAY test marks as percentages
DISPLAY average percentage
Identify where the control structures of sequence, selection and iteration could be used.
Algorithm 2.1 / Identify constructsGET marks possible / GET marks possible
GET 5 test marks / Loop?
CALCULATE 5 test mark percentages / Loop?
CALCULATE average percentage / Calculate average mark
DISPLAY 5 original test marks input / Loop?
DISPLAY 5 test marks as percentages / Loop?
DISPLAY average mark as percentage / DISPLAY average mark as percentage
Continue the process of refinement until each part is well defined. Let’s look at refining the step GET 5 test marks. We could simply write five separate statements as follows.
GET test mark 1
GET test mark 2
GET test mark 3
GET test mark 4
GET test mark 5
This seems fine—but what if we had 100 test marks? It would be tedious writing a GET statement 100 times! The GET test mark statements are examples of repetitive tasks that we should be able to express in a loop.
Single statements / Replace with loopGET test mark 1
GET test mark 2
GET test mark 3
GET test mark 4
GET test mark 5 / Loop to GET 5 test marks
When loops are involved, you should decide which type of loop to use.
- FOR loops are counting loops and since we know how many results to process, a FOR loop will suit our situation.
- WHILE loops are used when a condition must be met before the statements within the loop are executed.
- A REPEAT loop is used when the statements contained in the loop are to be executed at least one time before testing the condition.
It is definitely worthwhile identifying any processing that can be done with a loop, as it reduces the number of individual statements that need to be written and adds flexibility into the algorithm. But how do we construct these loops to process data?
Let’s try constructing the loop to GET the 5 test marks. We will use a FOR loop to GET the 5 marks.
FOR counter = 1 TO 5
GET mark
ENDFOR
This seems to make sense, but let’s see what happens. The first time through the loop we get the first number and place it into a variable called mark. The next time through the loop we get the second number and place it in the same variable called mark.
But wait a minute, didn’t we just store the second mark in the same place that we stored the first mark? That means we have overwritten the first mark with the second mark before we have had a chance to use the first mark. The first mark is now gone! This is not correct. We want to get all 5 marks then do some processing with each of them later on. So how do we use a loop to get the 5 marks? The secret is the array.
Using arrays
Before finalising the design of our algorithm it is worth looking at the data structure called an array.
An array is like a suburban street. The elements that make up the suburban street are the houses. Each house doesn’t have its own unique name but simply a number that is unique in that street. The street has a name like ‘Smith’. To refer to any one house in that street we use the street name and house number such as ‘10 Smith Street’. This is a simple way of saying ‘the 10th house in street called Smith’.
An array is similar in that it is essentially a group of variables that share a common name. Each variable can be referred to by the array name and its own unique number called the index.
In our problem we have five marks to deal with. Each mark has the same data type; they are all numbers. We can think of individual variables that we might have called mark1, mark2, mark3, mark4 and mark5 as elements of the array called marks.
To refer to the first test mark (the variable we may have called mark1) in the array called marks, we can use the notation marks[1]. To refer to the second test mark, the variable we may have called mark2, we would use mark[2]. The number enclosed in the brackets [ ] is the index to the array and is similar to the house number in the street analogy. Referring to individual locations in an array using the name and an index variable within a loop is the preferred way to process large amounts of data.