- Shuffle
Toggle OnToggle Off
- Alphabetize
Toggle OnToggle Off
- Front First
Toggle OnToggle Off
- Both Sides
Toggle OnToggle Off
Front
How to study your flashcards.
Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key
Up/Down arrow keys: Flip the card between the front and back.down keyup key
H key: Show hint (3rd side).h key
PLAY BUTTON
PLAY BUTTON
22 Cards in this Set
- Front
- Back
|
Definition of Optimization Problem
|
finding the best solution from all feasible solutions (the best answer to a particular problem)
|
|
Definition of Decision Problem
|
any arbitrary yes-or-no question whose answers depend on the values of some input parameters
|
|
Definition of Algorithms
|
method of translating inputs into outputs
|
|
Definition of Greedy Algorithms
|
Set of algorithms designed to solve optimization problems by calculating the locally optimal solution at every iteration.
|
|
One main difference between a greedy algorithm and dynamic programming
|
A greedy algorithm never reconsiders its choices while dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous decision.
|
|
Definition of vertex disjoint
|
no common vertices
|
|
Definition of heuristics
|
"rule of thumb"-rules, suggestions, guides or techniques that may be useful in making progress toward a solution of a problem
|
|
Definition of Brute-force search or exhaustive search
|
systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement
|
|
Decision problem errors in heuristics
|
Heuristics can say "Yes" when the correct answer is "No", and vice-versa
|
|
Optimization problem errors in heuristics
|
Heuristics can give a suboptimal value for an optimization problem (e.g., answer "5" when a 6-clique is present
|
|
Construction problem errors in heuristics
|
Heuristics can give a suboptimal object (e.g., construct a clique that is not the largest in the graph)
|
|
A false positive error
|
Saying "Yes" when the correct answer is "No"
|
|
A false negative error
|
Saying "No" when the correct answer is "Yes"
|
|
Define k-Clique Problem
|
k-clique is a group of k nodes, where each node in the clique is connected to every other node in the clique.
|
|
Heuristic that only comes up with false negatives
|
greedy heuristic
|
|
Running time for k-clique using exhaustive search
|
O(n^k)
|
|
The error bound in your output
|
optimum-size/output-size
(e.g., heuristic returns 6-clique but ∃ a 15-clique: error is 15/6 = 2.5) |
|
define vertex cover
|
subset of a graph s.t. every edge has an endpoint
|
|
Greedy algorithm for vertex cover
|
Let Vo=0
While G has an edge, DO -let v be a node with at least one edge incident with v, and add v to Vo -delete all edges incident to v from G -Return Vo |
|
A 2-approximation algorithm for vertex cover has an error of no more than
|
2
|
|
A 2-approximation algorithm for vertex cover
|
Let Vo=0
While G has any edge, DO -Pick any edge in G and add both its endpoints (v and w) to Vo -delete all edges incident with either v or w from G -Return Vo |
|
Cardinality
|
number of elements in a set
|
