Introduction

This assignment introduces the workshop applets accompanying the Wu textbook and explores the implementation of two basic data structures (arrays and ordered arrays) as well as several related algorithms (for insertion, deletion, and search).

The Workshop Applets can be found in Saka (login required).

Download the lab report template and save as hw21_lastname.doc, substituting your last name. You will save your lab results here; in this case the results will consist of various screenshots as well as answers to questions as indicated below ("Checkpoints")..

Hint:s for the best screenshots:

• make your browser window as small as possible while still able to display the entire applet;
• use Alt-PrintScrn to copy only the active window into the clipboard
• use Paste-Special in MS Word to paste as JPEG -- it will be MUCH smaller than the default BMP.

Ordered Array

1. Run the ordered array app by opening Ordered.html.
2. Follow the instructions on pages 53-56 of the text.
   1. Checkpoint 4: Screenshot after linear search fails (p. 53 ¶ 5)
   2. Checkpoint 5: Q: Explain the difference in how search in an unordered array differs from linear search in an ordered array.
   3. Checkpoint 6: Screenshot during binary search (p. 55 ¶ 3) - show a screen other than the initial or final screen in your search.
3. Create an array with 33 objects, binary search. Fill all of the cells. Make a predication: what is the maximum number of steps (i.e., how many midpoints will be considered) it will take to find a key? Choose a value from one of the cells randomly; step through the 'find' until it is found.
   1. Checkpoint 7: Screenshot of random 'find'
4. Now choose an element that will take the maximum number of tries to find. Show screenshots of second and final "Checking Index" screens (the final one screen *before* it reports "Have found..."
   1. Checkpoint 8: Screenshot of second...
   2. Checkpoint 9: Screenshot of final...
      Q: Was your prediction correct? If so, explain your reasoning; if not, explain your error.
5. Delete any two elements of the 33.
   1. Checkpoint 10: Screenshot after second deletion; "Shifting complete..."
6. Now what is the maximum number of steps it could take to find a key? You may need to experiment a little to find out. Try any random key and watch the process. Based on what you see, choose another key that wil take at least one more step (if possible). Demonstrate a search with this maximum number of steps. Show screenshots of second and final "Checking index" screens.
   1. Checkpoint 11: Screenshot of second...
   2. Checkpoint 12: Screenshot of final...
7. Re-fill the array so that there are 16 elements. Repeat the search process with an array of size 16.
   1. Checkpoint 13: Q: what is the maximum number of steps in a find for an array of size 16?
      Q: what is the maximum number of steps in a find for an array of size 8? size 9? size 7? size 973? size 1066? Explain