Week 02 Tutorial Questions

Recursion and Analysis of Algorithms

Recursion

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

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

What is recursion?

Correct answer: When a function calls itself

Better answer: A problem solving technique where problems are solved via subproblems (smaller versions of the same problem)

Explain how you could solve each of these problems recursively. Make sure to identify what the subproblems are in each case:
- Build a pyramid of width \(n\)
- Find the total size of a folder on your computer
- Evaluate a binary mathematical expression, where an expression is either (1) a number, or (2) the sum, difference, product or division of two sub-expressions, e.g., \(((7 - 5) \times 8) + (2 \div ((3 + 9) \times 6))\)
- Solve the Tower of Hanoi (see the question below)
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.

Recursion

Click to reveal answer:

Analysis of Algorithms