Programming Paradigms

The term programming paradigm is used to describe a particular approach or methodology used when programming. Different languages accommodate different paradigms. Some languages allow development using more than one paradigm or a mix of techniques.

Structured Programming

Structured programming is described in the notes for COMP1 Unit 3.

Functional Programming

Functional programming involves writing functions to solve problems, normally mathematical in nature. The program will use lists of values and functions that manipulate these values to provide a solution. Examples of languages include Haskell or F Sharp.

Logic Programming

Logic programming means defining a set of facts and rules. The program uses this knowledge base and its inference engine to determine the solution to a problem. Prolog is an example of such a language and is explained in the Prolog section of the site.

Event-Driven Programming

Event-driven programming means programming the computer's response to events like a mouse click or keyboard entry. The program continues to execute in a system loop reacting to the events that have been programmed.

Object-Oriented Programming

Examples include Java and C++. Object-oriented capability is found to some degree in most recent programming environments. In OOP, programmers develop and use objects in their programming. More in the next section.

Programming Paradigms - Online Lesson

OOP - June 10.pdf

OOP - June 12.pdf

2.1 Presentation A class in OOP (AQA).ppt

Recursion

A procedure is recursive if the procedure contains a call to itself. This is perfectly legitimate in C# and most other high-level languages. A characteristic of recursive procedures is that there must be a stopping condition that can always be reached by the procedure.

The following procedure will calculate the factorial of a number (3! = 3 x 2 x 1 = 6) using a recursive technique.

static int RecursiveFactorial(int num)
{
if (num == 1)
{
return 1;
}
else
{
return num * RecursiveFactorial(num - 1);
}
} 

There is an obvious danger with recursion. In a more complex function, you really need to make sure that there is always stopping condition.

The need to use a stack to store return values means that recursive techniques can be heavy on the memory use. A stack is only so big and a stack overflow would cause the program to crash.

Non-recursive solutions are therefore likely to be more efficient when it comes to processing time and storage. However, there are still reasons why recursion is a desirable feature in a programming language. In some cases, the code is easier to write and understand for the programmer than an iterative solution. This, in some cases, is more important than performance.

Dry-Running Recursive Procedures

You may be asked to dry-run a recursive procedure during the examination. This is slightly more complicated than for an iterative procedure - you need to keep track of the procedure calls.

Example

Dry-run the following procedure using the table of data shown below. The program starts with Process(1).

Procedure Process (P)
Print (P)
If Table[P].Left <> 0
Then Process (Table[P].Left)
EndIf
Print (Table[P].Data)
If Table[P].Right <> 0
Then Process (Table[P].Right)
EndIf
EndProcedure

• Label the program with line numbers - it will help you keep track of where you are within the program.
• Make sure that you understand the way that the elements in the table are referenced.
• Find rough space to create a table to store the information that would go into a stack each time the procedure calls itself. Fill the stack from the bottom - it is LIFO.
• Create a space to write out the printed output each time a Print statement is executed.

Fibonacci Numbers - The Revenge Of Recursion

Fibonacci numbers can be calculated using either recursive or iterative routines.

Fibonacci - Recursive

function fib1(n)
if n = 0: return 0
if n = 1: return 1
return fib1(n - 1) + fib1(n - 2)
End Function

Fibonacci - Iterative

function fib2(n)
if n = 0: return 0
if n = 1: return 1
create an array f[0 �c n]
f[0] = 0, f[1] = 1
for i = 2 �c n:
f[i] = f[i -1] + f[i - 2]
return f[n]
End Function 

As the input value of n increases by 1, the iterative algorithm requires 1 additional step (the for loop runs once more). The same is not true of the recursive algorithm.

If we were to call the recursive procedure with n=5, the following calls would be made to this procedure.

As n increases, the number of function calls quickly gets out of hand. If you look at the following table, you can see that by around n=10, the number of function calls is already very high. By n=20, the number of function calls is over 20000.

n	Recursive Calls
2	2
3	4
4	8
5	14
6	24
7	40
8	66
9	108
10	176

If you implement both algorithms in C# and use the System.Diagnostics tools, you can compare the execution time of both algorithms. The recursive procedure will crash the computer long before the iterative procedure. The main limit on the use of the iterative procedure is the size of number you can store using built-in data types.

