The Order Of An Algorithm Flashcards
(24 cards)
The efficiency of an algorithm
Is a measure of the run-time for the algorithm, often proportional to the number of operations to be executed.
The size of an algorithm
Is a measure of its complexity
The order of an algorithm
Is a measure of its efficiency as a function of the size of the problem
What’s the efficiency of bubble sorting algorithm as a function
1/2(n-1)n
What’s the measure of size for any sorting algorithm
n
Of what order is the bubble sorting algorithm is ?
Of quadratic order
What is an algorithm
It is a set of instructions
It must have a finite number of steps
It must work for any valid input
It must have an end
Full bin combinations algorithm explained
FInd combination of items that will completely fill a bin
Places remaining items using a first fit algorithm
First fit algorithm
Places items in the given order to the first available bin
It is a heuristic algorithm meaning it attemps to find the best optimal solution
First fit decreasing algorithm
Sort items in decreasing order by using another algorithm such as bubble sort or insertion sort and then performs first fit algorithm
Which algorithm between a full bin combinations and first fit algorithm produces the best optimal solution?
the full bin combinations algorithm
What is a graph
A graph is a series of nodes (or vertices) connected by edges (or arcs)
How to find the degree of a graph
To find the degree (or order or valency ) of a vertex count how many ends of edges (or arcs) there are at the vertex
Why can’t the order of a connected graph be an odd number?
Because in a connected graph it is possible to go from any vertex to the other
What is a loop ?
A loop is an edge (or arc) that starts and finshes at the same node
What is a tree ?
A tree is a connected graph with no cycles/loops
What is a spanning tree?
A spanning tree is a connected subgraph with no cycles/loops containing all vertices (or nodes)
How many edges in a tree of 10 nodes
9 edges (or arcs) because every node is visited only once
Isomorphic graph have
the same incidence matrix despite looking visually different
What is a network grpah
Adding a weight or value to nodes in a graph will produce a weighted grpah( or a network)
Planar graph defined
A graph where none of the edges are crossed by each other
Prim’s algorithm
will find the minumum spanning tree
It works by:
select any node to begin with
select the shortest edge connected to that node
select the shortest edge connecting any node that has been already
connected
repeat previous step until all nodes have been connected
Kruskal’s algorithm
selects the shortest edge in a network
select the next shortest edge which does not create a cycle
repeat previous steps until all nodes are connected
Dijkstra’s algorithm
