Algorithm Design and Problem Solving

Abstraction
Abstraction involves filtering out information that is not necessary to solve a
problem.

 Makes it easier to implement

 System is tailored to meet user’s requirements

Decomposition
Decomposition means breaking problems down into sub-problems in order to
make the problem easier to solve. This usually leads to the creation of smaller
modules.

 Easier to understand
 Easier to maintain smaller modules
 Smaller problems can be divided amongst the team and given to
respective experts

Algorithm
An algorithm is a sequence of steps used to solve a problem

Sub Routine/Modules
Dividing the program into smaller parts, each designed for a specific task

 Modules can be called upon many times so it reduces copy pasting the
same lines over and over
 They can be tested and debugged individually
 If a change is made to the routine, it only needs to be changed in one
place

Identifier
A name given to a specific variable in order to call it. Each names needs to
meet these rules;
 Unique
 No spaces or illegal characters
 Must begin with an alphabetical character
  Must not be a reserved word like IF or PRINT
INPUT Value
OUTPUT Value
DECLARE Variable : INTEGER
Variable ← 1 // Assignment
Variable ← Variable + 84 // Process

Data Types and Structures

There are 7 data types;
 Integer – Stores whole numbers including negatives
 Real – Stores numbers with decimal values
 Char – Stores a single character like ‘A’ or ‘1’ or ‘a’
 String – Stores a combination of alphanumeric characters or symbols
 Boolean – Stores true or false
 Date – Stores a date
 Array – A list of usually of the same type stored together under a single
identifier

Record Type
When variables of different types are logically related, we can use a user
defined type to store this information.

 Easier to understand the code

 Closer association between variables
TYPE <NAME>
DECLARE <FIELD NAME> : <DATA TYPE>
.
.
ENDTYPE

TYPE PERSON
DECLARE Name : STRING
DECLARE Age : INTEGER
ENDTYPE
DECLARE firstPerson : PERSON

firstPerson.Name ← “John”

OUTPUT FIRST_PERSON.Name
Array
A list of usually of the same type stored together under a single identifier
Index
A pointer to the location in the array
Upper Bound
The technical term for the maximum value that may be stored by the array
Lower Bound
The technical term for the lowest value that may be stored by the array
DECLARE List1 : ARRAY[1:20] OF INTEGER //1D ARRAY
List1[1] ← 2
DECLARE List2 : ARRAY[1:5,1:5] OF INTEGER //2D ARRAY
List2[2,3] ← 0
To output an array we can use a for loop until the length of the array.
Linear Search
Max = 10
Value = 99
Found = True
I = 0
REPEAT
I = I + 1
IF Array[I] = Value THEN
Found = True
ENDIF
UNTIL Found = True OR Index >= Max
IF Found
OUTPUT I
ELSE
OUTPUT “Not found”
ENDIF
Bubble Sort
Array[1:10]
Max = 9
REPEAT
NoSwaps = True
FOR J = 1 TO Max
IF Array[J] > Array[J+1] THEN
Temp = Array[J]
Array[J] = Array[J+1]
Array[J+1] = Temp
NoSwaps = False
 ENDIF
NEXT J
Max = Max – 1
UNTIL NoSwaps

Files
Text files allow data to be stored that will not be lost when the program
restarts.
OPENFILE <NAME> FOR WRITE // WRITE/READ/APPEND
WRITEFILE <NAME>, <VALUE> // Writes one line
READFILE <NAME>, <VARIABLE> // Reads one line
CLOSEFILE <NAME> // Necessary to do after done
Write mode overrides the previously written text but append adds on to it.
OPENFILE “Text.txt” FOR READ
WHILE NOT EOF(“Text.txt”) DO
READFILE “Text.txt”, Value
OUTPUT Value
ENDWHILE
CLOSEFILE “Text.txt”

Abstract Data Types (ADT)

A collection of data with associated operations like a stack, queue and a linked
list.
Queue
Each element in a queue stores one data item. There is a pointer for the front
and the back of the queue. Works on the principles of “First in first out”
When adding an element to queue, you need to make sure there is empty slots
available. Likewise, when removing an element, you need to make sure there is
a valid element to remove.
A queue can be implemented by creating a one-dimensional array of data type
“X”. The size of the array is equal to the size of the queue. An integer variable
for the front and end pointer of the queue. They are initialized to 1. Initialize
an integer variable to store the number of elements in the queue and size.
When the front and end pointer are equal, then there is only one element in
the queue.
Linked List
Each element stores a node that contains a data item and a pointer to the next
element in the node. There is a pointer to the start of the list as well. Null is
used to represent the end of the list. When adding or removing elements data
is not moved only the pointers are adjusted. Nodes are traversed in a specific
order.

 Easier to add and remove data and maintain the sequence by changing
pointers
 Pointers are changed only not the data itself
 Need to store value of pointer and the value of the data
 More complex
Stack
Each element stores one data item. There is a pointer to the current place of
the stack. A stack stores elements on the principles of “First in last out”.
A stack can be implemented by creating a one-dimensional array of data type
“X”. The size of the array is equal to the size of the stack. A variable for the
pointer is declared and initialized to 1. The pointer variable is used as the index
for the array. Each item in the stack is one item in the array. Push and pull
functions are created. These need to check for under and overflow.

Programming
Loops / Iteration
There are three types of loops, post conditioned, pre-conditioned and
controlled.
I = 1
FOR I TO 10 // Controlled
// Do Stuff
NEXT I
WHILE I <= 10 // Pre-Conditioned
// Do Stuff
I = I + 1
ENDWHILE
REPEAT // Post-Conditioned
// Do Stuff
 I = I + 1
UNTIL I > 10
A controlled loop is used when we know the number of iterations. A pre-
conditioned loop is used when we know the condition to keep running the
loop. A post conditioned loop is used when we know the stopping condition.

Conditions / Selection
There are two structures used, if-then-else and case-of-endcase. Case is used
when there are only a few specific values that we need to check for. If can be
used for Booleans and range.
IF CONDITION THEN
// Do Stuff
ELSE IF CONDITION THEN
IF CONDITION THEN
// Do Stuff
ENDIF
ELSE
// Do Stuff
ENDIF

CASE OF VARIABLE
1: // Do Stuff
2: // Do Stuff
3 TO 5: // Do Stuff
OTHERWISE // Do Stuff
ENDCASE

Flow Chart
Symbol Use

Start/End

Arrow

Input/Output

Process
 Decision

Function Calls

Procedures
A procedure is a means of giving a group of statements a name so that it can
be called possibly multiple times during the programs execution and to
improve readability.
A procedure has a header, body, and end. The header contains the procedure
interface, the body contains all the statements executed by the procedure.
PROCEDURE NAME(VARIABLE: DATATYPE)
// Do Stuff
ENDPROCEDURE
PROCEDURE SAY_HI()
OUTPUT “Hi”
ENDPROCEDURE

PROCEDURE ADD(Num1: INTEGER, Num2: INTEGER)

OUTPUT Num1 + Num2
ENDPROCEDURE
PROCEDURE SET_ADD(BYVAL Num1: INTEGER,BYREF Value:
INTEGER)
Value = Num1 + Value
ENDPROCEDURE
Values between the brackets are called parameters. Parameters are passed to
the procedure with the name and data type. A parameter is the placeholder
value but the argument is the actual value passed to the procedure/function.
There are two ways to pass variables to a procedure BYREF and BYVAL. BYREF
allows the procedure to edit values of a variable so that they can be used after
the procedure runs but BYVAL only takes the values without modifying the
original variable’s values.
A procedure can also have no parameters.
Functions
A function works like a procedure except that it returns a value back.
FUNCTION NAME(VARIABLE: DATATYPE) RETURNS DATATYPE
// Do Stuff
ENDFUNCTION
FUNCTION GET_VALUE() RETURNS
RETURN VALUE
ENDFUNCTION
FUNCTION ADD(Num1: INTEGER, Num2: INTEGER) RETURNS
INTEGER
RETURN Num1 + Num2
ENDFUNCTION
VALUE = CALL ADD(1,2)
Header
A function/procedure’s header refers to the first line PROCEDURE START()
Procedure/Function Interface
Provides the mechanism to pass data in order to the function/procedure along
with the datatype. It defines the number of arguments a function has.
Build in functions exist like CHAR() and MID()

Software Development
Development Life Cycle
There are benefits to having a development life cycle

 Easier to plan out and manage

 A clear idea of what is to be expected at the end of the cycle
A software development cycle has 5 main stages;
 Analysis
 Design
 Implementation/Coding
 Testing
 Maintenance
Analysis
During the analysis stage, the current system is investigated to figure out what
issues need to be addressed by the software. A “requirement specification” is
created. Then multiple solutions are proposed to the client and they can
choose which one they would like to pursue.
Design
Once a solution has been chosen it is a good idea to plan out the steps needed
to carry it out such as flow charts and pseudocode. A programming language is
picked as well as designing the user interface.
Coding
After an algorithm has been designed in pseudocode and flowcharts it is then
converted into an actual program by using a high-level programming language.
Testing
During this phase the software goes through rigorous trials to iron out bugs
and improve upon the current design.
Maintenance
Once the program has been fully released to the public, it is required to keep it
up to date with new industry standards and patch any new bugs found.

