Module #7 Flashcards
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
greedy algorithms have how many components
5 components
from which a solution is created
Candidate Set
which chooses the best
candidate to be added to the solution
Selection Function
that is used to determine if a
candidate can be used to contribute to a solution
Feasibility Function
which assigns a value to a
solution, or a partial solution, and
Objective Function
which will indicate when we have
discovered a complete solution
Solution Function
is a greedy algorithm that finds a minimum spanning tree for a weighted
undirected graph.
Prim’s Algorithm
also known as Jarnik’s Algorithm
Prim’s Algorithm
The algorithm operates by building this tree one vertex at a time, from
an arbitrary starting vertex, at each step adding the cheapest possible
connection from the tree to another vertex.
Prim’s Algorithm
The prim’s algorithm was developed in ____ by Czech mathematician Vojtěch Jarník
1930
Prim’s Algorithm was later rediscovered and republished by computer scientists Robert C. Prim in
1957
Prim’s Algorithm was later rediscovered and republished by computer scientists Robert C. Prim and Edsger W. Dijkstra in
1959
Time Complexity of Prim’s Algorithm
O(n^2)
Each iteration of for loop takes
O(n) time
is a special kind of tree that minimizes the lengths (or “weights”) of the edges of the tree
minimum spanning tree
Kruskal’s Algorithm was first described by Kruskal in ______ in the same paper where he rediscovered Jarnik’s algorithm.
1956
Kruskal’s Algorithm was also rediscovered by Loberman and Weinberger in what year
1957
is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the
forest.
Kruskal’s algorithm
It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
Kruskal’s Algorithm
Time Complexity of Kruskal’s Algorithm
O(E log E)
for finding the shortest path from
a given node to all other nodes in a graph
Dijkstra’s algorithm
Always takes the shortest edge connecting a known node to an unknown
node
Dijkstra’s algorithm
is an algorithm for finding the shortest paths between nodes
in a graph, which may represent, for example, road networks.
Dijkstra’s algorithm
Dijkstra’s algorithm was conceived by computer scientist Edsger W. Dijkstra in
1956
The algorithm exists in many variants. Dijkstra’s original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.
Dijkstra’s algorithm
Edsger Dijkstra invented Dijkstra’s Algorithm in
1959
He kick-started what became known as the Structured Programming movement.
Edsger Dijkstra
was a university professor for much of his life, which spanned the era when basic methods of computer programming were still being worked out.
Edsger Dijkstra
Dijkstra pointed out that this
resulted in programs that were difficult to follow, and therefore very difficult
for other programmers to change the journal of the Association for Computing Machinery entitled Go To Statement Considered Harmful in a letter in
1968
He invented the Semaphore, the mechanism that allows concurrent programs to share a single resource.
Edsger Dijkstra
was born in the Netherlands, where he worked as a university researcher and professor until 1984
Edsger Dijkstra
Edsger Dijkstra took up a professorship at the
University of Texas at Austin
is an algorithm we can use to find shortest
distances or minimum costs depending on what is represented in a graph.
Dijkstra’s algorithm
Time Complexity of Dijkstra’s algorithm
O(E+V log V)
