Math Statistics

posted by .

The sorting algorithm known as bogosort can be described in pseudocode as:

while not isSorted(input):
shuffle(input)


If we feed bogosort a shuffled array of length n of unique items the distribution of the number of times
bogosort checks if the array is sorted (henceforth called `an iteration') is Geo( 1/n! ).

(a) What is the expected number of iterations it will take bogosort to run for an array of k unique
values?

(b) When writing this question I ran bogosort many times. I wanted to nd a case where I was using
an array of 5 items and it took bogosort more than 500 iterations to sort the array. What is the
probability that if I run bogosort on an array of 5 items that bogosort will take more than 500
iterations to sort it? (Write out the sum you would need to evaluate and evaluate the sum. Write
the answer to 4 decimal places)

(c) When feeding in a shued array of 3 unique values into bogosort the probability that it takes less
than or equal to 2 iterations to sort the array is 11/36. If I use bogosort to sort 20 random arrays
each with 3 unique values - What is the distribution of the number of arrays it takes less than or
equal to 2 iterations to sort?

(d) What is the probability that for the same situation as in the previous part that exactly 2 out of the
20 arrays took less than or equal to 2 iterations to sort?

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. Computer Programming

    I was wondering if someone could review my pseudocode to see if I got this right. Here is the question: Input a list of employee names and salaries, and dtermine the mean (average) salary as well as the number of salaries above and …
  2. Intro to Computer Programming - Pseudocode

    This assignment (below) jumped way ahead of my abilities compared to the last assignment. I think I need a parallel array or a 2D array, an accumulator or loop counter, a verification of input, and Boolean something. But I'm not sure …
  3. computers

    The recursive algorithm of the 4th Section of the chapter "Computational Geometry" employs a trick of presorting, in which we maintain two arrays X and Y of the input points P sorted on coordinate x and y, respectively. The algorithm …
  4. pseudocode programming

    Develop an algorithm or write pseudocode to determine if a citizen is eligible to vote. The criteria for eligibility are that the citizen must be 18 or older and must not be a convicted felon. The algorithm must continuously accept …
  5. Ms Visio

    • 2. Construct a data dictionary and draw a hierarchy chart and flowchart or pseudocode for a program to calculate commissions. Output. Output is the commission report shown in the spacing chart that follows. At most, 50 detail lines …
  6. Simple Array Process

    need help with this generate only the pseudocode. No charting is required, but you will have to incorporate the bubble sort algorithm to ensure the selling prices are in order so you can determine the median selling price. Do not assume …
  7. Fundamental of computer science

    Pseudocode CountPositive integer totalPos,number Begin loop Input numbers If number>0 then totalPos<-totalPos +1 Loop while number<>0 Print totalPos Convert the above Pseudocode into a pascal program.
  8. programming

    Consider the following input and output: INPUT: (((5 + 1) – (7 – 4)) / (11 – 8)) OUTPUT: 5 1 + 7 4 – – 11 8 - / 2.1. What variables do you need to consider for the input?
  9. Program

    Write a pseudocode and algorithm that to else the user to input 10 numbers in program we display the largest number
  10. pseudo code algorithm

    Write a pseudo code algorithm which: • Determines the average weight of a person over a particular year. • For each month, your algorithm should input the person's weight for that month (a positive real number). Your algorithm …

More Similar Questions