Week 02 Tutorial Questions

Recursion and Analysis of Algorithms

Recursion (25 mins)

For the programming questions below, use the following data type:

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

We say that recursion is a problem solving strategy where problems are solved via solving subproblems. What do we mean by a subproblem?
Suppose we want to find the length (i.e., number of nodes) of a linked list recursively.
1. What is a possible subproblem for this problem?
2. How does solving the subproblem help solve the original problem?
3. What base case(s) exist?
4. Implement a recursive function that finds the length of a linked list. It should have this signature:
```
int listLength(struct node *l) { ... }
```
Suppose we want to count the number of odd values in a linked list recursively.
1. What is a possible subproblem for this problem?
2. How does solving the subproblem help solve the original problem?
3. What base case(s) exist?
4. Implement a recursive function that counts the number of odd values in a linked list. It should have this signature:
```
int listCountOdds(struct node *l) { ... }
```
Suppose we want to check if a list is sorted in ascending order recursively.
1. What is a possible subproblem for this problem?
2. How does solving the subproblem help solve the original problem?
3. What base case(s) exist?
4. Implement a recursive function that checks whether a list is sorted in ascending order. It should have this signature:
```
bool listIsSorted(struct node *l) { ... }
```

Analysis of Algorithms (25 mins)

Consider the following functions. For each one, answer the following questions:

How long does each line take to execute?
What is the time complexity of the overall program?
Does the time for the program change as \(n\) increases?

Function 1

void func(int n) {
	int x = 7;
	x = x + n;
	printf("%d\n", x);
}

Function 2

void func(int n) {
	int i = 0;
	while (i < n) {
		printf("%d\n", i);
		i++;
	}
}

Function 3

void func(int n) {
	for (int i = 0; i < n; i++) {
		printf("%d\n", i);
	}
}

We usually express time complexity in terms of a variable \(n\). Often, we are not given \(n\) directly as an input (like in the question above), but instead the input is a data structure, such as an array. What would \(n\) represent for each of the inputs below?
1. An array
2. A Linked List

Extra Questions

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

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:
```
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.