CodeBlanks Logo Icon CodeBlanks
Login Register

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.

Practice 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)).

Starter code

solution.py
def is_within_factor(approx, optimal, factor):
    # Is solution within factor

Sample solution

solution.py
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))

Expected output

True

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 What does a 2-approximation algorithm give in the worst case?

  • At most twice optimal Correct answer
  • Optimal
  • Exponential time
  • No solution

Explanation: A 2-approximation gives at most twice the optimum.

2 Comparison

Question 
if approx <= optimal * ____:
Answer 
if approx <= optimal * factor:

Explanation: factor is right.

3 Summary - Approximation and randomized: match the terms

Term Meaning
find_max Maximum
sample_max Sample
approx_ratio Ratio
factor Factor

All lessons in Expert

1 Amortized analysis

  1. What is amortized?
  2. Aggregate method
  3. Dynamic array example
  4. Summary - Amortized

2 NP-completeness

  1. P and NP
  2. NP-complete
  3. Reduction
  4. Summary - NP-completeness

3 Approximation and randomized

  1. Approximation algorithms
  2. Randomized algorithms
  3. Las Vegas and Monte Carlo
  4. Summary - Approximation and randomized

4 String matching

  1. KMP algorithm
  2. Rabin-Karp
  3. Boyer-Moore
  4. Z-algorithm
  5. Suffix array
  6. Summary - String matching

5 Computational geometry

  1. Vector cross product
  2. Convex hull
  3. Line intersection
  4. Closest pair
  5. Point in polygon
  6. Summary - Geometry

6 Network flow

  1. Flow network
  2. Ford-Fulkerson
  3. Edmonds-Karp
  4. Max-flow min-cut
  5. Bipartite matching
  6. Summary - Network flow

7 Game theory and parallel

  1. Minimax
  2. Alpha-beta pruning
  3. Nash equilibrium
  4. Parallel algorithms
  5. MapReduce
  6. Summary - Game theory and parallel

8 Expert final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4
  5. Challenge 5