Recursion - Online Lesson

2.2 Presentation Recursive Techniques.ppt

Lists and Pointers

Linear Lists

A linear list is an abstract data type. It is a dynamic structure - the number of items in the list can increase and decrease at run-time. Items in a list are stored in order in adjacent locations in memory.

The following example illustrates how a linear list can be programmed using an array. This is written in Javascript which can be viewed along with the source code of this page. The algorithms from below have been used with a few tweaks. Validation is minimal although fussy in some places.

Linear List

Item	Surname	Forename	%/th>
1	Bloggs	Joe	84
2	Budd	Rose	43
3	Day	Violet	95
4	Russell	Jack	63
5	Thumb	Tom	63

Size: 5

Max Size: 20

Algorithms For A Linear List

Each item in the example list has 3 properties, the first one being used for sorting. You need to use a user-defined type to represent each item in the list. In C#, we would do this as follows,

public struct TStudent {

public string surname;

public string forename;

public int mark;

}

A one-dimensional array is used to store the records.

TStudent[] students = new TStudent[20];

The remaining algorithms are in pseudocode.

Insertion

Get Item

item[0] = new Item

ptr = size

if size = maxsize then

prompt user that list is full

else

While item[ptr].surname>item[0].surname

item[ptr+1] = item[ptr]

ptr = ptr - 1

End While

size = size + 1

item[ptr+1] = item[0]

End If 

Finding The Location Of An Item

item[0].surname = surname to be found

ptr = size

while item[ptr].surname> surname to be found

ptr = ptr -1

End While

If ptr = 0 Then

Return False

Else

Return ptr

Deletion

Call find item function to see if item is found

If item not found Then

Write Error Message

Else

ptr = location of item

While ptr < size

item[ptr] = item[ptr +1]

ptr = ptr + 1

End While

size = size -1

End If

Linked Lists

A linked list is a dynamic data structure to hold data in sequence.

• Items are not necessarily stored in contiguous (next to each other) data locations.
• Items in a linked list are called nodes. Nodes contain a data field and a pointer to the address of the next item.
• The data field holds the actual value of the list item, the pointer field contains the address of the next item.
• The pointer field of the last item indicates this using a special value (eg 0 or -1).
• In addition, a pointer variable must be stored showing the address of the first item in the list.
• It is also common to store the location of the next free address.

The term, Dynamic Data Structure refers to the fact the memory needed to store a linked list will vary at runtime.

Linked List

Address	Name	Pointer
1	Shanks	0
2	Armitage	4
3	Pinky	1
4	Perky	3
5		6
6		0

Start:2

Next Free:5

Linked List Algorithms

Implementing a linked list with an array, requires an array of records. In the example, there are 2 fields in the record, the name and the pointer. You need global variables to store the following,

• Maximum List Size
• Start Address
• Next Free Address

To Insert An Item

This algorithm is long because there are 3 scenarios to consider. The item might be placed as the first item in an empty list, it might be the first item in the list or it might be placed at some other location in the list.

Get New Item Name

If nextfree = 0 then

Prompt user list is full

Exit Sub

End If

Set item[nextfree].name to new item name

If start = 0 (list currently empty) then

item[nextfree].pointer = 0

nextfree = 2

start = 1

Exit Sub

End If

Ptr = start

If newItem
tempPtr = item[nextfree].pointer

item[nextfree].pointer = start

start = nextfree

nextfree = tempPtr

Else (place within list)

placed = false

While Placed Is False And item[Ptr].pointer <> 0

If newItem>=item[item[Ptr].pointer].name Then

Ptr = item[Ptr].pointer

Else

placed = true

End If

End While

tempPtr = nextfree

nextfree = item[nextfree].pointer

item[tempPtr].pointer = item[Ptr].pointer

item[Ptr].pointer = tempPtr

End If

To Find The Previous Item In The List

In order to process deletions from the list, it will be necessary to work out which item points to the item to be deleted.

tempP= start

Do

previous = tempP

tempP = item[tempP].pointer

Loop While tempP <> Address Of Item To Delete

Return previous

To Delete An Item

itm = Address Of Item To Delete

If Empty List Then

Prompt User

Exit Sub

End If

If item[itm] = start (first in list) Then

tempPtr = item[itm].pointer

item[itm].pointer = nextfree

start = tempPtr

