Tuesday, February 19, 2008

Algorthm Design

Algorithms is one of my favorite subjects in my life which I love so much. There are many Algortithm design techniques available.It's good for students who have taken computer science as the majors to have a deep knowledge about algorithms and it's various design techniques.

Most of the time when a programming puzzle is given most of the students try to Brute force for the solution.Although this is also a technique to find the solution to the problem,don't resort to it always.Resort to Brute force when you have no other way to solve the problem.And if you are going to brute force you are assured of a solution but the time taken to execute is very large for very big inputs.

There are various algorithm design techniques like Divide and Conquer,Dynamic Programming,Greedy algorithms,Branch and Bound,Linear Programming,Backtracking etc.It's very important to know what each design technique means and try to analyze and compare the various design techniques.To be more confident on these design techniques try to solve the programming problems at www.topcoder.com .

I will give you a simple problem in probability.Try to solve this.I am writing this problem because it cannot be solved using brute force method.Think very smart and different to find the solution.

A redundant storage system can survive a certain number of hard drive failures without losing any data. You are doing some analysis to determine the risk of various numbers of drives failing during one week. Your task is complicated by the fact that the drives in this system have different failure rates. You will be given a double[] containing n elements that describe the probability of each drive failing during a week. Return a double[] containing n + 1 elements, where element i is the probability that exactly i drives will fail during a week. Assume that drive failures are independent events.

Examples

0)

{1.0, 0.25, 0.0}
Returns: {0.0, 0.75, 0.25, 0.0 }
The first drive is guaranteed to fail, the second has a 25% chance of failing, and the third is guaranteed not to fail. So there is a 25% of two failures and a 75% chance of only one failure.
1)

{0.4, 0.7}
Returns: {0.18000000000000002, 0.54, 0.27999999999999997 }
There is a probability of 0.4 x 0.7 = 0.28 that both drives will fail. The chance that only the first will fail is 0.12 and that only the second will fail is 0.42, for a total probability of 0.54 that exactly one drive will fail. This leaves a probability of 0.18 that no drives will fail.
2)

{0.2, 0.3, 0.0, 1.0, 0.8, 0.9}
Returns:
{0.0, 0.011199999999999993, 0.15319999999999995, 0.5031999999999999, 0.2892, 0.0432, 0.0 }

If you could solve the problem,write the code in the comments.
hit counter