EX1.

  1. Simulate the method SelectionSort, defined below on an array containing the elements.
    1. 6,8,14,17,23
    2. 17,23,14,6,8
    3. 23,17,14,8,6

    How many comparisons and swaps of elements are made in each case?

    void SelectionSort (int A[]) {

    for (int i = 0 ; i<A.length; i++){

    small = i ;

    for (int j = i+1; j < n; j++)

    if (A[j] < A[small])

    small = j ;

    int temp = A[small];

    A[small] = A[i];

    A[i] = temp;

    }

    }

     

  2. What are the minimum and maximum number of (a) comparisons and (b) swaps that SelectionSort can make in sorting a sequence of n elements?
  3. What does SelectionSort do if al elements are the same?
  4. Use S(Sigma) and P(Pi) notation to express the following.
    1. The sum of the odd integers from 1 to 377
    2. The sum of the squares of the even integers from 2 to n (assume that n is even)
    3. The product of the powers of 2 from 8 to 2k
  5. Show the following formulas by induction on n starting at n = 1.
  6. Identify the parity of each of the following bit sequences as even or odd:
    1. 01101
    2. 111000111
    3. 010101
  7. Prove that the ripple-carry addition algorithm produces the correct answer. Hint: Show by induction on i that after considering the first i places from the right end, the sum of the tails of length i for the two addends equals the number whose binary representation is the carry bit followed by the i bits of answer generated so far.
  8. Give an example of a binary operator that is commutative but not associative.
  9. Give an example of a binary operator that is associative but not commutative.
  10. Show the every negative integer can be written in the form 2a+3b for some (not necessarily positive) integers a and b.