O Level CS P2 Problem Solving and Design
To view other notes of GCSE \ IGCSE Computer Science Click Here.
Top down/modular design
1. Advantages of designing a solution to a problem by splitting it up into smaller problems.
2. Produce and describe top-down/modular designs using appropriate techniques, including structure diagrams, showing stepwise refinement
Definition: A Top-down design is when a problem is split into smaller sub-problems, which themselves are split into even smaller sub-problems until each is just one element of the final program.
Benefits and drawbacks of modular program
| Benefits | Drawbacks |
| Smaller problems are easier to understand | Modules must be linked and additional testing must be carried out to make sure that the links work correctly |
| Smaller problems are easier to test and debug | Programming must ensure that cross-referencing is done |
| Development can be shared between a team of programmers - each person programming different modules according to their individual strengths | Interfaces between modules must be planned |
| Code from previously developed modules can be re-used |
Structure Diagrams
A structure diagram is a pictorial representation of a modular system.
Stepwise refinement
Stepwise refinement is the process of developing a modular design by splitting a problem into smaller sub-tasks, which themselves are repeatedly split into even smaller sub-tasks until each is just one element of the final program.
1. produce an algorithm for a given problem either in pseudocode form or the flowchart form
2. understand algorithms presented in the form of program flowcharts and pseudocode
What is an Algorithm?
An algorithm is a sequence of steps, which perform a specific task. In computing, algorithms are usually represented as a program flowchart, or in pseudocode.
What is a program flowchart?
A program flowchart is a pictorial representation of an algorithm. Program flowcharts consist of special symbols:
Here is an example of a flowchart to output the first five squared numbers:
What is Pseudocode?
Pseudo-code is a simplified form of programming code that uses common programming terminologies, but does not use the strict syntax rules of a programming language.
An example of a pseudocode algorithm:
{
BEGIN
INPUT CardNumber
REPEAT
INPUT PIN
IF PIN is wrong for this CardNumber THEN
OUTPUT “Wrong Pin”
END IF
UNTIL Pin is correct
INPUT Amount
IF there are enough funds THEN
Dispense Cash
Update customer’s balance
ELSE
OUTPUT “Sorry, insufficient funds”
END IF
END
}
Algorithms should be evaluated using the following criteria:
- Efficiency
- Correctness
- Appropriateness
Efficiency
An algorithm’s efficiency can be judged in terms of:
- Speed: How quick the algorithm produces the required output.
- Memory requirements: How many lines of code the algorithm contains.
Correctness
Although an algorithm is expected to produce the correct outputs, correctness can still be measured in terms of:
- Accuracy: How many decimal places produce output with greater accuracy (e.g. more decimal places)
- Range: Will the algorithm work with the complete range of inputs? Or can it only deal with positive numbers, whole numbers, numbers below 1 million, etc.
- Reliability: Will the algorithm always produce correct output within the range that it is designed to work? Or are there values which it will not accept (e.g. zero).
Appropriateness
Appropriateness can be measured in terms of:
- Length: If the problem is simple then a short algorithm would normally be expected.
- Speed: if the output needs to be generated quickly, then the algorithm must be able to generate output quick enough.
- Memory requirements: An algorithm controlling a washing machine must not require a lot of memory!
Flow Charts
This section covers the use of flow diagrams (charts) in the production of algorithms. This topic must not be confused with “Systems flowcharts” as those are different and these are covered in a different section (Systems analysis).
This section primarily covers four areas:
- Common flow chart symbols
- Writing flowcharts to solve problems
- Dry running of flowcharts to determine its function and outputs
- Exercises to test the above concepts
- Topical past paper question
Common flowchart symbols
Understand and use assignment statements
What is an Assignment?
An assignment is an instruction in a program that places a value into a specified variable. Some typical assignments are:
Note that the last example is a common method used to increment the value of a variable. It could be read
as:
(The new value of “Counter” is its existing value plus one
Arithmetic operators including operators for integer
Addition, subtraction and multiplication
| Operator | Meaning / Purpose | Example | Result |
| + | Addition | Result = 3 + 4 | 7 |
| - | Subtraction | Result = 7 - 3 | 4 |
| * | Multiplication | Result = 4 * 8 | 32 |
Powers
| Operator | Meaning / Purpose | Example | Result |
| ^ | Power | Result = 3 ^ 3 | 9 |
Division
A result of a division such as 17 ÷ 4 can be expressed either as a real (4.25) or as two integers (4 remainder 1).
The integer method, in most programming languages, uses the operators DIV and MOD.
| Operator | Meaning / Purpose | Example | Result |
| / | Division | Result = 10 / 2 | 5 |
| DIV | Integer Division - returns the result of a division after ignoring the decimal portion of all numbers | Result = 14 DIV 5 7.2 DIV 3.9 ( = 7 DIV 3) | 2 2 |
| MOD | Remainder - returns the remainder of the division of two integers | 14 MOD 5 18 MOD 6 3 MOD 7 | 4 0 3 |
Relational operators, eg. =, <, <=, >, >= and <>
Relational operators are used in the format: [Expression] [Operator] [Expression] and will always return a Boolean (True or False) value.
Relational operators are typically used with the “IF” selection and also within conditional loops (REPEAT-UNTIL or WHILE-WEND).
In the following table, the variables “a” and “name$” have the following assignments:
a <- 3+5
name$ <- "JAMES"
| Operator | Meaning / Purpose | Example | Result |
| = | Equal = tests if two expression are identical | IF a = 8 IF name$ = "JANET" IF a = 14 | True False False |
| < | Less than - tests if the first expression is less than the second | IF = a < 8 IF name$<"JANET" IF a < 14 | False True True |
| > | Greater than - tests if the first expression is greater that the first | IF a > 8 IF name$ > "JANET" IF a > 14 | False False False |
| <> | Not Equal - tests if two expressions are different | IF a <> 8 IF name$ <> "JANET" IF name$ <> "JAMES" IF a <> 14 | False True False True |
| <= | Less than or Equal | IF a<= 8 IF name$ <= "JANET" IF a <= 14 | True True True |
| >= | Greater than of Equal | IF a >= 8 IF name$ >= "JANET" IF a>= 14 | True False False |
Boolean operators AND, OR and NOT
AND & OR
The AND & OR operators always return a Boolean result and are used in the format:
[Boolean] [Operator] [Boolean]
The following ‘truth’ table summarizes the result of the Boolean operations:
Values Results
| Values | Results | ||
| X | Y | X AND Y | X OR Y |
| True | True | True | True |
| True | False | False | True |
| False | True | False | True |
| False | False | False | False |
NOT
The NOT operator reverses the result of the Boolean expression and is used in the format:
NOT [Boolean]
The following truth table summarizes the NOT operation:
| X | NOT X |
| True | False |
| False | True |
Examples of Boolean ‘logic’
Consider the following algorithm, which is used to monitor a printer and display its output via an
LCD display in the front panel:
IF NOT (PaperTrayEmpty) AND (FilesWaiting > 0) THEN
OUTPUT “PRINTING…”
ELSE
OUTPUT “PLEASE ADD PAPER"
END IF
Validation
Validation checks ensure that data entered into the computer is sensible. Data is checked in accordance with a set of rules. The computer's software can validate data while it is being entered into the computer. The main purpose of data validation is to spot an error. This can be done quickly and easily as the process is automated.
Range check. A mathematics exam is out of 100. A simple validation rule that the computer can apply to any data that is input is that the mark must be between 0 and 100 inclusive. Consequently, a mark of 101 would be rejected by this check as being outside the acceptable range. Code can be added to check that a particular control has a value between an allowed maximum and minimum:
If Age < 11 OR Age > 70 Then
Print (“The age that you have entered is not within the permitted range”)
End
Character check. A person’s name will consist of letters of the alphabet and sometimes a hyphen or apostrophe. This rule can be applied to input of a person’s name so that dav2d will immediately be rejected as unacceptable.
Format check. A particular application is set up to accept a national insurance number. Each person has a unique national insurance number, but they all have the same format of characters, 2 letters followed by 6 digits followed by a single letter. If the computer knows this rule then it knows what the format of a NI number is and would reject ABC12345Z because it is in the wrong format, it breaks the rule.
Length check. A NI number has 9 characters, if more or fewer than 9 characters are keyed in then the data cannot be accurate. Code can be added to check that a particular control has a value between an allowed maximum and minimum: 383
If Len(Password) > 12 Then
Print ("The password that you have entered is too long")
End
Existence check. A bar code is read at a supermarket check-out till. The code is sent to the main computer which will search for that code on the stock file. As the stock file contains details of all items held in stock, if it is not there then the item cannot exist, which it obviously does, therefore the code must have been wrongly read.
Presence check
Code can be added to check that a particular control has not been left empty or un-checked:
If Username = “” Then
Print (“You have not entered a Username”)
End
Writing flowcharts to solve problems
The following five problems are also covered in section 3.2 where the algorithms are constructed using pseudocode. Candidates may choose to answer questions using either flowcharts or pseudocode but a working knowledge of both techniques is well advised.
2.1 Example 1
A town contains 5000 houses. Each house owner must pay tax based on the value of the house. Houses over $200 000 pay 2% of their value in tax, houses over $100 000 pay 1.5% of their value in tax and houses over $50 000 pay 1% of their value in tax. All others pay no tax. Write an algorithm to solve this problem in the form of a flowchart.
2.1 Example 2
The following formula is used to calculate n: n = (x * x)/(1 – x). The value x = 0 is used to stop the algorithm. The calculation is repeated using values of x until the value x = 0 is input. There is also a need to check for error conditions. The values of n and x should be output. Write an algorithm to show this repeated calculation in the form of a flowchart.
Answers to the Examples:
Dry running of flowcharts
Dry running of flowcharts is basically a technique to:
- Determine the output for a known set of data to check it carries out the task correctly.
- Check the logic of the algorithm.
- Determine the function of the algorithm.
- When dry running a flowchart it is advisable to draw up a trace table showing how variables change their values at each stage in the algorithm.
The advantages of doing this are:
- If you make a mistake, it is easier to back track to where the error occurred rather than starting from the beginning again
- There is less chance of an error being made
- Encourages a more logical approach
The following three examples show all stages in the dry running for the given set of input data:
Example 1
This algorithm inputs 3 numbers, each number goes through successive division by 10 until its value is less than 1. An output is produced which contains the number input and a value generated by the flowchart processing.
Data to be used: X = 85, 3190, -40
Example 2
This algorithm inputs 5 values and outputs how many input numbers were negative and how many were positive.
Data to be used: N = 1, -5, 2, -8, -7
Example 3
This algorithm inputs the number of hours of sunshine recorded each day for a week (7 days). The output is the highest value for hours of sunshine and the average (mean) value for the numbers of hours of sunshine per day.
Data to be used: hours = 9.0, 7.8, 1.2, 4.5, 10.0, 6.4, 3.
Answers of the Examples:
Example 2
Example 3
GCSE \ IGCSE O Level Computer Science P2 Problem Solving and Design