Homework 1 Solution

CS 23

30 pts., due Feb. 14

Write C++ functions to solve each of the following problems. Use pre- and post-conditions for documentation. Construct a loop invariant for each loop.

1. Factorial of n.

   // Pre-Condition: n is a non-negative integer.
   // Post-Condition: The factorial of n is returned.
   
   int fact(int n)
   {
      int i;
      int prod = 1;
   
      // Invariant: prod = 1 * 2 * ... * (i - 1)
      for (i = 2; i <= n; ++i)
         prod *= i;
   
      return prod;
   }
   

2. Determining the smallest value among n integers.

   // Pre-Condition: data is an integer array of n elements.
   // Post-Condition: Returns the smallest value in data.
   
   int min(int data[], int n)
   {
      int index = 0;
      int i;
   
      // Invariant: data[index] = smallest(data[0]...data[i - 1])
      for (i = 1; i < n; ++i)
         if (data[i] < data[index])
            index = i;
   
      return data[index];
   }
   

3. Bubble sort of n integers.

   // Pre-Condition: data is an integer array of n elements.
   // Post-Condition: data is sorted into ascending order.
   
   void sort(int data[], int n)
   {
      int i;
      int j;
      int sorted = 0;
   
      // Invariant: The elements in data[i + 1]...data[n - 1] are the
      // largest elements in the array and are sorted in ascending order.
      for (i = n - 1; !sorted && i > 0; --i)
      {
         sorted = 1;
   
         // Invariant: The largest element of data[0]...data[j] is in
         // data[j].
         for (j = 0; j < i; ++j)
            if (data[j] > data[j + 1])
            {
               sorted = 0;
               swap(data[j], data[j+1]);
            }
      }
   }
   
   // Pre-Condition: i and j are integers.
   // Post-Condition: i's and j's values are exchanged.
   
   void swap(int &i, int &j)
   {
      int temp = i;
   
      i = j;
      j = temp;
   }
   

4. Determining the second smallest value among n integers.

   // Pre-Condition: data is an integer array of n elements.  Each of the
   // n values is unique.
   // Post-Condition: The second smallest value of data is returned.
   
   int secSmall(int data[], int n)
   {
      int i;
      int small;
      int sec;
   
      small = min(data, n);
   
      if (data[0] == small)
         sec = 1;
      else
         sec = 0;
   
      // Invariant: data[sec] is the smallest item in data[0]...data[i-1]
      // which is not smallest item in the entire array.  (I.e., it is the
      // second smallest item.
      for (i = 0; i < n; ++i)
         if (data[i] != small && data[i] < data[sec])
            sec = i;
   
      return data[sec];
   }