Week 02 Tutorial Answers

These questions are intended to be done in your own time or at the end of the tutorial if time permits.

Recursion

1. 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;
   	}
   }
   

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

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

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

   1. Write the algorithm in pseudocode.
   2. Analyse the worst-case time complexity of your algorithm.
   3. 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:

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

   2. 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) \).

   3. #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;
      }
      

2. 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;
      }