Homework 1
Document last modified: 

  1. Text 2.1-3.
    From text:

    Consider the searching problem:

    Input: A sequence of n numbers A=<a1,a2,...,an> and a value v.

    Output: An index i such that v=A[i] or the special value NIL if v does not appear in A.

    Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure your loop invariant fulfills the three necessary properties.

    Use the following simplification, that is where v is in A or in logic notation:

         $i where 0£i<A.length, v==A[i]

    class LinearSearch {

    //@ pre A != null;
    //@ pre (\exists int i;     0 <= i && i < A.length;    A[i] == v);
    //@ post A[\result]==v;

        int linearsearch(int A[], int v) {

             int i = 0;

             while(A[i] != v)
                  i = i + 1;
             return i;
        }
    }

    Consider the loop condition and the loop invariant. The loop condition is:

        while( A[i] != v )

    The loop invariant must state that is true before, during and after the loop execution. To be useful, the loop invariant must also produce the desired result, in this case, determining the index i where A[i] == v.

    The loop invariant must then define the elements of array A that v is not equal to, similar to the loop condition. The key insight is that A[i]!=v for all indices less than i.

    a. State the loop invariant in English using the terms from the text of the three properties: initialization, maintenance and termination. This is not a formal proof but should provide sufficient details to convince the reader of its validity.

    Initialization: The invariant property must hold in the state just before the first test of the while condition.

    Maintenance: The invariant property must hold in the state at the very end of the sequence of statements in the loop body.

    Termination: When the loop terminates, the invariant gives a useful property that helps show the algorithm is correct.

    b. Write the loop invariant and validate using ESCjava.

     

  2. Complete the Java program to add values at corresponding indices of two int arrays; A[0]+B[0], A[1]+B[1], .... You'll need to state preconditions and loop-invariant. Reasonable preconditions are that A and B are the same length. Validate using ESCjava.

     

    class Add {
    //@ post (\forall int i;   0 <= i && i < A.length;   \result[i] == A[i]+B[i]);

       int[] add(int A[], int B[]) {

     

  3. Text 2.2-2.
    From text:

    Consider sorting n number stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A and exchange it with A[2]. Continue in this manner for the first n-1 elements of A. Write pseudocode for this algorithm, which is known as the selection sort. What loop invariant does the algorithm maintain? Why does it need to run for only the first n-1 elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in Q-notation.
    1. Define a Java algorithm that returns a reference to the sorted array.
    2. Validate using ESCjava. Give preconditions, postconditions and loop invariants for each of the two loops.
    3. Test using the following or similar.
      public class SelectionSortEx {

        public static void main(String a[]) {
          double A[]={2,4,5,7,1,2,3,6};
          double B[]=(new SelectionSort()).selectionsort(A);
          for(int i=0;i<B.length;i++) System.out.println(B[i]);
        }
      }
    4. Give the best and worst case running times in Q-notation. Justify your answers.

Turn in

  1. Cover sheet with your name, C455, date, and Homework 1.
  2. Typed answer to Question 1a and 3d.
  3. Print out of LinearSearch, Add and selection sort.
  4. Print out of validation results for LinearSearch, Add and selection sort using ESCjava.
  5. Execution results of Question 3c.