modelling with algorithms

Question 1

unambiguous

Answer 1

person or machine does not have to make choices (other than true or false)

Question 2

deterministic

Answer 2

output always the same (no randomness)

Question 3

methods of bin packing

Answer 3

first fit
first fit decreasing
full bin packing

Question 4

pros and cons of methods of bin packing

Answer 4

full bin works well for small numbers of items and gives optimum solution
however time grows exponentially
other methods faster

Question 5

heuristic

Answer 5

use some knowledge about the problem to reduce the time taken, sometimes trading speed for optimal outcome

Question 6

quicksort

Answer 6

pivot element
compare to each element in list sort before or after
pick another pivot
repeat until sorted

Question 7

Algorithmic complexity

Answer 7

Measure of how many basic operations (comparisons) an algorithm needs to run based on the size of the problem
Used to classify based on performance
Worst case scenario
Big O notation

Question 8

Bubble sort complexity

Answer 8

Quadratic

Question 9

Insertion sort complexity

Answer 9

Quadratic

Question 10

Merge sort complexity

Answer 10

Log(n)

Question 11

Full bin packing complexity

Answer 11

kn

Question 12

A computer algorithm of quadratic complexity takes 0.25 s for 100 entries, how long would it take for 400?

Answer 12

100x4 = 400
0.25 x 16 = 4s

Question 13

Simple graph

Answer 13

No loops or multiple edges

Question 14

Degree/ order of vertex

Answer 14

How many edges leave the vertex

Question 15

No of edges

Answer 15

0.5n(n-1)

Question 16

Sum of degrees

Answer 16

n(n-1)

Question 17

Sum of degrees (no edges)

Answer 17

Sum of degrees = 2x no of edges

Question 18

Bipartide

Answer 18

Two sets of vertices
Edges connect vertices from one set to another do knot connect vertices within a set

Question 19

Complete bipartides denoted by

Answer 19

Kr,s
Where r= vertices in set 1
And s= vertices in set 2

Question 20

Isomorphic

Answer 20

Same graph rearranged

Question 21

Eulerian

Answer 21

All orders are even

Question 22

Semi-eulerian

Answer 22

Two odd orders

Question 23

Tree

Answer 23

Simple connected graph with minimum possible no of arcs

Question 24

Network

Answer 24

Arcs have weights

Question 25

Forest

Answer 25

Collection of trees Disconnected with no cycles

Question 26

Incidence matrix

Answer 26

Can represent arcs and loops How many ways to get from one to another

Question 27

Kruskal’s

Answer 27

Minimum spanning tree Add edge with lowest weight unless it creates a cycle

Question 28

Prim’s

Answer 28

Start at one node Add shortest edge connected to node Add shortest node connected to any node already in tree

Question 29

Dijkstras

Answer 29

Shortest path Start at A Label node and write distance Update all adjacent nodes Pick node with smallest working value Work backwards from end to give shortest path

Question 30

Adjacency matrix

Answer 30

Weighted graphs

Question 31

Prim’s from table

Answer 31

Choose vertex Delete row Number column Circle lowest undeleted entry in numbered columns Ringed entry = next to be added to tree Repeat until all rows deleted

Question 32

Dijkstras from table

Answer 32

Label starting vertex and cross out column Work across row adding working values to each box Label box with lowest working value and cross out its column Work along row updating any working values Repeat until all columns deleted