• Shuffle
Toggle On
Toggle Off
• Alphabetize
Toggle On
Toggle Off
• Front First
Toggle On
Toggle Off
• Both Sides
Toggle On
Toggle Off
Toggle On
Toggle 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

A key: Read text to speech.a key

Play button

Play button

Progress

1/22

Click to flip

### 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