Week 02 Tutorial Answers

Recursion and Analysis of Algorithms

Recursion

For the questions below, use the following data type:

struct node {
	int value;
	struct node *next;
};

Write a recursive function to compute the length of a linked list. It should have this signature:

int listLength(struct node *l) { ... }

Answer:

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

Write a recursive function to count the number of odd numbers in a linked list. It should have this signature:

int listCountOdds(struct node *l) { ... }

Answer:

int listCountOdds(struct node *l) {
	if (l == NULL) {
		return 0;
	} else if (l->value % 2 != 0) {
		return 1 + listCountOdds(l->next);
	} else {
		return listCountOdds(l->next);
	}
}

Write a recursive functions to check whether a list is sorted in ascending order. It should have this signature:

bool listIsSorted(struct node *l) { ... }

Answer:

bool listIsSorted(struct node *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->value > l->next->value) {
		return false;
	
	// check whether rest of the list is sorted
	} else {
		return listIsSorted(l->next);
	}
}

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:

struct node *listDelete(struct node *l, int value) { ... }

Answer:

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

Recall that an alternative representation of a linked list uses a struct that contains a pointer to the first node of the list:
```
struct list {
	struct node *head;
};
```
How would your recursive solutions for the above questions change if the functions took a struct list pointer instead of a node pointer? For example:
```
int listLength(struct list *l);
```
Answer:
We can't recurse through the list with a struct list pointer, because the nodes themselves are represented by a different struct type (struct node). Therefore, we need to create a helper function to perform the recursion, that takes in a struct node pointer. We can then call the helper function from the original function.

listLength, listCountOdds and listIsSorted would be implemented as follows:
```
int listLength(struct list *l) {
	return listLengthRec(l->head);
}

int listCountOdds(struct list *l) {
	return listCountOddsRec(l->head);
}

bool listIsSorted(struct list *l) {
	return listIsSortedRec(l->head);
}
```
where listLengthRec, listCountOddsRec and listIsSortedRec are the recursive solutions to questions 1-3 above.

A function that takes a struct list pointer does not need to return a pointer to the beginning of the list if it modifies the list. Thus, listDelete can be a void function. It would be implemented as follows:
```
void listDelete(struct list *l, int value) {
	l->head = listDeleteRec(l->head, value);
}
```
where listDeleteRec is the solution to question 4 above. Note that the return value of the recursive functions must be assigned back to l->head, because if the first node of the list changes, l->head must be updated to point to the new first node.
The Tower of Hanoi is a puzzle consisting of three rods (Rod A, B and C) and disks of various sizes. The disks are initially stacked on Rod A from largest (at the bottom) to smallest (at the top), and the goal is to move all the disks onto Rod C, while following these rules:
- Only one disk can be moved at a time
- A larger disk cannot be placed on top of a smaller disk
Write a function that prints out instructions to complete the puzzle. The function should take in the number of disks, and the names of the three rods (A, B and C).
```
void solveHanoi(int numDisks, char *fromRod, char *toRod, char *otherRod) { ... }
```
For example, for three disks, the function call solveHanoi(3, "A", "C", "B") should print the following:
```
Move disk from Rod A to Rod C
Move disk from Rod A to Rod B
Move disk from Rod C to Rod B
Move disk from Rod A to Rod C
Move disk from Rod B to Rod A
Move disk from Rod B to Rod C
Move disk from Rod A to Rod C
```
Answer:
Behold, the power of recursion!
```
void solveHanoi(int numDisks, char *fromRod, char *toRod, char *otherRod) {
	if (numDisks == 0) return;
	
	solveHanoi(numDisks - 1, fromRod, otherRod, toRod);
	printf("Move disk from Rod %s to Rod %s\n", fromRod, toRod);
	solveHanoi(numDisks - 1, otherRod, toRod, fromRod);
}
```

Analysis of Algorithms

Design an algorithm to determine if a string of length \( n \) is a palindrome - that is, it reads the same backwards as forwards. For example, "racecar" is a palindrome, while "reviewer" is not.

Write the algorithm in pseudocode.
Analyse the worst-case time complexity of your algorithm.
Implement your algorithm in C. Your program should accept a single command line argument, and check whether it is a palindrome. Examples of the program executing are:
```
./palindrome racecar
yes
./palindrome reviewer
no
```
Hint: You may use the standard library function strlen(3), which has prototype size_t strlen(char *), is defined in <string.h>, and which computes the length of a string (without counting its terminating '\0' character).

Answer:

isPalindrome(S):
	Input:  array S[0..n - 1] of characters
	Output: true if S is a palindrome, false otherwise
	
	l = 0
	r = n - 1
	while l < r do
		if S[l] ≠ S[r] then
			return false
		end if
		l = l + 1
		r = r - 1
	end while
	
	return true

The worst case occurs when the string is a palindrome, as the while loop must run to completion. In this case, the number of times each line is executed is:

isPalindrome(S):
	Input:  array S[0..n - 1] of characters
	Output: true if S is a palindrome, false otherwise
	
	l = 0                                   <-- 1
	r = n - 1                               <-- 1
	while l < r do                          <-- n/2
		if S[l] ≠ S[r] then                 <-- n/2
			return false
		end if
		l = l + 1                           <-- n/2
		r = r - 1                           <-- n/2
	end while
	
	return true                             <-- 1

This is \(2n + 3\) line executions, so the worst-case time complexity is \(O(n)\).

In fact, there is no need to count line executions. By observing that there are at most \( \lfloor n/2 \rfloor \) iterations of the loop and the operations inside the loop are \( O(1) \), we can conclude that the worst-case time complexity is \( O(n) \).

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

static bool isPalindrome(char *s);

int main(int argc, char *argv[]) {
	if (argc == 2) {
		if (isPalindrome(argv[1])) {
			printf("yes\n");
		} else {
			printf("no\n");
		}
	}
	return 0;
}

static bool isPalindrome(char *s) {
	int l = 0;
	int r = strlen(s) - 1;

	while (l < r) {
		if (s[l] != s[r]) {
			return false;
		}
		l++;
		r--;
	}
	return true;
}

Using only techniques that you have learned so far, design an algorithm to determine if an array contains two elements that sum to a given value.
1. Write the algorithm in pseudocode.
2. Analyse the worst-case time complexity of your algorithm.
3. Implement your algorithm as a function in C. The algorithm should accept an array and a value as input and return true or false.
Answer:
1. ```
hasTwoSum(A, v):
	Input:  array A[0..n - 1] of integers
	        integer v
	Output: true if A contains two elements that sum to v, false otherwise

	for i = 0 up to n - 1 do
		for j = i + 1 up to n - 1 do
			if A[i] + A[j] = v then
				return true
			end if
		end for
	end for
	
	return false
```
2. The worst case occurs when there are no two elements that sum to the given value. In this case, there are \( n \) iterations of the outer loop and \( (n - 1) + (n - 2) + \ldots + 1 + 0 = \frac{1}{2} n(n - 1) \) iterations of the inner loop. Removing constant factors and lower terms gives a worst case time complexity of \( O(n^2) \).
3. bool hasTwoSum(int a[], int n, int v) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (a[i] + a[j] == v) { return true; } } } return false; }