nextfree = itm

Exit Sub

End If

If item[itm].pointer = 0 (last in list) Then

item[itm].pointer = nextfree

nextfree = itm

item[findPrevious(itm)].pointer = 0

Exit Sub

End If

(Deal With Other Scenarios)

item[findPrevious(itm)].pointer = item[itm].pointer

item[itm].pointer = nextfree

nextfree = itm

To Output The List In Order

If start = 0 (empty list) Then

Prompt User

Exit Sub

End If

startPrint = start

Do

output item[startPrint].name

startPrint = item[startPrint].pointer

Loop While startPrint <> 0

Key Terms

A Static Data Structure is a data structure whose size is declared when the program is run. An array is an example of this. If too many locations are set aside for storage, memory is wasted. If too few are set aside the program will not work.

In dynamic data structures, you do not have to reserve memory space. The space used for dealing with dynamic data structures is called the heap. The heap is a pool of available memory locations which can be allocated in blocks to the dynamic structure. When no longer needed, the locations are returned to the heap for use by other applications.

Pointer variables point to memory addresses.

Other Things To Consider

The example list above is obviously far smaller than may be used in practice. In order to store data that needs to be sorted in more than one way, you would need to store additional pointers that sustain this order.

When drawing diagrams of linked lists, you must make sure that you indicate the start and next free addresses. It is also vital that the pointer of the last item is 0 or -1 to indicate the end of the list.

Lists - June 10.pdf

Stacks and Queues

Stack

A stack is a Last In First Out (LIFO) data structure. You push new items onto the top of the stack. You pop items from the top of the stack to remove them. A pointer indicates the top of the stack.

Stacks are used in calculations and translation from one computer language to another. They are also used to reverse items in a list or array.

