Definitons + Key Memorisation Flashcards
Heuristic algorithm
When an algorithm gives an efficient solution but not necessarily the most optimal
Such as first fit / first fit decreasing
What is n for thr complexity in all these algorithms?
The Number of THINGS TO SORT
So if 5 numbers ti sort, n is 5, put n into equation, and compare with total number of comapriosns to find formual (adjust if it’s one below the triangle number )
Simple graph
No loops or multiple edges
Total number of edges in a complete graph
If all are connected to Esch other, do it for the first few, you’ll see follows triangle numbers, hence 1/2n (n-1)
Tree?
Amount of nodes
Cycle
Simple connected graph with minimum amount of nodes
- no loops multiple edges, indirectly connected
N-1
Where it can go around and around
NETWORK defintion
A graph with WEIGHTED ARCS
MST ?
Tree with least weight
- use Kruskal and prims algorithm to find this
What does isomorphic mean
When two graphs are exactly the same ( drawn differently)
They will have the SAME incidence matrix
What does greedy mean as an algorithm
Give 2 examples, and are they optimal?
Greedy are algorithms that DO EVERYTHING AT ONCE , no consideration to what may happen later , no strategy
For example Kruskal does randomly and prims
However these still yield optimal solutions, thus not heuristic …
REMEMBER how to represent Kruskal workings
Each arc you choose write it down
- but when you purposefully skip an arc as it would cause a cycle, STILL WRITE, BUT CROSS IT OUT
How to represent prims in both methods
How to do table method
1) MUST SHOW ORDER THATS IT
2) Table method = pick a coloumn, label with number and INSTANTLY DELETE row (to stop cycles)
- fund lowest in coloumn record, other letter label and delete row. Repeat
How to find shortest path in a system ?
And longest?
Method AND how to find route
Shortest = Dijskrta ( three box ), find route by tracing back between final node for valued that perfectly subtract , can be more than one route
Longest = CPA (forward back pass), find the route by looking at the CRITICAL PATHS
What happens if indepent float negative?
Just call it 0 bruh
Remember durations!
2 important rules for drawing activities
1) when two acitvites coming from same have to enter same!
1) must put a dummy to ensure each activity is indecently labelled uniquely (don’t draw bith going in)
2) also always draw lowest dummies, and pick the activity which is by itself first
Remember twice as many A AS B means what I’m terms of a and b quantities
A is twice B
So if B is 1, A must be atleast 2
Hence X >= 2Y
BUN TL , it means a must be 2 times B calm move on
How to do blend / combination inequalities
Blend means percentage of total thing. If total thing represented as x +y, make sure to put this in brackets
Combination means do x / quantity etc = 1 and multiply through!
What difference between standard form and augmented form
Standard is just maximise, non negative variables, non negativity cinstraints for 0, and all functions are less than some positve value
Augmented is when eberythign is equation, using slack etc
Why do we use simplex in first place
Can’t draw more than 3 variables
Algorithmic method
What happens between every iteration for simplex
3 things
Moves to the next vertex on the feasibility region whcih improves it the greatest
- swaps basic for non basic variable around
- checks if more room for improvement, if not, found optimal solution
What does having slack variables full mean in cintext
Depends on context but means you haven’t used all the resoruces best as possible, there is a better solution
However when there isn’t a better solution, there might still be some slack, as some must be wasted to reach full
