Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
ALGO MOD7
| Question | Answer |
|---|---|
| this is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum | greedy algorithm |
| in many problems, this type of algorithm does not usually produce an optimal solution, but nonetheless may yield locally optimal solutions that approximate a global optimal solution in a reasonable time | greedy algorithm |
| a greedy strategy for the TSP has the following heuristic: "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; it is not guaranteed to find the best solution | greedy algorithm |
| in mathematical ______, greedy algortithms optimally solve combinatorial problems having the properties of matroids, and give constant-factor approximation for many optimization problems with submodular structure | optimization |
| in mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of __________, and give constant-factor approximation for many optimization problems with submodular structure | matroids |
| in mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids, and give constant-factor approximation for many optimization problems with ___________ structure | submodular |
| enumerate the 5 components of greedy algorithms | (1) CANDIDATE SET, (2) SELECTION FUNCTION, (3) FEASIBILITY FUNCTION, (4) OBJECTIVE FUNCTION, (5) SOLUTION FUNCTION [CSFOS] |
| this component of greedy algorithms is from which a solution is created | candidate set |
| this component of greedy algorithms chooses the best candidate to be added to the solution | selection function |
| this component of greedy algorithms is used to determine if a candidate can be used to contribute to the solution | feasibility function |
| this component of greedy algorithms is used to assign a value to a solution or a partial solution | objective function |
| this component of greedy algorithms is used to determine when a solution is complete | solution function |
| finding solution is quite ___ with a greedy algorithm for a problem | easy |
| analyzing the run time for greedy algorithms will often be much ___________ than for other algorithms like D&C | easier |
| for greedy algorithms, you have to work _____ to understand correctness issues | harder |
| even with the correct algorithm, this type of algorithm is hard to prove why it is correct | greedy |
| proving that a greedy algorithm is correct is more of an ___ than a ___ | art; science |
| enumerate the 3 examples of greedy algorithm | (1) PRIM'S ALGORITHM, (2) KRUSKAL'S ALGORITHM, (3) DIJKSTRA'S ALGORITHM [PKD] |
| what are the 4 other terms for prim's algorithm? | jarnik's algorithm, prim-jarnik algorithm, prim-dijkstra algorithm, DJP algorithm [JPPD] |
| this algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted 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, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex | prim's algorithm |
| this algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959 | prim's algorithm |
| Prim's algorithm was developed in the year ____ by Czech mathematician _______ | 1930; Vojtěch Jarník |
| Prim's algorithm was later rediscovered and republished by computer scientists _______ in the year ___ and _______ in the year ___ | Robert C. Prim; 1957; Edsger W. Dijkstra; 1959 |
| other well-known algorithms aside from prim's for finding minimum spanning trees include ___________ and ___________ | kruskal's algorithm; borůvka's algorithm |
| what is the main difference between prim's and kruskal's / borůvka's algorithm? | prim's algorithm only finds minimum spanning trees for connected graphs, while the others can find it even if graph is disconnected |
| the three MST algorithms (prim's, kruskal's, borůvka's) are equally fast for _____ graphs, but slower than other more sophisticated algorithms | sparse (few edges) |
| for graphs that are sufficiently ____, prim's algorithm can be made to run in linear time | dense |
| for graphs that are sufficiently dense, prim's algorithm can be made to run in ______ time | linear |
| these are used for network designs (i.e., telephone, electrical, hydraulic, TV cable, computer networks) | minimum spanning trees |
| these are used to find approimate solutions for the travelling salesman problem | minimum spanning trees |
| this is the process of adding white noise to a digital recording to reduce the noise/distortion | dithering |
| one disadvantage of this MST algorithm is that the list of edges has to be searched from beginning as new edge is added | prim's algorithm |
| one disadvantage of this MST algorithm is that if there are more than one edges having the same weight, then all possible spanning trees are required to be found for final MST | prim's algorithm |
| prim's algorithm has what worst-case time complexity? | O(n^2) where n is the number of vertices |
| in prim's, each iteration of for loop takes ____ time, so the total time complexity is O(n^2) | O(n) or linear |
| in prim's, if we store nodes not yet included in tree as a _____ tree, then the time complexity can be reduced to O(log n) time | red-black |
| in prim's, if we store nodes not yet included in tree as a red-black tree, then the time complexity can be reduced to _____ time | O(log n) |
| this is a special kind of tree that minimizes the lengths (or "weights") of the edges of the tree | minimum spanning tree |
| this has one path that joins any two vertices | tree |
| this is a tree that contains all of the graph's vertices, reaches out to all vertices (so it is connected), and is acyclic (has no nodes that loop to itself) | spanning tree |
| this MST algorithm always takes the lowest-cost edge between nodes in the spanning tree and nodes not yet in the spanning tree | prim's algorithm |
| dijkstra's algorithm has what worst-case time complexity? | O(|E| + |V|log|V|) where |E| is the number of edges and |V| is the number of vertices |
| this algorithm is an algorithm for finding the shortest path between nodes in a graph, which may represent, for example, road networks | dijkstra's algorithm |
| this algorithm was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later | dijkstra's algorithm |
| who conceived dijkstra's algorithm and in what year? | Edsger W. Dijkstra; 1956 |
| what year was dijkstra's algorithm published? | 1959 |
| this algorithm finds the minimum spanning tree by sorting first the edges of the graph in non-decreasing order of their weights | kruskal's algorithm |
| this algorithm was conceived by Joseph Kruskal in 1956 | kruskal's algorithm |
| kruskal actually rediscovered this algorithm in 1956 | Jarnik's algorithm or Prim's algorithm |
| the basic idea behind this algorithm is first scan all edges in increasing weight order, if an edge is safe, keep it example add it to the set A | kruskal's algorithm |
| this is a MST algorithm that finds an edge of the least possible weight that connects any two trees in the forest | borůvka's algorithm |
| kruskal's algorithm will find the MST using the graph and cost, this is called the ______ approach | merge-tree |
| kruskal's algorithm has what worst-case time complexity? | O(E log V) where E is the number of edges and V is the number of vertices |
| prim's algorithm runs faster for ____ graphs, kruskal's runs faster for ____ graphs | dense; sparse |
Created by:
user-1791948