When a recursive procedure is called, a stack of records is used to store the local variables for each procedure call as well as the return address (ie the exact line of the procedure to return to.

Overflow & Underflow

When a stack or queue is full, attempting to add a new element will create an overflow error. When the stack or queue is empty, attempting to remove an element creates an underflow error.

Queues

A queue is a First In First Out (FIFO) data structure. New items are added to the end of the queue. Items are removed from the front of the queue. Pointers indicate the front and rear of the queue.

Linear Queue

Look carefully at the diagram of the queue above. If Job1 were to be removed from the queue and a new Job to be added, we would already have reached the maximum capacity for the queue shown above but still have a space left at the start. In a linear queue, all of the other jobs would have to shuffle one place to the left and then the space would be available at the end of the queue.

Circular Queue

The circular queue operates in a similar way except it avoids the shuffling of items. When items are removed from the queue, all other items stay in the same location. Pointers are used to mark the front and rear of the queue. Try filling the queue and then removing a few items. Now add some more items to the queue and look carefully at the pointers.

Circular Queue Algorithms

To Add To The Queue

If qlength>qmax Then
Prompt User Queue Full
Else
If qrear = 6 Then
qrear = 1
Else
qrear = qrear + 1
End If
qitems[qrear] = item to add
qlength = qlength + 1
End If

To Remove From The Queue

If qlength = 0 Then
Prompt user Queue Empty
Else
Take item from qitems[qfront]
qlength = qlength - 1
If qfront = 6 Then
qfront =1
Else
qfront = qfront + 1
End If
End If

Other Ways To Implement Queues

You can use a linked list, along with global variables to store start and end positions of the queue.

A priority queue stores the priority of each element. When we implement priority queues, it is the priority of the element, not when it is added that determines its position in the queue. A linked list can be used to represent this. The algorithms need to be tweaked to look at the priority of the item when adding or removing.

Data Structures - Online Lesson

Graphs and Trees

Graphs

A graph consists of a set of vertices and edges. Each edge may have a label, known as its weight or cost.

The London Underground map is probably the most familiar graph diagram that you have seen. If you were to compare the map with the physical locations of the stations, you will see that some liberties have been taken with the geography of the city. The diagram restricts itself to the information that is useful to its users - the connections. On the diagram you can see which stations are connected and work out a route. The distances don't matter so scale is not important in this diagram.

If we consider the transport links between towns in the local area, we might come up with a graph something like the following,

• A - Bishop's Stortford
• B - Braintree
• C - Colchester
• D - Harlow
• E - Chelmsford

This type of graph is known as an undirected graph. There is no directional information. Notice that there is also no sense of scale and the towns are not in their exact position. This graph merely shows the connections between the vertices. For example, following major roads only, you pass through Braintree on your way to Colchester from Bishop's Stortford.

In this graph, A & B are neighbours because there is a connection between them. A & D are also neighbours. Vertex A is said to have a degree of 2 - it has two neighbours.

The WWW, LANs & WANs, traffic flow, transport links, circuits, chemical compounds, social networks are all examples of real-world situations that lend themselves to being modelled with a graph.

Weighted Graphs

If we were to label each of the edges with the distances between the towns, we would have what is called a labelled or weighted graph. It isn't hard to see why this information is useful.

In the weighted graph, the edges are labelled with weights. If the above graph represented the distances between locations, you can quickly calculate the relative cost of different routes between the locations. The weights can be negative numbers - remember the graph is an abstract representation of a real-world scenario.

There is interest in determining the shortest path between vertices - you should look for Dijkstra's algorithm online and be thankful you haven't been asked to pronounce the name out loud.

Directed Graphs

A directed graph includes arrows on each edge. The arrows show the path that can be followed from each vertex to the next. Be careful of getting bogged down in the map model though. The arrows can be used to represent other facts.

In the diagram below, the vertices represent teams playing a round-robin tournament. Each team plays each of the others once.

The arrow on each edge shows which of the two connected teams won the match. In this diagram, team A beat team C but lost to team B. Team B won the tournament since they were the only undefeated team.

Adjacency Matrix - Undirected Graph

An adjacency matrix is a way of representing the connections in a graph.

The adjacency matrix for the above graph is as follows,

A	B	C	D	E
A	0	1	1	0	1
B	1	0	0	1	0
C	1	0	0	1	1
D	0	1	1	0	0
E	1	0	1	0	0

In the table, a 1 is used to indicate that the vertices are connected, a 0 is used where they are not. For a directed graph, the adjacency matrix is symmetrical. For example, there is a 1 for the connection from A to E and for the connection from E to A.

Adjacency Matrix - Directed Graph

Our round-robin tournament graph will not have a symmetrical adjacency matrix. For example, A is adjacent to C but not to B.

A	B	C	D
A	0	0	1	0
B	1	0	1	1
C	0	0	0	0
D	1	0	1	0

Reading the table row-by-row, we clearly see that team B are the winners of this tournament and that team C didn't win a match.

Adjacency Matrix - Weighted Graph

In a weighted graph, the weights need to be accounted for in the adjacency matrix. Since 0 might be a valid weight, we cannot use that to represent the absence of an edge. Infinity tends to be used in such cases.

A	B	C	D	E
A	���	5	5	���	5
B	5	���	���	3	���
C	5	���	���	4	6
D	���	3	4	���	���
E	5	���	6	���	���

Adjacency List - Undirected Graph

An adjacency list details the neighbours of each vertex.

Vertex	Adjacent Vertices
A	B, C, E
B	A, D
C	A, D, E
D	B, C
E	A, C

Adjacency List - Directed Graph

With a directed graph, the adjacency list must take into account the direction of the arrows on each edge.

Vertex	Adjacent Vertices
A	C
B	A, B, D
C
D	A, C

Adjacency List - Weighted Graph

The adjacency list for the weighted graph must include details of the weight of each edge.

Vertex	Adjacent Vertices
A	B,5; C,5; E,5
B	A,5; D,3
C	A,5; D,4; E,6
D	B,3; C,4
E	A,5; C,6

Graph Traversal - Depth-First Search

A path is a sequence of vertices beginning at one vertex, visiting a series of vertices until the destination is reached. A depth-first search of a graph begins with one vertex and follows a path from there until it reaches the last vertex. It then backtracks and follows a different path from the initial vertex. It does this until all vertices are reached.

When we perform this kind of search, we need to keep track of whether or not we have visited a vertex (discovered) and whether or not we have fully explored a vertex. A depth-first traversal of the above graph would run as follows,

Step 1 - Start With Vertex A

Vertex	Discovered	Completely Explored
A	True	False
B	False	False
C	False	False
D	False	False
E	False	False

Stack (Bottom To Top): A

Step 2 - Visit A's First Neighbour

Vertex	Discovered	Completely Explored
A	True	False
B	True	False
C	False	False
D	False	False
E	False	False

Stack (Bottom To Top): A, B

Step 3 - Visit B's First Neighbour

Vertex	Discovered	Completely Explored
A	True	False
B	True	False
C	False	False
D	True	True
E	False	False

Stack (Bottom To Top): A, B, D

Step 4 - Backtrack And Visit B's Second Neighbour

Vertex	Discovered	Completely Explored
A	True	False
B	True	True
C	False	False
D	True	True
E	True	True

Stack (Bottom To Top): A, B, E

Step 5 - Backtrack And Visit A's Second Neighbour

Vertex	Discovered	Completely Explored
A	True	True
B	True	True
C	True	True
D	True	True
E	True	True

Stack (Bottom To Top): A, C

When the discovered and completely explored columns are true for each vertex, the entire graph has been traversed.

Trees

What Is A Tree?

A tree is a dynamic data structure in which data is stored in a hierarchical manner.

In the above diagram, each part of the tree that contains information (the boxes) is called a node. The first node (in this diagram - 'Computing') is called the root node. The lines which connect each of the boxes are called branches. Some nodes have child nodes - they connect to nodes on the level below. Nodes that don't have children are called leaf nodes.

A tree is very similar to a graph. In fact, we could say that the tree shown above is a connected, undirected graph. This particular tree is a rooted tree. All of the edges are directed away from the root node.

Binary Trees

A binary tree is a special type of tree where each node is allowed a maximum of 2 children. You construct a binary tree by placing the first data item as the root node. For each subsequent item, branch to the left if it is less than the root node, branch to the right if it is greater. Apply this branching rule at each node that is met unitl the item can be placed.

Do this with the following names,

Partridge, Duckworth, Smith, Arkwright, Wren, Thumbface, McJack.

You should end up with a tree diagram that looks like this,

Starting from the root node, if you were searching for Thumbface, which items would you need to access?

Make another tree with the following capital cities,

London, Paris, Washington, Canberra, Lima, Madrid, Lisbon.

Which data items would be accessed if you were searching for Madrid?

Traversing The Tree

There are a variety of methods used for traversing the tree to produce sorted output. The following traversal methods produce output in different orders.

• Pre-Order Traversal
• In-Order Traversal
• Post-Order Traversal

A diagrammatic representation of how to construct a binary search tree, as well as the different traversal methods, can be found by clicking or downloading the following PowerPoint slideshow.

Binary Tree Algorithms

The simulation on this page uses an array of records to manage the items in the binary tree. The structure definition is shown in C, the remaining algorithms are pseudocode.

Record Definition & Global Variables

public struct TreeItem {

public int left;

public int right;

public string name;

}

int maxsize = 15;

TreeItem[] treeitems = new TreeItem[maxsize];

Inserting Items In The Tree

Two procedures are used. The first checks that the tree is full and, if not then looks to see if this is the first item (root node) of the tree. If this is the root node it creates it, no fuss involved since the root node initially points to 0. If the node is not the root, the second procedure is called. This procedure is recursive, walking through the tree following the left/right rules changing the appropriate pointer of the parent node.

Procedure InsertItem(itm)

IF treeitems.length = maxsize THEN Exit Procedure

IF treeitems.length = 0 THEN

treeitems[0] = new TreeItem(itm)

ELSE

treeitems[treeitems.length] = new TreeItem(itm)

ChangePointers(treeitems.length - 1, 0)

END IF

End ProcedureProcedure ChangePointers(a,b)

IF treeitems[a].name < treeitems[b].name THEN

IF treeitems[b].left = 0 THEN

treeitems[b].left = a

ELSE

ChangePointers(a, treeitems[b].left)

END IF

ELSE

IF treeitems[b].right = 0 THEN

treeitems[b].right = a

ELSE

ChangePointers(a, treeitems[b].right)

END IF

END IF

End Procedure

In-Order Traversal

The procedure for in-order traversal is recursive. The first call to this procedure would be InOrderPrint(0).

Procedure InOrderPrint(a)

IF treeitems[a].left <> 0 THEN

InOrderPrint(treeitems[a].left)

END IF

Print treeitems[a].name

IF treeitems[a].right <> 0 THEN

InOrderPrint(treeitems[a].right)

END IF

End Procedure

Pre-Order Traversal

Procedure PreOrderPrint(a)

Print treeitems[a].name

IF treeitems[a].left <> 0 THEN

PreOrderPrint(treeitems[a].left)

END IF

IF treeitems[a].right <> 0 THEN

PreOrderPrint(treeitems[a].right)

END IF

End Procedure

Post-Order Traversal

Procedure PostOrderPrint(a)

IF treeitems[a].left <> 0 THEN

PostOrderPrint(treeitems[a].left)

END IF

IF treeitems[a].right <> 0 THEN

PostOrderPrint(treeitems[a].right)

END IF

Print treeitems[a].name

End Procedure

Graphs - Online Lesson
Trees - Online Lesson

Binary Tree Simulation.ppt
Graphs - June 10.pdf
Programming Concepts - June 12.pdf

Searching and Sorting

Searching

Linear Search

The linear search is the simplest method to search for items stored in an unsorted list. The technique involves comparing the search item with each item in the list until either a match is found or the end of the list is reached.

The algorithm in pseudocode for a linear search is as follows,

CurrentItem �� 1
Found �� false
Repeat
If List[CurrentItem] = ItemSought
Then Found �� true
CurrentItem �� CurrentItem + 1
Until Found = True Or CurrentItem > Max 

Linear Search In C#

Binary Search

The linear search is not particularly efficient when searching a sorted array. The binary search works by comparing the item you want to find with the item stored at the midpoint of the list. If the item should come before the item at the midpoint, the second half of the list need not be searched. The midpoint of the the first part of the list would then be compared with the search item and a similar process followed. By comparing the item with ever-shrinking lists, the binary search requires very few comparisons to either find an item or establish that it is not in the list.

Iterative Binary Search

Procedure BinarySearch(List, First, Last, ItemToFind)
itemfound �� false
searchfailed �� false
Repeat
midpoint �� (First + Last) DIV 2
IF List[midpoint] = ItemToFind
Then itemfound �� true
Else
IF First >= Last
Then searchfailed �� true
Else
IF List[midpoint] > ItemToFind
Then Last �� midpoint -1
Else First �� midpoint + 1
End If
End If
End If
Until itemfound OR searchfailed
End Procedure

This procedure can also be written recursively. A recursive version is used in the C# sample.

Binary Search In C#

Sorting

Insertion Sort

The insertion sort is the closest sort algorithm to the way that we might sort the array if we wrote the numbers on some cards. Imagine that this is the case. You would take the first card and place it on the table. You would then take the second card and place it to the left or right of the first one depending on whether it was greater or less than that item. When the third card is taken, if it goes at the start of the list, you would need to shuffle the other cards to the right to put it in the correct position.

The following algorithm can be used for an insertion sort,

For outerLoop = 1 To arrayLength - 1
temp = item[outerLoop]
innerLoop = outerLoop
While (innerLoop > 0 And item[innerLoop - 1] >= temp)
item[innerLoop] = item[innerLoop - 1]
innerLoop = innerLoop - 1
End While
item[innerLoop] = temp
Next outerLoop

The AQA specification only lists Insertion Sort as an algorithm to learn. Cutting up pieces of paper and writing numbers on them is a good way to help you to understand how this sort works. You can also rewrite the algorithm so that the list is output after each iteration of the outerloop.

Make sure that you are aware of the many different approaches to sorting. Creating a program that compares the execution time (at different volumes) of each algorithm is a useful way to get a sense of how quickly they execute.

Insertion Sort In C#

Standard Algorithms - Online Lesson

Searching And Sorting - June 11.pdf
2.6 Presentation Binary Search (AQA).ppt
2.6 Presentation Insertion Sort (AQA).ppt

Simulation

A simulation is a computer model of a real system. The events that are simulated may be real or imaginary. The aim is to create a model that allows the performance of the system to be explored. A simulation may be used to model traffic flow on an actual road with a view to improving things with additional roads or altering the phasing of traffic lights. A similar approach may be taken to asses the feasibility of a new road system.

Simulations are an abstraction of the real system they aim to simulate. Only the key details are included in the model - unnecessary details are removed.

Example - Simulating The Tuck Shop Queue

Suppose that we wanted to simulate a tuck shop queue over the course of a lunch break. The aim of such a simulation is to explore whether or not the current setup functions as expected (ie queue times are short and throughput is high). In our simulation we have 3 entities - the components of our simulation. The server is one of the entities in our simulation - the customer is another. The queue itself is also one of the entities in our simulation.

The entities have attributes, properties or characteristics that our simulation must take into account. For example, a customer can be waiting in the queue or being served.

Our simulation is of a system that changes discretely over time. By this we mean that changes of state are abrupt - when a customer joins the queue they are waiting, when they get to the front and the server is free, the state of this entity changes to being served. This is an abrupt rather than a gradual change.

A methodological approach to constructing a simulation is required - the following are stages that we might expect to be undertaken in setting up this simulation.

Formulate The Problem

At this stage of the process, we consider the objectives of our simulation. In this case it might be to ascertain the number of customers that can be served over a given period of time.

We also need to consider the way we are going to measure our findings in the simulation. We should be able to state what we intend to measure (average wait time, average number of customers, maximum queue length etc.) and to what degree of accuracy.

Observation

Since this is a simulation of an existing system, we would need to observe and inspect the current system to be able to abstract the key details for our simulation.

State transition diagrams are a useful tool in modelling this system. We would look at the entire life cycle of the system - in this case, we would look at the journey each new customer makes through the system until they have been served.

There would be a need to consider the real-life system as an information system. What data enter the system, what are the outputs? What are the variables? What are the relationships between different parts of the system? What are the key processes.

In our example, we should look at the probability of a customer arriving. Is it a fairly consistent rate throughout the period of opening or is it more haphazard? We would need to measure this by collecting data. We need to think about the time it takes for a person to be served. This might vary over the course of lunch time with larger items bought earlier or it may be fairly constant. It may relate to the number of items being purchased which may in turn be connected to the amount of money being spent. We would be interested in the extent to which this varies from customer to customer.

Formulate The Model

In this stage of the process, we aim to describe the model as completely as possible. Some aspects of the model are best explained using diagrams. The life cycles of the entities need to be mapped out. We also need to state any assumptions that we are making (eg assume that it takes 1 minute to serve each customer.

In formulating the model, we consider how we are going to represent the passing of time. In a time-driven simulation we increment a master clock in time units appropriate to the model. After each tick, the program must work out which events (if any) should occur.

An activity-driven simulation is another method that is used. The program checks against a schedule for the next event to occur and advances the clock by an appropriate amount of time for the activity that has taken place. To get a sense of how this approach differs, consider the arrival of a person in a queue. If our program ticks away a second at a time, it might model the arrival of a customer by generating a random number on each tick and, if the number generated falls within a specific range, may add another customer to the queue. In an activity-driven simulation, when the next event to occur is the arrival of a customer, the program advances the master clock by the amount of time that this event takes to occur - again this could be a random number.

Validate The Model

Before spending time and money on development, the model needs to be validated. This means checking its logic as well as hand-tracing. You would need to look at the effect of extreme inputs on the system and make sure that you are not missing any theoretical limits. For example, there is a physical limit to the size of a queue.

Write The Program

With a valid model, the simulation needs to be programmed. There are languages developed for this purpose but high-level languages tend to be fairly well suited.

The fact that we base our model on entities with their own attributes makes simulation particularly suited to object oriented techniques.

Validate The Program

The program, once written, needs to be validated. This can be tricky if the system being modelled doesn't really exist. If it does, we can compare our model with historical data and verify that the data produced by our model matches what we observe in the real world. If there is no system, we can only check that the logic and assumptions behind the model are valid.

Design Experiment

Once the program is designed and validated, the next step is to design experiments to use the model. The simulation needs to run long enough to make a meaningful test. Our tuck shop queue would need to run repeatedly to ensure that possible problems are not missed.

Randomness

Remember that we use the term pseudo-random to describe the random numbers that a computer generates. It is vital to make sure that the seed of the random number generator is not kept the same for each run of the simulation. In such cases, the results may a little too predictable.

When you generate a random double in C#, the value is between 0.0 and 1.0 (but does not include 1). Probabilities are measured in the same range. Conveniently then, when we want to make an event happen with a certain probability, say 0.5, we need only check if our random double is less than the probability value to determine whether or not the event occurred.

Simulation - June 11.pdf
2.7 Presentation Simulation (AQA).ppt