## ← Quantifying The Error - Intro to Theoretical Computer Science

• 2 Followers
• 18 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=ZgZlRzDrle4" data-team="udacity"></div> ``` 1 Language

Showing Revision 2 created 05/25/2016 by Udacity Robot.

1. So let's get the facts. The optimum solution contains, at most, N objects,
2. simply because there's no more than N objects in the input itself. So it's almost a very coarse estimate,
3. but it'll do for us. So due to the rounding, we may introduce some error. So the algorithm, when working with the rounded objects,
4. might tell you that it's best thing to take this object here, this object here, this object here, and this object here, for example.
5. But instead, it could have been better to actually take this one here instead of that one here.
6. Or this object here instead of this object, and so on. Well, some, some might also be the same,
7. but sometimes we might make mistakes by just taking the wrong objects. So we know that these kind of mistakes
8. can only be made if the value of A divided by X, rounded down, is the same as the value of B divided by X, rounded down.
9. So mistakes of this kind, taking the wrong object, can only be made if, to the algorithm, object A, value-wise,
10. looks the same to the algorithm as object B, value-wise. Which means that the value of A--
11. so the original value, divided by X, rounded down, is the same as the value of B divided by X, rounded down.
12. But that actually allows us to quantify a mistake. So mistakes can only be made if this condition here is fulfilled.
13. Now, the amount of value lost in each mistake that we make is, of course, the value of the object, B,
14. which is the more valuable object we should have taken, minus the value of object A.
15. And now my question to you, and this is of course a bit challenging, is what is the maximum difference in value
16. that actually objects B and A can have? And the way to figure this out is to look at this condition, because the mistake is only made
17. if this here is fulfilled. So what I would like you to figure out is what is the maximum difference in value between the objects B and A?