Week 02 Tutorial Questions

GCC & Makefiles

1. (Compiling)

   What does each of these gcc options do:

   1. -E
   2. -c
   3. -o
   4. -g
   5. -O3

2. (Compiling)

   Consider the following Makefile:

   tw: tw.o Dict.o stemmer.o
   tw.o: tw.c Dict.h WFreq.h stemmer.h
   Dict.o: Dict.c Dict.h WFreq.h 
   stemmer.o: stemmer.c stemmer.h
   

   If none of the *.o files exist, explain how make decides which (implicit) rules to apply.

3. (Compiling)

   At the beginning and end of header files, we typically place the following:

   #ifndef X_H
   #define X_H
   // ... rest of X.h file ...
   #endif
   

   Explain the purpose of this and how it achieves this purpose.

Recursion

For the linked list questions below, use the following data type definitions:

typedef struct node {
	int data;
	struct node *next;
} Node;

typedef Node *List;

1. (Recursion)

   Write both iterative and recursive functions to compute the length of a linked list. Both functions should have the same interface:

   int listLength(List l) { ... }
   

2. (Recursion)

   Write both iterative and recursive functions to count the number of odd numbers in a linked list. Both functions should have the same interface:

   int listCountOdds(List l) { ... }
   

3. (Recursion)

   Write both iterative and recursive functions to check whether a list is sorted in ascending order. Both functions should have the same interface:

   bool listIsSorted(List l) { ... }
   

4. (Recursion)

   Write a recursive function to delete the first instance of a value from a linked list, if it exists. The function should return a pointer to the beginning of the updated list. Use the following interface:

   List listDelete(List l, int value) { ... }
   

5. (Recursion)

   Write a recursive function to delete all the even numbers from a linked list. The function should return a pointer to the beginning of the updated list. Use the following interface:

   List listDeleteEvens(List l) { ... }
   

6. (Recursion)

   Analyse the behaviour of the following function, which returns the n^th Fibonacci number:

   int fib(int n) {
   	if (n == 0) return 0;
   	if (n == 1) return 1;
   	return fib(n - 1) + fib(n - 2);
   }
   

   Examine how it computes fib(2), fib(4), fib(6). Is this method feasible for larger values of n?

7. (Recursion)

   Consider the problem of computing \( x^n \) for two integers \( x \) and \( n \), where \( n \) is non-negative. Since the result of this grows very large, even for moderate values of \( n \), assume that we are not worried about overflows.

   The standard iterative solution to this is \( O(n) \):

   int pow(int x, unsigned int n) {
   	int res = 1;
   	for (int i = 1; i <= n; i++) {
   		res = res * x;
   	}
   	return res;
   }
   

   It is possible to write a recursive solution to this which is \( O(\log n) \). Write one.