CS revision notes

Algorithm

Structured English Flowchart Pseudocode

Uses keywords and identifiers
Subset of English Shapes linked
(variables and constants ) along
language that consists together representing
with mathematical operators
of command a sequence of steps
without following a syntax of a
statements used to of an algorithm
particular programming language
describe an algorithm
to describe an algorithm

Flowchart symbols
Terminators Process Input/output Decision Continuation

Variable
A variable is used to store data that can change during
the running of a program
Can use a variable without knowing its value
Constant
A constant is used to store data that will not be changed
during the running of a program
Value only needs to be changed once if circumstances
change/during the initialisation process
Variable + Constant Names
1. No spaces
2. Letter and numbers only
3. Must start with a letter
Variable
Comment
name
A poor choice – it has no
l
meaning
length Okay but a bit vague

4. No accented letters or commas or apostrophe

side_length Good
sideLength Good
side length Wrong – don’t use spaces

Programming Data Types

Integer: whole number can be used in calculations
Real: fractionated number can be used in calculations
Char: single character and written between single quotes
String: a sequence of characters and written between double quotes
Boolean: logical value where data is of one of two types

Sequence
A series of steps executed one after the other and all of the statements are
executed.
Selection/Condition
A series of steps that are executed when criteria is met.
Sometimes not all the statements are executed.
A) un nested IF......... IF......THEN....ENDIF
B) nested IF........IF....THEN....ELSE....ENDIF ....checks for complex condition
C) CASE...OF......OTHERWISE.....ENDCASE

l
Allows multiple selections were one out of several branches of code is executed
depending on the value of the variable )
Simplifies pseudocode so it is more understandable
Checks for a value from a discrete large number of values
Repetition/Iteration/Loops
A sequence of steps that are executed an n number of times
Loop Structures
FOR ... TO ... NEXT
Count Controlled Loop
A set number of repetitions
You need to specify the number of times the loop needs to be executed
WHILE ... DO ... ENDWHILE
Pre-condition loop
Has criteria check at start / pre-test
This loop may never run
REPEAT ... UNTIL
Post-Condition loop
Has criteria check at end / post-test
This loop will always run at least once
A repetition, where the number of repeats is not known

Type of test data

Test Data: used to determine whether a solution is working or not so to make
sure algorithm follows required logic.
Normal Data
Data is within the range of acceptability
Abnormal/Erroneous Data
Data outside the range of acceptability
Extreme Data
Data that is on the limit of acceptability
Boundary Data
Used to establish where the largest and smallest values occur
At each boundary two values are required, one value is accepted and the other
value is rejected
Totaling Statement
Increases value of a variable by the value input so used to sum a list of numbers

Counting Statement
Increments the value of a counter gradually to find number of items in a list

How to make testing more manageable?

Reduce number of loop iterations to a manageable amount or simulate
input using a random function

How to make loop iterate and unknown number of times ?

Ask person to input number of iterations
Use a conditional loop such as
REPEAT.......UNTIL
WHILE.....DO....ENDWHILE
Make loop terminating condition the number input by person

Or

Use a rogue value to terminate the process and alert the user
that this value is the value needed to end the iterations.
A rogue value is a value of same data type as data entered but is
outside range of normal expected values
Arrays
A list of items of the same data type stored under a single name
Used to reduce the number of variables used
Any item can be found using an index number to show its place in the list

Name
The name identifying the array
Size
The number of elements in the array
Element
Each item in an array is called an element
Index
The index number identifies the position of an element in the array
Type
All elements in an array have the same data type
Dimension
Number of indexes required to access an elemnt
The organisational structure of the array: 1D is a list; 2D is a table

Advantages of using an arrays rather than variables

1. Can store multiple values under a single identifier
2. Reduces the number variables/ make program code shorter
3. Arrays have an index which identifies each stored element
4. Can use iteration to loop through an array
5. Allows for more efficient programming
6. Programs are easier to debug
Databases

Data type Example Reason of use

#
Boolean True Data is of one of two values

Text / Data expressed as a single word or

Hello short text that can be input quickly
alphanumeric
A number is placed in the field and
Numbers I or 3.5 may require calculations done on it

Needs to be expressed as (currency

Currency $1.25
given) and can be involved in calculations

Percentage 25% Data displayed with % sign

Date /time 12/07/2011 Data should be in format of date/time

Why does the computer need to know if the number is integer or real?
.
Because real numbers take up more space. If a database file has a million
records, this can represent a lot of wasted space.

Why are telephone numbers not stored as numeric data type?

May contain additional character(s) such as dash/space/brackets/plus

symbol
Retains leading zeros
Field would not be used for any calculations
Database Structure
Files: collection of related records that have data displayed as tables
thus allowing user to see the records all at once
Fields: column headings representing single item of data
Records: the information about an item or a person in a row
Primary key: key field that contains a value unique to each record
and has no duplicates
Why are no fields suitable primary keys?
None of them is unique to each record having no duplicates.
Other fields don't have suitable identifiers.

