Hierarchy Charts

Top-down design is an approach to problem solving that takes the goal and breaks it down into a series of subgoals that lead to the solution.

A hierarchy chart can be used to describe how this is done in a visual form.

Finding The Hypotenuse

The following diagram shows the steps involved in working out the length of the hypotenuse of a right-angled triangle given the lengths of the other two sides. The top box shows the problem that we are solving. From left to right, the steps that lead to the solution can be read off in order on the bottom row of the diagram.

With a more complex problem, you might break down the subgoals into subsubgoals adding rows beneath the current layer of subgoals.

Stepwise Refinement

Finite State Machines

Also see Video at bottom of Page

What Is A Finite State Machine?

If we start by simply interpreting the words that make up the name of the thing, we can say that a Finite State Machine is a machine that can be in only one of a fixed number of states at any time.

Think about a simple torch which has a single button for on and off. If the torch is off, pressing the button will turn it on. If it's on, pressing the button switches it off.

At the simplest level, the torch can therefore be said to have two states. It is an example of a finite state machine. The outcome of pressing the button depends on the state of the machine when the button is pressed.

Many types of digital machine are examples of FSMs. The computer you are probably using to view this page is one too. This is one of the reasons that you study this topic in Computing - because of the extent to which this concept relates to the architecture of the machines we call computers. It is also here because FSMs can be an important part of software development. There are plenty of tools (proprietary and open source) which allow you to represent FSMs visually using standard diagrams called State Transition Diagrams or Statecharts. You can also represent an FSM in a table called a State Transition Table. Using these tools, developers can work on abstract models of the software being developed. Many of these tools have provision for automatic code generation which allows designs to be implemented efficiently.

State Transition Diagrams

The torch described above can be represented using a State Transition Diagram like the one below.

The boxes are the possible states for the machine. The arrows indicate a transition between two states. The pointer indicates the direction of the change. Each transition is labelled with the input that caused the transition to occur.

Another Example

Imagine a combination lock. It has a keypad with the digits 0 - 9. You need to enter the combination 1, 3 & 5 to unlock the treasure.

When we do a state transition diagram for this, we might do something like this,

The arrow pointing into the locked state indicates the initial state. The double circle for the unlocked state indicates the goal or accepting state.

If you are struggling to follow the diagram, print it out and place your finger on the state marked locked. There are 2 arrows pointing out of this state. They are labelled 1 and not 1. Imagine that something other than a 1 is entered. This arrow points to the locked state - we're going nowhere. Now follow the arrow labelled 1, the correct first digit of the combination. This takes us to State 2, one digit has been correctly entered. From here the paths either take us to State 3, two digits correctly entered or, if we don't enter a 3, return to the initial state, locked. From State 3, we can reach the goal by entering a 5. At this point, we get the treasure.

The FSM above have no output. An FSM with no outputs is called a Finite State Automaton. FSAs have an initial state and at least one accepting state or goal.

Mealy Machines

When an FSM produces an output with each transition between states, it is known as a Mealy Machine. There is no accepting state. In a Mealy Machine, the output depends on both the previous state and the input.
Inputs and outputs are represented in state transition diagrams as you see below.

Vending Machine Example

Imagine a vending machine that sells cans of carbonated sugar water. This one isn't one of those machines that sells drinks made by those scummy international companies with their anti-union practices and hateful exploitation of the world's poorest people. As a result, it only costs 15p for each can of carbonated sugar water.

The machine accepts only 5p and 10p coinage. When 15p has been inserted into the machine, a can of carbonated sugar water is released.

Our Mealy Machine will have only 3 states. These are,
1.Got 0
2.Got 5p
3.Got 10p

When the machine has no money entered towards the cost of the can, it is in the state Got 0. Inserting coinage changes the state. Look carefully, this machine can cater for the different ways that you can arrive at 15p using the two coins. If two 10p coins are inserted, a can is released and the machine moves to the Got 5 state. An extension to this machine might be to cater for the release of change after or before the purchase is completed.

Finite State Machines - June 2012.pdf
AS Comp1 Finite State Machines 1.ppt
AS Comp1 Finite State Machines 2.ppt
Conversion Machine Worksheet.doc

State Transition Tables

A state transition table is a means of recording all of the possible states and transitions for a Finite State Machine. Some software modelling tools will generate code or state transition diagrams from such a table.

Let's return to the model we made for the vending machine. The state diagram looked like this,

!!!FSM Vending Machine!!!

