Pseudo-Codes and Flow Charts

Pseudo-Code

STEP 1: Input X = 1 and Y = 2

STEP 2: Print X

STEP 3: Let X = X + Y

STEP 4: Let Y = Y + 1

STEP 5: If Y < 11, then return to Step 2

STEP 6: Stop

X	Y	PRINT
1	2	1
3	3	3
6	4	6
10	5	10
15	6	15
21	7	21
28	8	28
36	9	36
45	10	45
55	11	55
66	12

Flow Chart

n	b	Output	n = a
1	10	1	No
2	5	2	No
3	10/3	-	No
4	5/2	-	No
5	2	5	No
6	5/3	-	No
7	10/7	-	No
8	5/4	-	No
9	10/9	-	No
10	1	10	Yes

This shows the multiples of 10.

A specific function can be used to make the algorithm terminate.

©2011 Grant Dwyer

Kruskal's Algorithm

List arcs in ascending order of weight.

Pick the arc of least weight.

If the next arc forms a cycle don’t use it, if it doesn’t use it.

Continue until all vertices are joined.

Arc	Weight	Used
DF	1	Yes
DC	1	Yes
DG	2	Yes
CF	2	No
EG	2	Yes
FG	3	No
DE	3	No
AC	3	Yes
BE	3	Yes
AB	4	No
BD	4	No
AD	5	No

Weight = 12

©2011 Grant Dwyer

Graph Theory Definitions

Graph: A set of nodes joined by arcs

Nodes: Points (vertices)

Arcs: Lines (edges)

Simple Graph: A graph without loops or multiple arcs

Subgraph of G: A graph whose nodes and arcs are all in the graph G

Complete Graph, K_n: A simple graph in which each of the nodes is connected by precisely one arc to every other node

Bipartite Graph: These graphs have two sets of nodes. The arcs only connect nodes from one set to the other, and do not connect nodes within a set

Complete Bipartite Graph: Every node in one set is connected to every node in the other set

Trail (Route): A sequence of arcs such that the end node of one arc is the start node of the next

Path: A trail with the restriction that no node is passed through more than once

Cycle: A closed trail where only the initial and final nodes are the same

Order of a Node: The number of arcs meeting at that node

Connected Graph: A graph where, for any two nodes, a path can be found connecting the two nodes

Eulerian Graph: A connected graph which has a closed trail containing every arc precisely once and all nodes 

have even order

Semi-Eulerian Graph: A connected graph with a trail which is not closed that contains every arc precisely once and only 2 nodes have odd order

Non-Eulerian Graph

Planar Graph: A graph which can be drawn in a plane in such a way that arcs only meet at nodes

Euler’s Relationship: For any connected graph drawn in the plane with R regions, N nodes and A arcs, R + N = A + 2

Network (Weighted Graph): A graph whose arcs have weights (numbers)

Digraph (Directed Graph): A graph with directed arcs

Matrix: A table showing all the information about the weights in a network

Tree: A connected graph with no cycles

Spanning Tree: Subgraphs that are also trees

Minimum Spanning Tree: A spanning tree where the total weight of the arcs is as small as possible

©2011 Grant Dwyer

Bin Packing

It is used to put a set of items that you need to fit into the minimum amount of bins.

2, 4, 3, 3, 2, 5, 4 (kg) in 8 kg piles

• First-Fit

Take the first item and put it into the first bin.

Put next item into the next bin it can fit into (either the first or another bin).

Try every item in the first, second, etc until all items are in the bins.

• First-Fit Decreasing

Arrange items into descending order.

Take the first item and put it into the first bin.

Put next item into the next bin it can fit into (either the first or another bin).

Try every item in the first, second, etc until all items are in the bins.

©2011 Grant Dwyer

Sorting

Use sorting to write the numbers 14, 10, 6, 15, 9, 21, 17 in ascending order.

• Bubble Sort

Look at the first 2 numbers, if in right order leave them, if not swap them.

Next pair of numbers will be dealt with the same way as the first 2 numbers.

Continue until you reach the other end, this is called a pass.

Go back to beginning and do it again until all numbers are in order.

4 Passes   7 swaps   21 comparisons

• Shuttle Sort

Look at the first 2 numbers, if in right order leave them, if not swap them, this is the first pass.

Next pair of numbers will be dealt with the same way as the first 2 numbers, if swap was made, compare the first number to the swapped one, swap if wrong way round, this is the second pass.

Compare third and fourth numbers, if swapped compare swapped number to the one before it and swap if needed.

Keep going backwards until no more swaps, this ends that pass.

Continue until all numbers are in the right order.

6 Passes   7 Swaps   11 Comparisons

©2011 Grant Dwyer