There are three main types of development cycles and each one serves its own
uses with benefits and drawbacks.
 Waterfall
 Iterative
  Rapid Application Development (RAD)
Waterfall

The downward arrows indicate that the work from one stage is passed to the
next stage. The upward arrows indicate that more work needs to be done on the
previous stage to complete the current one.

 Simple to understand
 Works well for smaller projects
 Easy to manage
 No software produced until the nearing end of the cycle
 Not good for large complex projects
 Cannot accommodate changes in requirements
Iterative
The iterative model does not start with a full list of requirements, it starts by
implementing a small subset of the requirements and further reviews and
testing are carried out to complete it.

 A working model is produced at each stage

 Results are obtained early in the cycle and periodically
 Easier to manage as issues and possible risks are identified at each
increment
 Only works for large scale projects, not suited for small ones as they
cannot be broken down into smaller software
 Design issues can arise as not all requirements are known at the start
  Resource intensive
Rapid Application Development
RAD relies on minimal planning and involves developing modules in parallel to
each other.

 Changes to the requirements can be accommodated easily

 Reduces development time
 A working model is produced at an early stage
 Too easy for the client to change their mind
 Requires highly skilled developers
 Only suitable for modularized and component-based programs

Structure Chart
These are used during the design stage of the program. A structure chart is a
visual representation of the logic behind a given solution.
It can represent the hierarchy of the modules as well as the parameters being
passed and the iterations that occur.

A hollow circle represents a variable being passed and a dark circle represents
a Boolean being passed.
If the arrow goes both way it indicates that the value is being returned to the
program.
The diamond is used for branching out the program due to a condition.
Each box does not need to contain the pseudocode behind the task, it can just
say “Generate random number” and the developer would need to work out
the logic behind that.
An arrow is used to indicate a loop.

State Transition Diagram

A state transition diagram is used to describe the behavior of a finite state
machine.
A finite state machine has limited number of states that it can be in.
A state machine is like a set of rules or instructions that govern how a system
behaves based on its current condition and the inputs it receives
 For understanding purposes only ^

The start state is indicated by an arrow.

The final state, if present, is indicated by a double circle.
When an input causes an output, a vertical bar is drawn.
Errors
No program is without fault; therefore, errors need to be found and
addressed. This is usually done when an end user submits a report or during
the testing phase. There are 3 main types of errors;
 Logic Error – An error in the logic that makes the program behave
abnormally
 Syntax Error – An error in which a statement does not follow the rules of
the program language
 Runtime Error – An error which usually causes the program to crash
while being executed

Program Fault
When a program behaves in a way it is not meant to under certain
circumstances
Can be reduced by using IDE features, a robust library and following common
good practice.
There are 8 main testing methods when it comes to testing the program to find
errors.
 Stub
 Whitebox
 Blackbox
 Dry run / Walkthrough
 Integration
 Alpha
 Beta
 Acceptance
Stub Testing
A placeholder module is implemented that outputs a message to show that it
has been called. It is used when the modules have not all been developed.
Whitebox Testing
Suitable test data is devised and input into the program. The data is then
followed line by line to make sure it ends at the correct output
It is used to test every path through the algorithm.
Blackbox Testing
A suitable list of test data is created along with expected results. The data is
then input into the program and the results are recorded. If the results are not
expected then further testing is carried out.
It is called Blackbox as the tester does not know how things happen.
Walkthrough Testing / Dry run
The program is checked line by line using a trace table where the values of the
variables are checked at each instance. When you receive an unexpected value
there is usually an error in the program. Logic errors can be identified.

Alpha Testing
The program is tested in house by people like developers and other people
involved in its development
Beta Testing
The program is tested by a limited number of chosen individuals. They give
feedback on the program and report errors.
Acceptance Testing
Before the program is handed over to the client it is tested by them to ensure
it meets the requirements
Integration Testing
As the program is generally written as smaller modules it is important to test
how well they function when together.

Test Data
There are 3 types of data input to a program to test it;
 Normal – Data that is accepted by the program
 Abnormal – Data that is rejected by the program
 Boundary/Extreme – Data that is either the smallest or largest accepted
value

Maintenance
 Corrective
 Perfective
 Adaptive
Corrective
Fixing identified errors
Adaptive
Amending a program to meet new requirements or industry standards
Usually involves changing the algorithm or the data structure.
Perfective
Modifying a program so that it performs better