Sorting and searching algorithms

2
2
} & \multirow{3}{*}{\includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-04_699_1486_269_366} \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-04_508_1272_462_366} }
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline &
\hline

5 A chairlift for a ski slope has 160 4-person chairs. At any one time half of the chairs are going up and half are coming down empty. An observer watches the loading of the chairs during a moderately busy period, and concludes that the number of occupants per 'up' chair has the following probability distribution.

1. Give a rule for using 1-digit random numbers to simulate the number of occupants of an up chair in a moderately busy period.
2. Use the 10 random digits provided to simulate the number of occupants in 10 up chairs. The observer estimates that, at all times, on average \(20 \%\) of chairlift users are children.
3. Give an efficient rule for using 1-digit random numbers to simulate whether an occupant of an up chair is a child or an adult.
4. Use the random digits provided to simulate how many of the occupants of the 10 up chairs are children, and how many are adults. There are more random digits than you will need.
5. Use your results from part (iv) to estimate how many children and how many adults are on the chairlift (ie on the 80 up chairs) at any instant during a moderately busy period. In a very busy period the number of occupants of an up chair has the following probability distribution.

   number of occupants	0	1	2	3	4
   probability	\(\frac { 1 } { 13 }\)	\(\frac { 1 } { 13 }\)	\(\frac { 3 } { 13 }\)	\(\frac { 3 } { 13 }\)	\(\frac { 5 } { 13 }\)

6. Give an efficient rule for using 2-digit random numbers to simulate the number of occupants of an up chair in a very busy period.
7. Use the 2-digit random numbers provided to simulate the number of occupants in 5 up chairs. There are more random numbers provided than you will need.
8. Simulate how many of the occupants of the 5 up chairs are children and how many are adults, and thus estimate how many children and how many adults are on the chairlift at any instant during a very busy period.
9. Discuss the relative merits of simulating using a sample of 10 chairs as against simulating using a sample of 5 chairs.

3 John has a standard die in his pocket (ie a cube with its six faces labelled from 1 to 6).

1. Describe how John can use the die to obtain realisations of the random variable \(X\), defined below.

   \(x\)	1	2	3
   \(\operatorname { Probability } ( X = x )\)	\(\frac { 1 } { 2 }\)	\(\frac { 1 } { 6 }\)	\(\frac { 1 } { 3 }\)

2. Describe how John can use the die to obtain realisations of the random variable \(Y\), defined below.

   \(y\)	1	2	3
   \(\operatorname { Probability } ( Y = y )\)	\(\frac { 1 } { 2 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 1 } { 4 }\)

3. John attempts to use the die to obtain a realisation of a uniformly distributed 2-digit random number. He throws the die 20 times. Each time he records one less than the number showing. He then adds together his 20 recorded numbers. Criticise John's methodology.

2. $$\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}$$ The numbers represent the sizes, in megabytes (MB), of eight files.
The files are to be stored on 50 MB discs.

1. Calculate a lower bound for the number of discs needed to store all eight files.
2. Use the first-fit bin packing algorithm to fit the files onto the discs.
3. Perform a bubble sort on the numbers in the list to sort them into descending order. You need only write down the final result of each pass.
4. Use the first-fit decreasing bin packing algorithm to fit the files onto the discs.

5.

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 20.
2. The list of numbers is to be sorted into descending order. Use a bubble sort to obtain the sorted list, giving the state of the list after each complete pass.
3. Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 20.
4. Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.

1. \(\begin{array} { l l l l l l l l l } 29 & 52 & 73 & 87 & 74 & 47 & 38 & 61 & 41 \end{array}\) The numbers in the list represent the lengths in minutes of nine radio programmes. They are to be recorded onto tapes which each store up to 100 minutes of programmes.

1. Obtain a lower bound for the number of tapes needed to store the nine programmes.
2. Use the first-fit bin packing algorithm to fit the programmes onto the tapes.
3. Use the first-fit decreasing bin packing algorithm to fit the programmes onto the tapes.