Algorithms Flashcards
What are the advantages and disadvantages of First-fit decreasing algorithm?
Advantages: easy to implement.
Disadvantage: may not provide optimal solution.
Advantages and disadvantages of full bin algorithm?
Advantages: provides good solution.
Disadvantages: difficult to do with large amounts of numbers.
What does critical path analysis enable us to do?
Plan and monitor complex projects
What does critical path analysis
aim to do?
Find the shortest possible time a project can be completed.
Given we have the total of the nodes in a graph, how do we find out how many arcs are in the graph?
Total order of nodes/2
If a graph has a total order of nodes=17 are we able to construct it , explain your reasoning.
We can’t , arcs have an even number of ends and also the number of arcs is determined by the total order/2 , we can’t have .5 of a node.
What is a walk?
A sequence of vertices that flow , you can walk on each edge and vertex more than once.
What is a path?
Sequence of edges that flow on, can go through the same vertex more than once.
What is a cycle/circuit?
Path where End vertex is the start vertex
What is a simple graph?
A graph with no loops or multiple edges.
What is a connected graph.
A connected graph has every vertex in the graph connected.
What is a complete graph?
A graph where all vertices are directly connected.
All vertices in a graph are directly connected. Find (algebraically) the number of edges in the graph.
1/2 n(n-1)
What are bipartite graphs?
A graph with 2 sets of vertices that can be only have one edge connecting to each vertex directly (think of a neural think network and also those join word to definition things).
What is planar graph?
A graph with no overlapping edges.
What is an isomorphic graph?
Identical graphs drawn differently.
Which algorithm is best suited for traversing heavily dense graphs
Prime algorithm.
Of what order/complexity are prims and Krystal’s algorithms?
Cubic
After using Kruskals and Prims algorithms starting with n edges.
How many edges will the minimum spanning tree have?
n-1.
Define the term tree.
A graph with no cycles.
What do trees include?
All vertices.
Eulerian graphs are?
Connected graphs with all nodes of even valency.
Semi-Eulerian graphs are?
A graph with exactly 2 nodes with odd valency.
What are the purposes of dummy activities?
-ensure each activity has a unique pair of start and end nodes.
- to show dependency in complex situations.
