CSE 143
 Miniquiz 11                                                         Name:
 11/21/2002                                                           Section:
 Time : 16 minutes
 
Question 1:

Consider a sorted integer array, A, of size 3000. Given a number x, we want to
find whether the number is present in the array.  Binary search is used. Find
the number times the algorithm will compare x to an element of the array in
order to determine the answer (worst case).




Question 2:

Consider the following diagram, which depicts the state of an array at various
stages as it is being sorted using Insertion Sort.
 (Even without having a definition of "stage", you should be able to determine
from the data shown what "stage" means for this problem).
 Fill out the state of the array at stage 4.

Stage 0:  (initial state)
13
 18
 12
 11
 15
 24
 23
 30

Stage 1:
13
 18
 12
 11
 15
 24
 23
 30

Stage 2:
12
 13
 18
 11
 15
 24
 23
 30

Stage 3:
11
 12
 13
 18
 15
 24
 23
 30

Stage 4: (fill in)
   
    
    
    
    
    
    
    


Question 3:

Assume that A[0..size-1] is an array of integers which is sorted in ascending order. A and size are instance variables.
We want a method to place an additional value in the correct location so that modified array is sorted in positions 0..size.
Also, assume that size>=1, and A.length>=size.

a. Label each of the following as PRE-condition, POST-condition, BOTH, or NEITHER.  The above spec is informal; make reasonable assumptions based on what you know about sorting and about this algorithm in particular (hint: this could be a helper method for Insertion Sort).

    1.  A[0..size-2] is sorted

    2. A[0..size-1] is sorted

    3. A[0..size] is sorted

    4. A[0..size+1] is sorted

    5. if x is one of the values in A[0..size-1] before the method was called, then x is one of the values in A[0..size] after the method is called.

    6. if y is one of the values in A[0..size] after the method was called, then y was one of the values in A[0..size-1] before the method was called.

b. Now, study the following partly completed method.  Then fill in the blanks so the method correctly implements the above specification.  Make no other changes.

void insertInteger(int newVal) {
  int currentPos;
  currentPos=______________;      
  while (currentPos  >= 0   && A[currentPos] ___ newVal)
  {
    A[currentPos+1]=A[currentPos];   
    currentPos--;
  }
 A[________________]=newVal;
 size++;
}