Week 01 Tutorial Answers

• Introductions

  • Introduce yourself to the other people in the tutorial class
  • Discuss what you learned from COMP1511
  • Discuss what parts you're still unsure of

  Answer:

  No answers are available for this question.

New C Syntax

1. Convert the following while loop to a for loop:

   int i = 10;
   while (i >= 0) {
       printf("%d\n", i);
       i--;
   }
   

   Answer:

   for (int i = 10; i >= 0; i--) {
       printf("%d\n", i);
   }
   

2. What while loop is equivalent to the following for statement:

   int ch;
   for (ch = getchar(); ch != EOF; ch = getchar()) {
       putchar(ch);
   }
   

   Answer:

   Two possibilities:

   // the literal translation
   int ch = getchar();
   while (ch != EOF) {
       putchar(ch);
       ch = getchar();
   }
   
   // the common idiom
   int ch;
   while ((ch = getchar()) != EOF) {
       putchar(ch);
   }
   

3. Consider a function to check whether the elements in an array occur in ascending order. Duplicates are allowed in the array, as long as they are adjacent.

   // Input:
   // - a is a valid pointer to the start of an array of ints
   // - n is a positive int indicating how many elements in a[]
   // Output:
   // - returns true if a[i] <= a[i + 1] for all i in [0..n - 2]
   bool isSorted(int *a, int n) {
       ...
   }
   

   Implement this function in two styles:

   1. using COMP1511 C Style
   2. using for, break/return to exit the loop early

   Answer:

   COMP1511 style version:

   bool isSorted(int *a, int n) {
       int sorted = true; // assume ok
       int i = 0;
       while (i < n - 1 && sorted) {
           if (a[i] > a[i + 1]) {
               sorted = false;
           }
           i++;
       }
       return sorted;
   }
   

   For-loop C version

   bool isSorted(int *a, int n) {
   	int sorted = true; // assume ok
   	int i;
   	for (i = 0; i < n - 1 && sorted; i++) {
   		if (a[i] > a[i + 1]) {
   			sorted = false;
   		}
   	}
   	return sorted;
   }
   

   Real-world C version:

   bool isSorted(int *a, int n) {
   	int i;
   	for (i = 0; i < n - 1; i++) {
   		if (a[i] > a[i + 1]) {
   		    return false;
   		}
   	}
   	return true;
   }
   

4. Describe the difference in behaviour (and in the final result) of the following two switch statements:

   // S1 switch (ch) { case 'a': printf("eh? "); break; case 'e': printf("eee "); break; case 'i': printf("eye "); break; case 'o': printf("ohh "); break; case 'u': printf("you "); break; } printf("\n");

   // S2 switch (ch) { case 'a': printf("eh? "); case 'e': printf("eee "); case 'i': printf("eye "); case 'o': printf("ohh "); case 'u': printf("you "); } printf("\n");

   What will be printed for each of the following values for ch: 'u', 'o', 'e'?

   Answer:

   The first switch statement correctly ends each case with a break to ensure that only the code directly associated with that case is executed. The second switch statement does not end each case with break and so execution will fall through from the matching case to all subsequent cases.

   The following output will be produced for the specified cases:

   • ch == 'u' ... S1 prints "you " ... S2 prints "you "
   • ch == 'o' ... S1 prints "ohh " ... S2 prints "ohh you "
   • ch == 'e' ... S1 prints "eee " ... S2 prints "eee eye ohh you "

