Week 02 Tutorial Questions

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) { ... }
```
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) { ... }
```
Write a recursive functions to check whether a list is sorted in ascending order. It should have this signature:
```
bool listIsSorted(struct node *l) { ... }
```
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) { ... }
```
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);
```
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
```

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