modelling with algorithms Flashcards
unambiguous
person or machine does not have to make choices (other than true or false)
deterministic
output always the same (no randomness)
methods of bin packing
first fit
first fit decreasing
full bin packing
pros and cons of methods of bin packing
full bin works well for small numbers of items and gives optimum solution
however time grows exponentially
other methods faster
heuristic
use some knowledge about the problem to reduce the time taken, sometimes trading speed for optimal outcome
quicksort
pivot element
compare to each element in list sort before or after
pick another pivot
repeat until sorted
Algorithmic complexity
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
Bubble sort complexity
Quadratic
Insertion sort complexity
Quadratic
Merge sort complexity
Log(n)
Full bin packing complexity
kn
A computer algorithm of quadratic complexity takes 0.25 s for 100 entries, how long would it take for 400?
100x4 = 400
0.25 x 16 = 4s
Simple graph
No loops or multiple edges
Degree/ order of vertex
How many edges leave the vertex
No of edges
0.5n(n-1)
Sum of degrees
n(n-1)
Sum of degrees (no edges)
Sum of degrees = 2x no of edges
Bipartide
Two sets of vertices
Edges connect vertices from one set to another do knot connect vertices within a set
Complete bipartides denoted by
Kr,s
Where r= vertices in set 1
And s= vertices in set 2
Isomorphic
Same graph rearranged
Eulerian
All orders are even
Semi-eulerian
Two odd orders
Tree
Simple connected graph with minimum possible no of arcs
Network
Arcs have weights
Forest
Collection of trees
Disconnected with no cycles
Incidence matrix
Can represent arcs and loops
How many ways to get from one to another
Kruskal’s
Minimum spanning tree
Add edge with lowest weight unless it creates a cycle
Prim’s
Start at one node
Add shortest edge connected to node
Add shortest node connected to any node already in tree
Dijkstras
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
Adjacency matrix
Weighted graphs
Prim’s from table
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
Dijkstras from table
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
