Week 8 - Greedy Algorithms Flashcards
What is a greedy algorithm?
A greedy algorithm is an approach that makes the locally optimal choice at each step with the hope of finding the global optimum. It solves problems by choosing the best option available at the moment, without considering the broader context.
What is the knapsack problem?
The knapsack problem involves selecting a combination of items with given weights and values to maximize the total value without exceeding a weight limit, such as a knapsack’s capacity of 35 kg.
What is the downside of greedy algorithms?
The downside of greedy algorithms is that they may not always produce the optimal solution for all problems, as they only consider local optimal choices and can miss the globally optimal solution.
What is a set covering problem?
The set covering problem involves finding the smallest subset of sets that covers all elements in a universal set, minimizing the total number of sets used.
What is an example of a set covering problem?
An example of a set covering problem is selecting a subset of radio stations to play on in order to cover all cities across Australia while minimizing costs, given that each station covers different cities with some overlaps.
What is a powerset?
The powerset of a set is the set of all possible subsets, including the empty set and the set itself. This is 2^n possible subsets.
What is the naive “brute force” for a set covering problem?
The naive “brute force” approach for a set covering problem involves two steps:
- List all possible subsets: Generate every possible subset of sets, which amounts to (2^n) subsets, where (n) is the total number of sets.
- Select the optimal subset: Identify the smallest subset from these that covers all elements in the universal set.
The time complexity is O(2^n) which is impractical for large values of n.
What algorithm can be used to solve a set covering problem in a reasonable time?
An approximation algorithm for the set covering problem is the Greedy Approximation Algorithm. It involves:
- Selecting the Set: Pick the station (or set) that covers the most cities, even if it overlaps with some cities already covered.
- Repeating: Continue selecting sets until all cities are covered.
This approach provides a “good enough” solution efficiently.
List some of the operators for sets.
Some common operators for sets include:
-
Union (
|): Combines all unique elements from both sets. -
Intersection (
&): Finds common elements present in both sets. -
Difference (
-): Identifies elements in one set that are not in the other.
What are the two key factors on which approximation algorithms are evaluated?
The two key factors on which approximation algorithms are evaluated are:
- Speed: How quickly the algorithm can compute a solution.
- Quality: How close the computed solution is to the optimal solution.
What are NP-complete problems?
NP-complete problems are a class of problems for which finding an exact solution requires examining all possible solutions (brute force), leading to exponential time complexities, such as (O(2^n)) for the Set-Covering Problem and (O(n!)) for the Traveling Salesman Problem (TSP). These problems are both difficult to solve and to verify efficiently.
How can you recognise an NP-complete problem?
To recognize an NP-complete problem, look for characteristics such as the need to examine all combinations or possible solutions, difficulty in breaking the problem into smaller sub-problems, and challenges with sequences or sets. If the problem can be reduced to or restated as a known NP-complete problem like the set-covering problem or the traveling-salesperson problem, it is likely NP-complete.