We can record the states and transitions using the following table,

This model could be extended to accept other coinage and to return change to the customer. Currently, the model only shows what happens when the correct coins are entered.

Decision Tables

Decision tables are used to model logic by observing all of the possible conditions and outcomes that can occur.

Imagine that we want to model a person's entitlement to benefits during a period of unemployment. If the person is not 18 or over, they get no entitlement, if they are, they get benefits if they have savings of less than £10000.

We can write this logic out as follows,

If Age >= 18 And Savings < £10000

Then Output "Entitled"

Else Output "Not Entitled"

The corresponding decision table for this scenario is as follows,

Y & N are used to indicate the possible outcomes of the conditions. An X indicates the action that results from each combination of outcomes. The pattern of Ys & Ns in the table is predictable. Look at what happens if we add a third condition to the table.

If Age >= 18 And Savings < £10000 And Out_Of_Work = True

Then Output "Entitled"

Else Output "Not Entitled"

Decision Tables Exercises Teacher Answers.doc

Decision Tables Exercises.doc

Algorithm Design

Algorithm Design

Back at the start of this section we defined the term algorithm as a process that achieves a useful outcome. We noted that an algorithm is not written in any specific programming language and may be implemented using different key words and statements depending in which language is chosen to implement the algorithm as a program.

The section on stepwise refinement gave you an example in the following structure table,

0 Do The Weekly Shopping
0.1 Prepare List
0.1.1 Check Cupboards
0.1.2 Check Fridge
0.1.3 Write Down What Is Needed
0.2 Do Shopping
0.2.1 Drive To Shops
0.2.2 Select Items
0.2.3 Pay For Items
0.3 Put Shopping Away
0.3.1 Unpack Shopping
0.3.2 Put Some Items In Fridge
0.3.3 Put Some Items In Cupboards

Having gone through this process, adding detail to each of the vague steps we began with, we can essentially see the terms that are indented furthest as being our algorithm.

We could therefore see our algorithm as being,

Check Cupboards
Check Fridge
Write Down What Is Needed
Drive To Shops
Select Items
Pay For Items
Unpack Shopping
Put Some Items In Fridge
Put Some Items In Cupboards

When we write our instructions in the order in which they should be executed, we are showing an appreciation of sequence. This is the simplest of concepts in algorithm design</td><td>the statements are executed in order and, when we design our own algorithms, we must pay attention to the sequence of our instructions.

Selection

Sometimes our actions will depend on the outcome of a decision (see Decision Tables). We use the term Selection to refer to the parts of our algorithms that depend on the outcome of a decision.

Iteration

Sometimes an algorithm will require something to be done repeatedly until a condition is met. For example, when we inflate a tyre, we continue to add air until the tyre is fully inflated. Sometimes we repeat statements until a condition is met, sometimes we repeat them while something remains true.

We use the term Iteration or Repetition to refer to those repeating sections of our algorithm.

Assignment

We use the term assignment for an expression where the left hand side is assigned the value of the right hand side.

For example,
Number ← 5
The left-pointing arrow is a common symbol for assignment.

Introduction to Algorithms.ppt

Structured English

Structured English is a way of describing an algorithm using a small subset of the English language and a few simple conventions.

There are no clear standards for Structured English.

Sequence

An instruction in Structured English should being with a verb.

For example,

INPUT hours worked
MULTIPLY hours worked by rate of pay
OUTPUT pay

When you have reached the section of the programming guides on procedures and functions, you will learn that it is common to group a series of statements like this into one logical block of code with a unique name in the program.

Imagine we had labelled the above algorithm with the unique name CalculatePay. We might then refer to this group of statements as follows,

DO CalculatePay

Assignment

In Structured English we use the term SET when we assign a value to a variable. For example,

SET hoursworked to 40

Selection

We have 3 main options to show selection in our algorithms,

1. IF ... Then
2. IF ... Then ... Else ...
3. SELECT ...

For example,

IF error found
THEN OUTPUT "Error" 

IF error found
THEN OUTPUT "Error"
ELSE OUTPUT "All Fine"

SELECT VALUE errorNumber
1: OUTPUT "Error Number 1"
3: OUTPUT "Error Number 3"
5: OUTPUT "That's a bad miss"
END SELECT 

The indentation is good practice, makes the code easier to read and has to be seen as a compulsory part of the process.

Iteration

We can represent repetition in our algorithms using the following constructs in Structured English

FOR EACH employee
DO CalculatePay 

