1: Algorithms & Graph Theory

Question 1

Bubble Sort Algorithm (1:2, 3)

Answer 1

1. Start at the beginning of the working list and move from left to right, comparing adjacent items
   a) If they are in order, leave them
   b) If they aren’t in order, swap them
2. When you get to the end of the working list, the last item will be in its final position. Remove this item from the working list
3. If you have made some swaps in the last pass, repeat steps 1 & 2
4. When a pass is completed without any swaps, the list is in order

Question 2

Quick Sort Algorithm (6)

Answer 2

1. Choose item at the midpoint of the list to be the first pivot
2. Write down all the items that are less than the pivot, keeping their order in a sub-list
3. Write down the pivot
4. Write down the remaining items in a sub-list
5. Repeat steps 1 to 4 for each sub-list
6. When all the items have been chosen as pivots, stop

Question 3

First-Fit Algorithm (2)

Answer 3

1. Take the items in the given order

2. Pack each item in the first available bin that can take it, starting from bin 1 each time

Question 4

First-Fit Algorithm +/- (2)

Answer 4

+ Quick and easy to implement

- Not likely to lead to a good solution

Question 5

First-Fit Decreasing Algorithm (2)

Answer 5

1. Sort the items into descending order

2. Apply the first-fit algorithm on the reordered list

Question 6

First-Fit Decreasing Algorithm +/- (3)

Answer 6

+ Usually get a fairly good solution
+ Quick and easy to implement
- May not get an optimal solution

Question 7

Full-Bin Method (2)

Answer 7

1. Use inspection to find combinations of items that will fill a bin and pack these items first
2. Pack any remaining items using the first-fit algorithm

Question 8

Full-Bin Method +/- (2)

Answer 8

+ Usually get a good solution

- Difficult to do, especially when the numbers are plentiful and awkward

Question 9

Vertex / Node

Answer 9

Point on a graph

Question 10

Edge / Arc

Answer 10

Line segment joining two vertices

Question 11

Weight

Answer 11

Number associated with an edge

Question 12

Weighted Graph / Network

Answer 12

Graph with weighted edges

Question 13

Vertex Set

Answer 13

List of vertices

Question 14

Edge Set

Answer 14

List of edges

Question 15

Subgraph

Answer 15

Part of an original graph, all of whose vertices and edges belong to the original graph

Question 16

Degree / Valency / Order

Answer 16

Number of edges incident to a vertex

Question 17

Even / Odd Degree

Answer 17

Even / odd number of edges incident to a vertex

Question 18

Walk

Answer 18

Route through a graph along the edges from one vertex to the next

Question 19

Path

Answer 19

Walk in which no vertex is visited more than once

Question 20

Trail

Answer 20

Walk in which no edge is visited more than once

Question 21

Cycle

Answer 21

Walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once

Question 22

Hamiltonian Cycle

Answer 22

Cycle that includes every vertex

Question 23

Connected Vertices

Answer 23

Two vertices are connected if there is a path between them

Question 24

Connected Graph

Answer 24

A graph is connected if all of its vertices are connected

Question 25

Loop

Answer 25

Edge that starts and finishes at the same vertex

Question 26

Simple Graph

Answer 26

Graph in which there are no loops and there is, at most, one edge joining any pair of vertices

Question 27

Directed Edge

Answer 27

An edge with a direction associated with it

Question 28

Digraph

Answer 28

Graph with directed edges (a.k.a., directed graph)

Question 29

Euler’s Handshaking Lemma (2)

Answer 29

• In any undirected graph, the sum of the degrees of the vertices = 2 x the number of edges
• Thus, in any undirected graph, there is an even number of odd vertices

Question 30

Tree

Answer 30

Connected graph with no cycles

Question 31

Spanning Tree

Answer 31

Subgraph, which contains all the vertices of the original graph and is a tree

Question 32

Complete Graph

Answer 32

Graph in which every vertex is joined, by a single edge, to every other vertex (notation: K_n where n is number of vertices)

Question 33

Isomorphic Graphs

Answer 33

Graphs which show the same information but may be drawn differently

Question 34

Planar Graph

Answer 34

Graph that can be drawn in a plane such that no two edges meet except at a vertex

Question 35

Planarity Algorithm (5, 1:4))

Answer 35

1. Identify a Hamiltonian cycle
2. Draw a polygon with vertices labelled to mach the ones in the Hamiltonian cycle
3. Draw edges inside the polygon to match the edges of the original graph not already represented by the polygon
4. Make a list of all edges inside the polygon
5. Choose any unlabelled edge in the list and label it ‘I’. If all edges are now labelled, the graph is planar
6. Look at any unlabelled edges that cross the edge(s) just labelled:
   - If there are none, go back to step 5
   - If any of these edges cross each other, the graph is non-planar
   - If none of these edges cross each other, give them the opposite label to the edge(s) just labelled
   - If all edges are now labelled, the graph is planar. Otherwise, go back to the start of step 6

Question 36

Algorithm

Answer 36

A finite sequence of step-by-step instructions carried out to solve a problem

Question 37

Eulerian Graph

Answer 37

Connected graph, whose vertices are all even. It contains an Eulerian cycle

Question 38

Eulerian Cycle

Answer 38

Cycle, that includes every edge exactly once

Question 39

Semi-Eulerian Graph

Answer 39

Connected graph with exactly two odd vertices. It contains a trail, that includes every edge but starts and finishes at different vertices