Week 5 Tutorial — Sample Solutions

  1. There are two classes of input for factorials:

  2. Floating point numbers may not be represented exactly because of the limited precision of all computers. Consider for example, the following program: 

    #include <stdio.h>
int main(void) {
   printf("%f\n",    90.1);
   printf("%.15f\n", 90.1);
   return 0;
}

    The output of this program is: 

    90.100000
90.099999999999994

    In the prime function, the square root is computed as a floating-point value, which may not be the exact square root because of the way floating-point numbers numbers are stored. For example, if n==25 then it is possible that sqrt(n) may have the value 4.99999999, depending on the hardware and compiler. If you truncate a float to an int then this can cause a serious problem. The assignment rootn = sqrt(n) will truncate the floating-point number, so rootn will be assigned 4, in which case the function will only check the values 3 and 4 as possible divisors, and will miss 5, which is the only divisor of 25. It will thus incorrectly conclude that 25 is a prime number.

    To be sure that truncation is not masking solutions, an extra loop could be added to make sure that rootn is large enough. In other words:

    int rootn;
rootn = sqrt(n);   // this assignment truncates: does rootn * rootn = n, I wonder
while (rootn * rootn < n) { // extra loop to overcome possible truncation error
   rootn++;
}

    1. The function has 2 bugs:
      • If nwords is 0 then found is undefined.
      • The only time this function returns a correct result is when the word being searched for is the last word in the list.

      One possible fix is: 
      int findWord(char *word, char *wordList[], int nwords) {
   int found = -1; // this is returned if no match
   int i;
   for (i = 0; i < nwords; i++) {
      if (strcmp(wordList[i],word) == 0) {
         found = i;
      }
   }
   return found;
}

    2. An obvious inefficiency is that the function continues to check the words in the list even after it has found a match. Once you know the location of the word, there is no point searching further down the list: 

      // Use a flag to stop the search
int findWord(char *word, char *wordList[], int nwords) {
   int found = -1;
   int i = 0;
   while (i < nwords && found < 0) {
      if (strcmp(wordList[i],word) == 0) {
         found = i;  // found the word
      } else {
         i++;        // not a match, try next
      }
   }
   return found;
}

      Another (advanced) possibility is to check the first letter before calling the function strcmp(): 

      // Possibly avoid calling strcmp() by checking first letter matches
int findWord(char *word, char *wordList[], int nwords) {
   int found = -1;
   int i = 0;
   while (i < nwords && found < 0) {
      if ((*wordList[i] == *word) && (strcmp(wordList[i],word) == 0)) {
         found = i;  // found the word
      } else {
         i++;        // not a match, try next word
      }
   }
   return found;
}

      (NB: If we know the words are alphabetically sorted, then we could also use a more 'sophisticated' algorithm called Binary Search. We will treat that topic later on in the course.)
    1. A possible implementation of strncat(): 

      char *strncat(char *dest, char *source, int n) {
    int i;
    char *d = dest;
    char *s = source;
    while (*d != '\0') {
        d++;
    }
    i = 0;
    while (*s != '\0' && i < n) {
        *d = *s;
        d++;
        s++;
        i++;
    }
    *d = '\0';
    return dest;
}

    2. The classes of input test cases for this problem relate to the lengths of the strings and the value of n. The following would provide a reasonable set of tests:

      char dest[8] char src[8] n Expected Note
      "" "" 0 "" n == length(src)
      "" "abc" 3 "abc" n == length(src)
      "" "abcd" 3 "abc" n < length(src)
      "abc" "" 0 "abc" n == 0
      "abc" "defg" 0 "abc" n == 0
      "abc" "defg" 3 "abcdef" normal case
      "abcd" "efgh" 3 "abcdefg" exactly fills dest
      "abc" "" 2 "abc" error, n > length(src)
      "abcd" "efgh" 4 undefined error, overfills dest

      • In the last testcase, dest is too short and the result is undefined
        • if undefined behaviour is unacceptable, the function could be rewritten to dynamically allocate a new string buffer of the right length (strlen(dest)+n+1). This will ensure no buffer overflows, but changes the way the function would be used (dest does not get modified), and importantly carries the danger of so-called memory leaks (as the caller needs to know that new memory has been allocated in this function and must dispose of this memory when it's no longer needed).