Study your flashcards anywhere!

Download the official Cram app for free >

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

image

Play button

image

Play button

image

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