Use the Step button to execute the algorithm two or three times until you understand exactly how the algorithm works and how the animation corresponds to the steps in the pseudocode window. Remember to click Reset when you are ready to start over with a new set of data.
1. How many positions does the location marker achieve?
Observe that with the eight pieces of data, there are always seven passes through the loop (n - 1) if there were n pieces of data). However, the number of positions that the location marker takes on (Step 7) depends on the relative order of the data. You will now make use of the animator to explore this dependence in more depth. Using the step mode, gather data from 10 executions of the algorithm and enter the results on the Worksheet. For each data set, copy down the entire data set and keep up with the position of the location marker and the data value at that position each time the location marker moves. For example, if the data set were 20, 15, 25, 30, 42, 18, 72, 11, then you would copy the entire list as the data set. The original position of the location marker would be position 1, and the value at that position is 20. Therefore, you would enter 1 for the location and 20 for the value. When the location marker moves, list the location number that the marker moves to and the data value there.
Continue until the algorithm terminates. Once you are sure of how this works, it is fine just to click Reset and copy the relevant data down without stepping through the entire execution (just be sure that you know what will happen).
2. Determining the values at the location marker by scanning
Look at the data obtained. Notice that the values stored at the positions taken on by the location marker form a subsequence of the original data set; that is, the values of the subset are taken from the original set in the same relative order as in the original set. On the Worksheet, explain in your own words how to scan the list from left to right and pick out the values that will be in this subsequence.
3. Smallest number of positions for the location marker
What would be the smallest number of positions that location marker could possibly point to during the execution of the algorithm? Describe the special conditions under which this would happen. Approximately how often would you expect this to occur? Put your answers on the Worksheet.
Lab 3: Search for the Largest Value
4. Largest number of positions for the location marker
What would be the largest number of positions that the location marker could possibly point to during the execution of the algorithm? Describe the conditions under which this would happen. Approximately how often would you expect this to occur? Put your answers on the Worksheet.
5. Likelihood of many positions for the location marker
How would you compare the likelihood that the location marker would point to three different positions with the likelihood that the location marker would point to seven different positions? Would you expect the likelihood that the location marker points to three different positions to be much smaller, about the same, or much larger than the likelihood that it would point to seven different positions?
1. How many positions does the location marker achieve?
Data Set 1: Data Set 6: Positions: Positions: Values: Values:
Data Set 2: Data Set 7: Positions: Positions: Values: Values:
Data Set 3: Data Set 8: Positions: Positions: Values: Values:
Data Set 4: Data Set 9: Positions: Positions: Values: Values:
Data Set 5: Data Set 10: Positions: Positions: Values: Values:
2. Determining the values at the location marker by scanning
Explanation for finding subsequence:
3. Smallest number of positions for the location marker
Smallest number of positions for the location marker:
Special conditions for this to occur: How frequently would this occur?
4. Largest number of positions for the location marker
Largest number of positions for the location marker:
Special conditions for this to occur: How frequently would this occur?
5. Likelihood of many positions for the location marker
How likely is it that the location marker will point to three different positions compared to seven different positions:
[ ] much smaller
[ ] about the same
[ ] much larger