Testing n simultaneous conditions

Guys I'm having trouble solving this question. I gave it a lot of thought but sadly I couldn't come up with a way to go about it. I thought of dynamic programming and specifically Rod Cutting. If anyone could just help me visualize it better and some better idea if not the algorithm or code.

A programmer wants to test whether or not n given conditions are all simultaneously true (e.g he may want to test whether both x>0 and y<z^2, but it is not clear which condition should be tested first. Suppose that it costs Ti units of time to check condition i and that the condition will be true with probability Pi, independent of the outcomes of all other conditions. In which order he should make the test in the best possible manner.

Depends the logical operators you can use.
Lets say you can use only AND.
Then you can have 1 to i logical expressions like this:

Code:

---

E1 AND E2 ... AND Ei

---

If Ei is false then the whole expression is false. Thus it is easier to check the expression Pi which needs the less time.

If you can use also OR then you just have to break the expressions into groups.
For example

Code:

---

(E1 AND E2) OR E3
G1 OR G2
where G1 = E1 AND E2, G2 = E3

---

If either G1 or G2 are true then the whole thing is true. So you will start with the group that has more probabilities to be true. To find that you follow the logic on the first example.

Note that you can have more logical operations, but they can be broken down to AND and ORs and maybe using NOT, in which case you just calculate a new probability as Pi' = 1 - Pi

Makes sense?

If you are wondering what is the use of this take this example.
Each Ei is a very time consuming function that returns a boolean. The minimum to run this function is 1 hour. Now, lets say you know Ti and Pi for each Ei function, since you know the implementation of the function.
You have two options
1) Start evaluating from left to right (or right to left or some other fixed order)
2) Evaluate first how much time it will take and start from the least time consuming expression
Considering that 2) requires a few milliseconds where you can save hours 2) is much preferable.

Quote:

---

Originally Posted by degant7

Guys I'm having trouble solving this question. I gave it a lot of thought but sadly I couldn't come up with a way to go about it. I thought of dynamic programming and specifically Rod Cutting. If anyone could just help me visualize it better and some better idea if not the algorithm or code.

A programmer wants to test whether or not n given conditions are all simultaneously true (e.g he may want to test whether both x>0 and y<z^2, but it is not clear which condition should be tested first. Suppose that it costs Ti units of time to check condition i and that the condition will be true with probability Pi, independent of the outcomes of all other conditions. In which order he should make the test in the best possible manner.

---

Interesting problem! This is the first time I've really had to put my mathematical hat on for these forums.

I think C_ntua is missing the point here - it seems to me that the calculation figuring out the most efficient order is not considered part of the run time. It may be that you have fixed conditions that will form part of a program, and you want to order those conditions in your source code in the most efficient way.

Anyway, I think I know the full solution (not just for the simple version I'll provide to get you started), but I'm having a hard time trying to prove that it is correct. To get started, try a much simpler case. You have two conditions with execution times Ta, Tb respectively and probability of being true Pa, Pb respectively. The key here is that when you test Ca && Cb, you only have to evaluate Cb if Ca turns out to be true, because if Ca is false then you already know Ca && Cb is false. Hence you can calculate the expected runtime of Ca && Cb vs Cb && Ca and compare them. Ca && Cb will take Ta + PaTb. This is because Ca always has to be evaluated, taking time Ta, and Tb has to be evaluated with probability Pa.

UPDATE: I have now proved my solution is correct.