Study your flashcards anywhere!
Download the official Cram app for free >
 Shuffle Toggle OnToggle Off
 Alphabetize Toggle OnToggle Off
 Front First Toggle OnToggle Off
 Both Sides Toggle OnToggle Off
 Read Toggle OnToggle Off
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
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 yesorno 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 Bruteforce 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 viceversa


Optimization problem errors in heuristics

Heuristics can give a suboptimal value for an optimization problem (e.g., answer "5" when a 6clique 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 kClique Problem

kclique 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 kclique using exhaustive search

O(n^k)


The error bound in your output

optimumsize/outputsize
(e.g., heuristic returns 6clique but ∃ a 15clique: 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 2approximation algorithm for vertex cover has an error of no more than

2


A 2approximation 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
