Week 02 Tutorial Answers

GCC, Makefiles, Recursion

GCC & Makefiles

(Compiling)

What does each of these gcc options do:
1. -E
2. -c
3. -o
4. -g
5. -O3
Answer:
1. -E runs a *.c file through the pre-processor and shows the result on stdout
2. -c compiles a *.c file to a relocatable *.o file
3. -o specifies the name of the result file for some gcc step
4. -g incorporates information into a *.o for the debugger
5. -O3 compiles using the optimizer to make the machine code more efficient
(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.
Answer:
The make command starts by deciding on a top-level target. In this case, it will be tw, since this is the first target in the file. In order to make tw it needs the source files that tw relies on to exist. These sources are tw.o Dict.o stemmer.o. Since none of these exist, they need to be created, and so we consider each of them as targets and look for rules to create them.

For tw.o, the sources are tw.c Dict.h WFreq.h stemmer.h. They have no rules in which they are targets, so we consider them in turn and check whether their file update time is more recent than tw.o. If any of them are, we trigger the action for creating tw.o, which would be gcc -c tw.c.

We could create Dict.o and stemmer.o using similar reasoning. Once we have all the sources for target tw, we trigger the action for creating it, which would be:
```
gcc -o tw tw.o Dict.o stemmer.o
```
(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.

Answer:

The purpose is to prevent duplicate definition errors if the X.h file is included twice in a single compilation step. This typically occurs because some A.c includes Y.h, which includes X.h and then A.c also includes X.h directly.

The first time X.h is included, the symbol X_H is not defined, and so the #ifndef test succeeds, and the rest of the X.h file is included in the compilation. One action in this is to define the X_h symbol. If the file is included again in the same compilation, the X_H symbol is already defined, the #ifndef test fails, and the rest of the X.h file is ignored.

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;

(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) { ... }

Answer:

Iterative version:

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

Recursive version:

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

(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) { ... }

Answer:

Iterative version:

int listCountOdds(List l) {
	int count = 0;
	for (Node *curr = l; curr != NULL; curr = curr->next) {
		if (curr->data % 2 != 0) {
			count++;
		}
	}
	return count;
}

Recursive version:

int listCountOdds(List l) {
	if (l == NULL) {
		return 0;
	} else if (l->data % 2 != 0) {
		return 1 + listCountOdds(l->next);
	} else {
		return listCountOdds(l->next);
	}
}

(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) { ... }

Answer:

Iterative version:

bool listIsSorted(List l) {
	if (l == NULL) {
		return true;
	}
	
	for (Node *curr = l; curr->next != NULL; curr = curr->next) {
		if (curr->data > curr->next->data) {
			return false;
		}
	}
	return true;
}

Recursive version:

bool listIsSorted(List l) {
	// an empty list is sorted
	if (l == NULL) {
		return true;
	
	// a list with one item is sorted
	} else if (l->next == NULL) {
		return true;
	
	// if first item is greater than second item, list is not sorted
	} else if (l->data > l->next->data) {
		return false;
	
	// check whether rest of the list is sorted
	} else {
		return listIsSorted(l->next);
	}
}

(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) { ... }

Answer:

Without freeing the deleted node:

List listDelete(List l, int value) {
	if (l == NULL) {
		return NULL;
	} else if (l->data == value) {
		return l->next;
	} else {
		l->next = listDelete(l->next, value);
		return l;
	}
}

Including freeing the deleted node:

List listDelete(List l, int value) {
	if (l == NULL) {
		return NULL;
	} else if (l->data == value) {
		List restOfList = l->next;
		free(l);
		return restOfList;
	} else {
		l->next = listDelete(l->next, value);
		return l;
	}
}

The line l->next = listDelete(l->next); may be confusing due to the repeat of l->next. You may find it easier to digest if it is written like this instead:

		List restOfList = l->next;
		l->next = listDelete(restOfList, value);

(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) { ... }

Answer:

Without freeing the deleted nodes:

List listDeleteEvens(List l) {
	if (l == NULL) {
		return NULL;
	} else if (l->data % 2 == 0) {
		return listDeleteEvens(l->next);
	} else {
		l->next = listDeleteEvens(l->next);
		return l;
	}
}

Including freeing the deleted nodes:

List listDeleteEvens(List l) {
	if (l == NULL) {
		return NULL;
	} else if (l->data % 2 == 0) {
		List restOfList = l->next;
		free(l);
		return listDeleteEvens(restOfList);
	} else {
		l->next = listDeleteEvens(l->next);
		return l;
	}
}

The line l->next = listDeleteEvens(l->next); may be confusing due to the repeat of l->next. You may find it easier to digest if it is written like this instead:

		List restOfList = l->next;
		l->next = listDeleteEvens(restOfList);

(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?

Answer:

fib(2)
	calls fib(1)
		returns 1
	calls fib(0)
		returns 0
	returns 1 + 0 = 1

fib(4)
	calls fib(3)
		calls fib(2)
			calls fib(1)
				returns 1
			calls fib(0)
				returns 0
			returns 1 + 0 = 1
		calls fib(1)
			returns 1
		returns 1 + 1 = 2
	calls fib(2)
		calls fib(1)
			returns 1
		calls fib(0)
			returns 0
		returns 1 + 0 = 1
	returns 2 + 1 = 3

fib(6)
	left as an exercise for a very patient person

The main problem here is the repeated calling of functions that have already been called. The standard solution for this is to build a table of the results of previous calls to fib() and retrieve already computed results from this table.

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

Answer:

int pow(int x, unsigned int n) {
	if (n == 0) return 1;
	if (n == 1) return x;
	if (n % 2 == 0) { // n is even
		return pow(x * x, n / 2);
	} else { // n is odd
		return x * pow(x * x, n / 2);
	}
}