Greedy Algorithms

Question 1

Np-complete

Answer 1

Problems without a fast algorithmic solution

Question 2

Approximation algorithms

Answer 2

Find approximate solutions to np-complete problems quickly
Judged by their speed and accuracy to the optimal solution

Question 3

Greedy strategy

Answer 3

At each step you pick the locally optimal solution.
These algorithms are simple to write but normally get pretty close.

Question 4

Set union

Answer 4

Combine all elements of two sets

Question 5

Set intersection

Answer 5

Take the common elements of two sets

Question 6

Set difference

Answer 6

Take the non-shared elements of two sets

Question 7

6 signs a problem might be np-complete

Answer 7

The algorithm is fast with a few items but quickly slows down

“All combinations of x”

“Every possible version of X” and can’t be broken into smaller sub problems

Difficult to solve problems with a sequence ie a sequence of irises

Hard to solve problems with a set

Can the problem be restated as a set covering problem or the traveling sales person problem?