Summary - Approximation and randomized

Print a randomized approximate solution in a mini task.

Summary - Approximation and randomized

In this group you learned approximation and randomized algorithms. Approximation ratio, Las Vegas and Monte Carlo combine to give practical approaches to NP-complete problems.

Now you will write a function that brings all pieces together. This summary unites the group's concepts in a single piece of code.

Exercise is_within_factor function

Write is_within_factor(approx, optimal, factor). Return True if approx <= optimal * factor. Print True with print(is_within_factor(9, 9, 2)).

Show example solution

def is_within_factor(approx, optimal, factor):
    # Is solution within factor
    if approx <= optimal * factor:
        return True
    return False
print(is_within_factor(9, 9, 2))

Test yourself

What does a 2-approximation algorithm give in the worst case?
- At most twice optimal
- Optimal
- Exponential time
- No solution
Show answer

At most twice optimal — A 2-approximation gives at most twice the optimum.

Comparison

if approx <= optimal * ____:

Show answer

if approx <= optimal * factor:

Summary - Approximation and randomized: match the terms

find_max

Maximum
sample_max

Sample
approx_ratio

Ratio
factor

Factor

Next lesson: KMP algorithm

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies