Average Case Flashcards
What is the intuition behind average case algorithms?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/382/412/a_image_thumb.png?1553799513)
What is the definition of Expectation of variable T?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/382/549/a_image_thumb.png?1553799694)
Find the expectation of T for the following:
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/382/884/q_image_thumb.png?1553799878)
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/382/884/a_image_thumb.png?1553799951)
Find the expactation of the following:
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/384/193/q_image_thumb.png?1553799978)
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/384/193/a_image_thumb.png?1553800076)
What is a Randomized Algorithm?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/386/349/a_image_thumb.png?1553800115)
What is the randomized algorithm type: Las Vegas?
What is an example of this algorithm?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/386/431/a_image_thumb.png?1553800362)
What is the randomised algorithm type; Monte Carlo?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/386/660/a_image_thumb.png?1553800397)
What are the advantages/disadvantages of randomized algorithms in general?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/386/764/a_image_thumb.png?1553800687)
What are the advantages/disadvantages of Las Vegas algorithms?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/387/231/a_image_thumb.png?1553800715)
What are the advantages/disadvantages of Monte Carlo algorithms?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/387/270/a_image_thumb.png?1553800739)
Why does it make more sense to think about expected time instead of worst-case time for Las Vegas algorithms?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/387/298/a_image_thumb.png?1553800823)
How would you use a Monte Carlo algo to approximate the value of Pi using only addition, multiplation, and division?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/928/437/a_image_thumb.png?1554232126)
What would the code look like for the following Algo?
What would the run time be?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/928/584/q_image_thumb.png?1554232156)
![](https://s3.amazonaws.com/brainscape-prod/system/cm/272/928/584/a_image_thumb.png?1554232180)