5. Consider the following function to convert a number in the range 0..6 into a weekday name. 0 returns "Sun", 1 returns "Mon", 2 returns "Tue", and so on.

   char *numToDay(int n) {
   	assert(0 <= n && n <= 6);
   	char *day;
   	if (n == 0) {
   		day = "Sun";
   	} else if (n == 1) {
   		day = "Mon";
   	} else if (n == 2) {
   		day = "Tue";
   	} else if (n == 3) {
   		day = "Wed";
   	} else if (n == 4) {
   		day = "Thu";
   	} else if (n == 5) {
   		day = "Fri";
   	} else if (n == 6) {
   		day = "Sat";
   	}
   	return day;
   }
   

   Suggest at least two alternative and more concise ways of achieving the same result. Include the assert(...) in each case.

   For each function, including the one above, explain what would happen if the assert(...) was removed and the function was invoked via numToDay(7).

   Answer:

   One possibility: use a switch...

   char *numToDay(int n) {
   	assert(0 <= n && n <= 6);
   	char *day;
   	switch (n) {
   		case 0: day = "Sun"; break;
   		case 1: day = "Mon"; break;
   		case 2: day = "Tue"; break;
   		case 3: day = "Wed"; break;
   		case 4: day = "Thu"; break;
   		case 5: day = "Fri"; break;
   		case 6: day = "Sat"; break;
   	}
   	return day;
   }
   

   which could be done more compactly, and with a default, as...

   char *numToDay(int n) {
   	assert(0 <= n && n <= 6);
   	switch (n) {
   		case 0:  return "Sun";
   		case 1:  return "Mon";
   		case 2:  return "Tue";
   		case 3:  return "Wed";
   		case 4:  return "Thu";
   		case 5:  return "Fri";
   		case 6:  return "Sat";
   		default: return "???";
   	}
   }
   

   An alternative would be to use a table lookup...

   char *numToDay(int n) {
   	assert(0 <= n && n <= 6);
   	char *days[7] = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
   	return days[n];
   }
   

6. Give an if statement equivalent to the following switch statement:

   assert(islower(ch));
   switch (ch) {
   	case 'a':
   	case 'e':
   	case 'i':
   	case 'o':
   	case 'u':
   		printf("vowel"); break;
   	default:
   		printf("consonant"); break;
   }
   

   Answer:

   The following if statement behaves the same:

   if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') {
   	printf("vowel");
   } else {
   	printf("consonant");
   }
   

7. Use a conditional expression to replace the if in the following code:

   int ch = getchar();
   
   char *type;
   if (isdigit(ch)) {
       type = "digit";
   } else {
       type = "non-digit";
   }
   
   printf("'%c' is a %s\n", ch, type);
   

   Answer:

   int ch = getchar();
   
   char *type = isdigit(ch) ? "digit" : "non-digit";
   
   printf("'%c' is a %s\n", ch, type);
   

8. Consider the following definitions:

   typedef int Integer;
   
   struct point {
       int x;
       int y;
   };
   typedef struct point Point;
   
   struct node {
       int value;
       struct node *next;
   };
   typedef struct node *Node;
   

   Explain the meaning of each of the typedefs.

   Answer:

   typedef is a keyword which is used to give types alternate names. In the above code:

   • Integer is an alternate name for int, for example the following two lines are equivalent:

     int a = 0;
     Integer a = 0;
     

   • Point is an alternate name for struct point, for example the following two lines are equivalent:

     struct point p = {1, 2};
     Point p = {1, 2};
     

   • Node is an alternate name for struct node *, for example the following two lines are equivalent:

   struct node *curr = NULL;
   Node curr = NULL;
   

Linked List Revision

1. Consider the following two list representations:

   // Representation 1 struct node { int value; struct node *next; }; typedef struct node *List;

   // Representation 2 struct node { int value; struct node *next; }; struct list { struct node *head; }; typedef struct list *List;

   1. Compare the two representations diagramatically.
   2. How is an empty list represented in each case?
   3. Suppose we want to write a function that inserts a number into a list at a given position. What would the function prototype look like for each representation?
   4. What are the advantages of having a separate list struct as in Representation 2?

   Answer:

   1. Representation 1:
      Representation 2:
      
   2. Representation 1: An empty list is simply represented by a NULL pointer.
      Representation 2: An empty list is represented by a pointer to a struct list that contains a NULL pointer in its head field.
      
   3. Representation 1: The function must return a pointer to the first node of the updated list, since the new number could have been inserted in the beginning of the list.
      

      struct node *insert(struct node *list, int num, int pos);
      

      Representation 2: The function does not need to return a value, since the head pointer is hidden behind the struct list pointer, which does not change.
      

      void insert(struct list *list, int num, int pos);
      

   4. Some advantages:
      Functions that modify the list don't need to return the updated list.
      The list struct can be used to store additional information about the list (metadata), which can improve performance. For example, if the list struct contained a field for the length of the list, a function that gets the length of the list could simply return this value instead of iterating through the entire list. If the list struct contained a pointer to the last node of the list (usually called last or tail), then this pointer can be used to easily insert items at the end of the list. The tradeoff is that these fields need to be constantly updated to be consistent with the list.