REPEAT UNTIL no more employee records
READ next employee record
READ hours worked
READ pay rate
MULTIPLY pay rate by hours worked

DO WHILE more employee records to process
READ next employee record
READ hours worked
READ pay rate
MULTIPLY pay rate by hours worked 

Pseudocode

Pseudocode is so named to reflect the fact that although it is like code, it is not actual programming code. Pseudo means false.

The syntax of pseudocode is less strict than the syntax of a programming language</td><td>there is no compiler or debugger telling you that you have not placed a semi-colon at the end of the line.

There are lots of versions of pseudocode and no single standard.

We tend to write a little more detail in pseudocode than we do in Structured English. It is, perhaps, a little closer to the code we may write in our programming language.

Sequence

As before, statements are written in the order in which they need to be executed. Look carefully at the example to see how input, output and assignment are handled in pseudocode.

Input Hours

Input Rate

Wage ← Hours * Rate

Output wage

Selection

If hours > 40

THEN
overtime ← hours</td><td>40

pay ← pay + overtime * 3.75
EndIfIf average > 50

THEN Output "Pass"
ELSE Output "Fail"

EndIfIf x In [0 ... 9, A, B, C, D, E, F]

THEN Output "Valid Hex"
ELSE Output "Bad Hex"

EndIfCase x Of

1: Output "January"

2: Output "February"

3: Output "March"
EndCase

Iteration

For x ← 1 To 12

Output x

EndFor 

This executes the statement, Output x 12 times. The variable x is called a stepper variable. Each time the loop executes, the value of x increases by 1. The output from this algorithm would be the numbers 1 to 12.

Repeat

x ← x + 1

Until x = 6

In this example, the statement within the construct will be executed at least once. If the code prior to that shown in the example makes x have a value that cannot reach six by repeatedly adding 1, the loop will continue indefinitely or until an overflow occurs because these is not enough memory to store the value of x. The loop executes at least once.

While x < 6 Do

x ← x + 1

EndWhile

In this example, the value of x is examined before executing the statements contained within the loop. The statement will not execute if, at this point in the program, x has a value of 6 or greater.

For Each x In [5, 7, 9]

Output x

EndFor

From Pseudocode To C#

The following pseudocode describes an algorithm for adding two numbers together and reporting their sum and average.

Input Number1

Input Number2

Sum ← Number1 + Number2
Average ← Sum / 2

Output Sum, Average

When we write this in C#, we get the following,

double number1;

double number2;

double sum;

double average;

Console.Write("Input Number 1: ");

number1 = System.Convert.ToDouble(Console.ReadLine());

Console.Write("Input Number 2: ");

number2 = System.Convert.ToDouble(Console.ReadLine());

sum = number1 + number2;

average = sum / 2;

Console.WriteLine("Sum: {0}, Average: {1}", sum, average);

Console.ReadLine();

There is quite a difference. When we write an algorithm, we are more concerned with whether we are doing the right thing to achieve the result than we are with the exact form of the statements that we need in a programming language. As a result, our actual code is longer and more fussy. Ultimately, it is easier to see if the logic of the algorithm is correct in the shorter, more concise form offered by pseudocode.

Programming Flowcharts

Flowcharts are used in a variety of contexts to describe and plan different types of objects. Program flowcharts describe or model programs and algorithms independently of any programming language.

You will see all sorts of symbols in tools or shapes for flowcharting. To model an algorithm or program, we need the following symbols.

Example

The following example shows how you can use the decision shape to model iteration within a program flowchart.

Dry-Running

Trace tables are used by programmers to track the values of variables as they change throughout the program. This is useful when a program is not producing the desired result.

Look at the following program extract. The program is supposed to calculate the sum of the squares of a series of numbers entered by the user. The user enters -1 when they have reached the end of their list of numbers.

n:= 0;

total:= 0;

while n<>-1 do

begin

write('Please enter a number');

readln(n);

total:= total + n * n;

end;

writeln('Total= ', n:8:2);

Assume that the following order of input is used</td><td>2, 5, 3, 1, -1.

To find out why this program is not working, first work out what the expected result should be.

To make a trace table, we write out the variables used in the program and any expressions that are evaluated by ifs or whiles. We read the program, line by line, writing in the values as they are set and only write information into the table when it changes.

Copy and complete the table to show what this code actually produces. Explain the nature of the problem.

Another Algorithm

x ← 4
y ← 3

Result

Repeat

Result ← Result * x

y ← y - 1

Until y = 0