[Show with no answers]   [Show with all answers]

1. Class introduction (for everyone, starting with the tutor):

   • introduce yourself to the other people in the tute class
   • discuss what you learned from COMP1511
   • discuss what parts you're still unsure of
   • choose lab partners (who you'll work with until week 5)

   [show answer]

   There is no "correct" answer for this exercise.

   (Unless your tutor asks you what is your favourite beer, in which case the Correct Answer is any of BrewDog's "Sink The Bismarck" or Moon Dog Brewing's "Jumping the Shark 2013" or Ballast Point Brewing's "Grapefruit Sculpin". A Very Wrong answer to the question is VB or Toohey's New or Corona or Heineken or Peroni.)

2. Consider the following program (adapted from Sedgewick):

   #include <stdlib.h>
   #include <stdio.h>
   #include <assert.h>
    
   int main(int argc, char *argv[])
   {
   	int i, j, *a;
   	int N = 0;
    
   	// initialisation
   	assert(argc > 1);
   	sscanf(argv[1], "%d", &N);
   	assert(N > 0);
   	a = malloc(N*sizeof(int));
   	assert(a != NULL);
   	for (i = 2; i < N; i++) a[i] = 1;
    
   	// computation
   	for (i = 2; i < N; i++) {
   		if (a[i]) {
   			for (j = i; i*j < N; j++) a[i*j] = 0;
   		}
   	}
    
   	// results
   	for (i = 2; i < N; i++) {
   		if (a[i]) printf("%d\n",i);
   	}
   	exit(EXIT_SUCCESS);
   }
    

   Try to answer each of the following questions about this program:

   1. there are no braces around the bodies of some for loops; does this matter?
   2. what is the line of code sscanf(argv[1],"%d",&N); doing?
   3. suggest an alternative for the sscanf(...) statement?
   4. for each of the asserts ...
      • describe what error is being checked for and why
      • suggest a better error message than what you get from assert
   5. what are the values of a[0] and a[1] during execution?
   6. why don't the values of a[0] and a[1] matter?
   7. what is the purpose of this program?

   [show answer]

   1. No, it doesn't matter. If a C control structure (if, else, while, for) has a "body" which is a single statement, braces are not required. An alternative way of stating this is that all of the above control structures have a "body" which is a single statement and braces {...} are a grouping mechanism that allows a collection of statements to be treated as a single statement.

   2. The sscanf allows you to apply scanf-style extraction of data values from a string instead of a file. This particular sscanf is converting the first command-line argument (argv[1]) into an integer value (%d) and storing this value in the variable N.

   3. The following would produce a similar effect to the sscanf:

      N = atoi(argv[0]);

      To find whether there are any subtle differences, take a look at the man entries for sscanf() and atoi().

   4. assert(argc > 1) ...

      • this is checking whether there are at least two elements on the command-line; we need to ensure that a value for N has been supplied available as the first command-line argument (the first element on the command-line is always the name of the command
      • a better error message here might be a usage message such as

        Usage: a.out Number,  where Number is positive

      assert(N > 0) ...

      • this is checking that the numerical value of the command line argument (now N) is positive; since this value is being used to allocate an array of size N, it doesn't make sense to have a negative size
      • the above usage message would also be suitable here

      assert(a != NULL) ...

      • this is checking that memory space was successfully allocated for the array; since N can be arbitrarily large (up to 2³¹-1), it is possible that a request could be made for such a large array that malloc() cannot allocate the space
      • several possible messages might be suitable, but not necessarily useful for users

        Cannot allocate space for array // but maybe not meaningful to a user
        Max number is too large // but this is not the only possible reason why malloc() might fail

   5. The array elements a[0] and a[1] are never assigned a value, so they contain random rubbish.

   6. Since a[0] and a[1] are never accessed during the execution (check the for loops), it doesn't matter what their values are.

   7. The program implements the "Sieve of Eratosthenes", a very old algorithm for determining prime numbers. It does this by using an array to hold a true/false value for each of the first N integers; if a[i] is true, this means that i is a prime number. The algorithm sets up this array by first assuming that all of the numbers from 2..N are prime. It then makes multiple scans through the array, "eliminating" as potential prime numbers, any numbers which are multiples of smaller numbers.

3. A C program has several means of interacting with its run-time environment. Describe what each of the following is and what it is used for: argc, argv, stdin, stdout, stderr, exit().

   [show answer]

   1. argc: is an integer argument to the main() function that indicates how many arguments were typed on the command line that invoked the program. Since it includes the name of the command, it always has a value that is at least 1.

   2. argv: is an array of strings, argument to the main() function that contains the strings for the arguments that were typed on the command line that invoked the program. argv[0] is always the name of the executable file of the program.

   3. stdin: is an input stream (type FILE *) that is open when the program starts and can be used to read program input. By default, it is connected to the keyboard, but can be redirected to come from a file.

   4. stdout: is an output stream (type FILE *) that is open when the program starts and can be used as a destination for program output. By default, it is connected to the screen, but can be redirected so that the output is sent to a file.

   5. stderr: is an output stream (type FILE *) that is open when the program starts and can be used as a destination for program output. By default, it is connected to the screen, but can be redirected so that the output is sent to a file. Note that redirection of stderr and stdout are independent, so you can redirect one without redirecting the other.

   6. exit(): is a function that can be called to terminate execution of the program. It takes a single integer argument which is used as the exit status of the program. The exit status can be used by the program's environment to determine whether the program completed successfully (exit status of zero) or whether there was an error (exit status non-zero).

4. 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?

   [show 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

5. Which of the following statements are equivalent? Which are incorrect? Assume that x is an int variable.

   1. scanf("%d", x);

   2. scanf("%d", &x);

   3. printf("%d", x);

   4. fscanf(stdin, "%d", &x);

   5. fscanf(stderr, "%d", &x);

   6. fprintf(stdout, "%d", x);

   7. fprintf(stderr, "%d", x);

   [show answer]

   (b) and (d) are equivalent. (c) and (f) are equivalent. (g) would have the same effect as (c) and (f) if none of the output streams have been redirected. (a) is incorrect (passing int value rather than int *). (e) is incorrect (can't read from an output stream).

6. Define a swap() function that exchanges two elements in an array.

   For an array a[] and two indexes i and j, we could exchange the i'th and j'th elements by the call:

   swap(a, i, j)
   

   [show answer]

   The function is defined as:

   void swap(int a[], int i, int j)
   {
   	int tmp;
   	tmp = a[i];
   	a[i] = a[j];
   	a[j] = tmp;
   }

   It would also be possible to define it using the C pre-processor:

   #define	swap(a,i,j) \
   	({ int tmp; tmp = a[i]; a[i] = a[j]; a[j] = tmp; })

   Using the macro would result in (slightly) more efficient run-time. Only useful if we were doing a very large amount of swapping.

7. 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.

   [show answer]

   Version using while:

   int sumOfList(List L)
   {
   	Node *cur = L;
   	int sum = 0;
   	while (cur != NULL) {
   		sum += cur->value;
   		cur = cur->next;
   	}
   	return sum;
   }

   Version using for:

   int sumOfList(List L)
   {
   	Node *cur;
   	int sum = 0;
   	for (cur = L; cur != NULL; cur = cur->next) {
   		sum += cur->value;
   	}
   	return sum;
   }

   Recursive version:

   int sumOfList(List L)
   {
   	if (L == NULL)
   		return 0;
   	else
   		return L->value + sum(L->next);
   }

8. Important: Make sure you can properly understand and effectively use the following topics (covered in COMP1511). In case you have any questions, please discuss them with your tutor.

   • Structs (see videos on Structs)
   • Pointers (see videos on Pointers)
   • Malloc (see videos on Malloc)
   • Linked Lists (see videos on Linked Lists)