2. Consider the following simple linked-list representation and a function that sums the values in the list:

   typedef struct node {
   	int value;
   	struct node *next;
   } Node;
   
   typedef Node *List; // pointer to first node
   

   Write a function to sum the values in the list. Implement it first using while and then using for. Finally, implement it using recursion (can leave this for next week).

   Answer:

   Version using while:

   int sumList(List l) {
   	Node *curr = l;
   	int sum = 0;
   	while (curr != NULL) {
   		sum += curr->value;
   		curr = curr->next;
   	}
   	return sum;
   }
   

   Version using for:

   int sumList(List l) {
   	Node *curr;
   	int sum = 0;
   	for (curr = l; curr != NULL; curr = curr->next) {
   		sum += curr->value;
   	}
   	return sum;
   }
   

   Recursive version:

   int sumList(List l) {
   	if (l == NULL) {
   		return 0;
   	} else {
   		return l->value + sumList(l->next);
   	}
   }
   

3. Implement a function to delete the first instance of a value from a list, if it exists. Use the following list representation and prototype:

   struct node {
       int value;
       struct node *next;
   };
   
   struct list {
       struct node *head;
   };
   
   void listDelete(struct list *l, int value);
   

   Answer:

   void listDelete(struct list *l, int value) {
       // list is empty
       if (l->head == NULL) {
           return;
       
       // deleting first value
       } else if (l->head->value == value) {
           struct node *newHead = l->head->next;
           free(l->head);
           l->head = newHead;
       
       // deleting middle value
       } else {
           struct node *curr = l->head;
           while (curr->next != NULL) {
               if (curr->next->value == value) {
                   struct node *toDelete = curr->next;
                   curr->next = toDelete->next;
                   free(toDelete);
                   break;
               }
               curr = curr->next;
           }
       }
   }
   

C Revision

1. Consider a program called myprog which is invoked as:

   ./myprog hello there, 'John Shepherd' > myFile
   

   1. What are the values of argc and argv?
   2. Where would the statement printf("%s", argv[1]); place its output?
   3. Where would the statement ch = getchar(); get its input?

   Answer:

   1. argc has the value 4; argv[0] is "./myprog", argv[1] is "hello", argv[2] is "there,", argv[3] is "John Shepherd"

   2. printf would place its output in the file myFile

   3. getchar() would get its input from the keyboard

2. Consider the following two sets of definitions and statements:

   int x, y;
   char *c, *d, *e, *f;
   
   y = 2;
   x = y;
   d = "abc";
   c = d;
   e = "xyz";
   f = "xyz";
   
   x++;
   *c = 'A';
   

   1. Show the state of the memory after the first set of assignments.
   2. Would anything be different if we had done c = "abc"; d = c;?
   3. Show the state of memory after x++;.
   4. What happens when *c = 'A'; is executed? Why?

   Answer:

   The following diagram shows the memory layout up to *c = 'A';:

   

   Note: Since e and f are assigned string literals which are identical (i.e., contain the same sequence of characters), the compiler may choose to create only one copy of the string and point both e and f to the same string to save space.

   When the program attempts to do *c = 'A';, it generates a segmentation fault. Constant strings (e.g. "xyz") are placed in a read-only area of the memory, and attempting to write into a read-only memory region fails.

Before starting this week's lab, make sure you properly understand the following topics:

• Structs (see videos on structs)
• Pointers (see videos on pointers)
• Malloc (see videos on malloc)
• Linked Lists (see videos on linked lists)