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
