Module 7 Flashcards
It is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.
Greedy Algorithm
In many problems, it does not usually produce an optimal solution.
Greedy Strategy/Algorithm
It may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.
Greedy Heuristic/Algorithm
What is the heuristic of the travelling salesman problem?
“At each step of the journey, visit the nearest unvisited city.”
This heuristic does not intend to find a best solution, but it terminates in a reasonable number of steps.
Greedy Algorithm/Heuristic
In mathematical optimization, these optimally solve combinatorial problems having the properties of matroids, and give constant-factor approximations to optimization problems with submodular structure.
Greedy Algorithm
What are the Five Components of Greedy Algorithms?
(Ca - Se - F - O - S)
- Candidate Set
- Selection Function
- Feasibility Function
- Objective Function
- Solution Function
This component creates a solution.
Candidate Set
This component chooses the best candidate to be added to the solution.
Selection Function
This component determines if a candidate can be used to contribute to a solution.
Feasibility Function
This component assigns a value to a solution or a partial solution.
Objective Function
This component indicates when we have discovered a complete solution.
Solution function
What are the advantages of Greedy Algorithm?
- Finding a solution is quite easy.
- Analyzing the run time is generally much easier than other techniques.
What are the disadvantages of Greedy Algorithm?
- You have to work much harder to understand correctness issues.
- Even with the correct algorithm, it is hard to prove why it is correct.
- Proving that a greedy algorithm is correct is more of an art than a science.
In computer science, this algorithm (also known as Jarnik’s algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.
Prim’s Algorithm
This algorithm finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
Prim’s Algorithm
This algorithm operates by building this tree one vertex at a time, starting from an arbitrary vertex, at each step adding the cheapest possible connection from the tree to another vertex.
Prim’s Algorithm
When was Jarnik’s algorithm developed?
1930 by Czech Mathematician Vojtech Jarnik (Jarnik30)
When was Jarnik’s algorithm rediscovered by Robert C. Prim?
1957 (Prim57)
Prim’s Algorithm is also called?
- Jarnik’s Algorithm
- Prim-Jarnik Algorithm
- Prim-Dijkstra Algorithm
- DJP Algorithm
True or False
The most basic form of Prim’s algorithm only finds minimum spanning trees in connected graphs.
True
True or False
Prim’s algorithm can be used to find the minimum spanning forest for each connected component of a graph.
True
Minimum spanning trees are used for what?
Network Designs
What are the disadvantages of Prim’s algorithms?
- List of edges has to be searched from beginning as new edge gets added.
- If there are more than one edges having the same weight, then all possible spanning trees are to be found for the final minimal tree.
What is the time required by Prim’s algorithm where “n” is number of vertices in graph “G”?
O(n^2)
How long does each loop iteration of Prim’s algorithm take?
O(n)
In Prim’s algorithm, if we store nodes not yet included in the tree as a red-black tree, then how long does the algorithm take?
O(log n)
This tree is a kind of tree that minimizes the lengths or weights of the edges of the tree.
Minimum Spanning Tree
A tree that has one path joins how many vertices?
Two
A spanning tree of a graph is a tree that:
- Contains all original vertices
- Spans all vertices
- Is acyclic
How many steps does Prim’s algorithm have?
7 Steps (Prim7)
This algorithm is used for finding a minimum-cost spanning tree.
Kruskal’s Algorithm
This algorithm always tries the lowest-cost remaining edge.
Kruskal’s Algorithm
When did Kruskal rediscover Jarnik’s algorithm?
1956 (Kuskal56)
It is a minimum-spanning-tree-algorithm that scans all edges in increasing weight order; if an edge is safe, keep it.
Kruskal’s Algorithm
It finds an edge of the least possible weight that connects any two trees in the forest.
Kruskal’s Algorithm
It is a greedy algorithm as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
Kruskal’s Algorithm
This algorithm finds a subset of the edges that forms a tree with every vertex, where the total weight of all edges is minimized.
Kruskal’s Algorithm
In this algorithm, if the graph is not connected, it finds a minimum spanning forest (a minimum spanning tree for each connected component).
Kruskal’s Algorithm
How many steps does Kruskal’s algorithm have?
3 Steps (3skal)
In this algorithm, all of the edges are listed and sorted based on their cost.
Kruskal’s Algorithm
What is the time complexity of Kruskal’s algorithm?
O(E log E) or O(E log V), where E is the number of edges and V is the number of vertices.
This algorithm is used for finding the shortest path from a given node to all other nodes in a graph.
Dijkstra’s Algorithm
This algorithm always takes the shortest path from a known node to an unknown node.
Dijkstra’s Algorithm
When was Dijkstra’s algorithm created?
Created by Edsger W. Dijkstra in 1956.
When was Dijkstra’s algorithm published?
Published by Edsger W. Dijkstra in 1956.
True or False
Dijkstra’s algorithm finds the shortest path between two nodes, but a more common variant finds the shortest paths from the source node to all other nodes.
True
True or False
Dijkstra’s algorithm works backward from the end, finding the shortest leg each time.
True
When did Dijkstra point out to ACM that the Go To statement is considered harmful?
1968
This computer scientist invented the Semaphore, the mechanism that allows concurrent programs to share a single resource.
Edsger W. Dijkstra
How many steps does Dijkstra’s algorithm have?
5 Steps
What is the time complexity of Dijkstra’s algorithm?
O(|E| + |V| log |V|)
