# 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...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...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 == small)
sec = 1;
else
sec = 0;

// Invariant: data[sec] is the smallest item in data...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];
}
```

Thomas P. Kelliher
Fri Feb 21 10:54:26 EST 1997
Tom Kelliher