Term
| Define 'probabilistic analysis' |
|
Definition
| Probabilistic analysis is the use of probability in the analysis of problems. |
|
|
Term
| When is probabilistic analysis useful? |
|
Definition
| It's useful in analyzing the running time of an algorithm. Specifically the 'average-case' running time for our purposes. |
|
|
Term
| How are we using probabilistic analysis to find the 'average-case' running time? Give a brief overview. |
|
Definition
| We take the average over the distribution of the possible inputs (obtained from through previous knowledge and/or assumptions made). Basically, we're averaging the running time over all the possible inputs. |
|
|
Term
| What do we need to know about the inputs in order to perform probabilistic analysis on the data? |
|
Definition
| "We must use knowledge of, or make assumptions about, the distribution of inputs." If we don't have a reasonable input distribution we cannot use probabilistic analysis. |
|
|
Term
| When can we not use probabilistic analysis??????? Provide examples. |
|
Definition
| If we don't have a reasonable input distribution we cannot use probabilistic analysis. For example...??? |
|
|
Term
| What is a reasonable input distribution for probabilistic analysis?????? |
|
Definition
Don't know how to define one really
In the book the 'hiring problem'
input properties: |
|
|