Database Search Criteria

MMM_mf- 2 - - 0 0 8 0 0 was
Validation Verification
Automatically checking that data entered is sensible and for Checking that data entered matches data provided (usually
example falls within specific criteria manually)
Range Check
Checks that only numbers within a specified range are accepted. .
Double Data Entry
Length Check 1. The data will be entered twice
Checks that data contains an exact number of characters
2. Compared by the computer or by a human
Type / Character Check
Checks that the data entered is of a given data type 3. If a discrepancy is found, the data entry operator is asked
Format Check to re-enter the data
Checks that the characters entered conform to a pre-defined pattern
Presence Check
Visual Verification
Checks to ensure that some data has been entered and the value has not been left blank 1. The data will be compared to the source ‘document’
Limit Check
2. Compared by a human
Checks that data entered fits to only one of the two extremes
Boolean Check 3. If a discrepancy is found, the data is re-entered
Checks that data entered is either True or False Checksum
Existence Check
Checks that data entered is found in database
1. Value is calculated from data and appended to it
Check Digit 2. Data is sent with value to receiver
Is the final digit included in a code
3. Receiver recalculates value using same algorithm
It is calculated from all the other digits in the code.
Check digits are used for barcodes, product codes, International Standard Book Numbers 4. If both sent and recalculated value are the same, correct
(ISBN) and Vehicle Identification Numbers (VIN).
data is transmitted
Check Digit can usually detect the following types of error: Why use verification instead of validation?
1. an incorrect digit entered, for example 5327 entered instead of 5307
2. transposition errors where two numbers have changed order, for example 5037 instead of 5307 Data may have no fixed length or value to validate it
3. omitted or extra digits, for example 537 instead of 5307 or 53107 instead of 5307
Data has no fixed criteria to validate
4. phonetic errors, for example 13, thirteen, instead of 30, thirty.
Design and Testing Algorithms
Top down design
Breaking down of a computer system into set of sub systems
Then breakdown of sub systems into smaller sub systems
So that each sub system performs a single task
This reduces development time and debugging time as each sub system can be given to a separate
programmer to complete

Structure diagrams
Shows hierarchy of different components which make up a system and the relationship between them
It shows an overview of the program or subroutine

Library routines
Pre written code to add in you program to carry out a common task
It is a list of instructions that are used often
Which is given a name
Can be called from another program
Makes writing and testing program easier and faster as it was already tested and debugged

Subroutine
Is a self contained piece of code that can be called when needed that consists of a set of
programming instructions to perform a given task making a subsystem
If written in high level language Then example procedure and function
Procedure
A subroutine that does not have to return a value.
An example of a predefined procedure could be a ‘clear the screen’ command that would clear
whatever is currently displayed when running the program
Function
A subroutine that always returns a value
Example: converting integers to strings

Trace Table
Shows the value of variables as you manually test you data
Stages in producing an algorithm

Make sure that the problem is clearly specified.

Break the problem down into sub-problems; if it is complex, you may want to consider writing an
algorithm for each sub-problem. Most problems, even the simplest ones can be divided into:
• set up
• input
• processing
• output of results.
Decide on how any data is to be obtained and stored, what is going to happen to the data and
how any results are going to be displayed.
Decide on how you are going to construct your algorithm, using a flowchart or pseudocode.
Construct your algorithm, making sure that it can be easily read and understood by someone
else. This involves setting it out clearly and using meaningful names for any data stores.
Use several sets of test data (normal, abnormal and boundary) and trace tables to find any
errors.
If any errors are found, repeat the process until you think that your algorithm works
perfectly.

How to make sure solution is effective?

There are many different solutions to the same problem.

In order to consider the effectiveness of a given solution ask the following
questions.
-Does the solution work for all sets of data?
-Does the solution have any unnecessary processes that are never used?
-Are any actions repeated more often than necessary?
-Can the solution be simplified and still work as well?
DON'T FORGET
Table name in data base
Ticking fields to be shown
Make sure you add the sort if one is present
Initialising counter and total before loops
Adding counting statements in conditional loops
FOR loop has no counting statement to terminate process
Counting statement can be added in FOR loop to count items in a list not to
terminate the loop
Follow the flowchart or pseudocode slowly and understand their purpose

READ=INPUT
PRINT=OUTPUT

Explain/Describe/Show
All mean that you should write English statements not pseudocode.
ONLY WRITE PSEUDOCODE WHEN ASKED TO DO SO

Add prompts....usually have marks.

DO NOT ADD PROMPT WHEN ASKED TO NOT ADD ONE

READ THE QUESTION CAREFULLY