Week 02 Lab Exercise

The greatest common divisor, or GCD, of two integers \( a \) and \( b \) is the largest integer that divides both \( a \) and \( b \) with no remainder. For example, the GCD of \( 16 \) and \( 28 \) is \( 4 \) because \( 16 = 4 \times 4 \) and \( 28 = 4 \times 7 \), and there is no larger integer than divides both.

One way to calculate the GCD would be to totally factor both numbers and find common factors, but there is a much faster and easier way to do it.

If \( r \) is the remainder when we divide \( a \) by \( b \), then the common divisors of \( a \) and \( b \) are precisely the same as the common divisors of \( b \) and \( r \), so the following identity holds:

If we start with any two positive integers, and apply this identity repeatedly, \( r \) will eventually become zero, and the other number in the pair is the greatest common divisor.

This is an amazing method known as Euclid's algorithm, and is probably the oldest known non-trivial algorithm; it was first described in Euclid's Elements in around 300 BC.

Your task is to implement the following function in gcd.c:

int gcd(int a, int b);

This function should find the GCD of two integers using Euclid's algorithm as described above. You can assume that a and b are non-negative, and that at most one of them is 0.

Testing

gcd.c contains a main function which allows you to test your gcd function. The main function takes two command-line arguments which are the two integers. Here are some examples of its usage:

make
...
./gcd 16 28
The GCD of 16 and 28 is 4
./gcd 25 15
The GCD of 25 and 15 is 5
./gcd 12 72
The GCD of 12 and 72 is 12
./gcd 64 25
The GCD of 64 and 25 is 1
./gcd 0 42
The GCD of 0 and 42 is 42

I have a terrible rabbit problem.

I used to have a pair of baby rabbits; they were extremely cute and fluffy, so of course I got them. But the shopkeeper I got them from - a guy named Leonardo, of Pisa Pets - didn't tell me they would mature very fast, and breed even faster.

After a month, I had a mature pair of rabbits... and, of course, they bred. Damn.

So, a month later, I had a pair of adults and a pair of baby rabbits.

And a month later, I had two pairs of adults, and another pair of baby rabbits.

And a month later, I had three pairs of adults, and two pairs of baby rabbits.

And a month later, I had five pairs of adults, and three pairs of baby rabbits.

HELP! I HAVE SO MANY RABBITS, I'M GOING HOPPING MAD!

Can you help me figure out how many rabbits I'll have? Given that I started with one pair of baby rabbits, implement the following function in rabbits.c that tells me how many rabbits I'll have after a given number of months.

long long rabbits(int months);

You can assume I won't ask about any time longer than 60 months - surely the rabbits will have taken over the world by then...

Testing

rabbits.c contains a main function which allows you to test your rabbits function. The main function accepts one command-line argument which is the number of months. Here are some examples of its usage:

make
...
./rabbits 0
Number of rabbits after 0 month(s): 2
./rabbits 1
Number of rabbits after 1 month(s): 2
./rabbits 2
Number of rabbits after 2 month(s): 4
./rabbits 12
Number of rabbits after 12 month(s): 466
./rabbits 42
... after a long pause ...
Number of rabbits after 42 month(s): 866988874
./rabbits 60
... after several hours ...
Number of rabbits after 60 month(s): 5009461563922

Recursion works really well with linked lists, because a linked list can be defined recursively as follows:

This means we usually have a base case where the node pointer is NULL, and a recursive case where we do something with the current value and recursively call the function on the rest of the list. Depending on the problem, there may be more base cases or recursive cases.

Your task is to implement this function in listTail.c:

int listTail(struct node *list);

This function should use recursion to find the last value in the given list. You can assume that the list is not empty. The function must not modify the list.

Testing

listTail.c contains a main function which allows you to test your listTail function. The main function:

• Reads the size of the list
• Reads the values of the list
• Displays the list
• Calls listTail
• Displays the result

Here are some examples of its usage:

make
...
./listTail
Enter list size: 7
Enter list values: 6 8 9 2 5 1 3
List: [6, 8, 9, 2, 5, 1, 3]
The last element is: 3
./listTail
Enter list size: 4
Enter list values: 2 5 2 1
List: [2, 5, 2, 1]
The last element is: 1
./listTail
Enter list size: 1
Enter list values: 42
List: [42]
The last element is: 42

Your task is to implement this function in listMax.c:

int listMax(struct node *list);

This function should use recursion to find the largest value in the given list. You can assume that the list is not empty. The function must not modify the list.

Testing

listMax.c contains a main function which allows you to test your listMax function. The main function:

• Reads the size of the list
• Reads the values of the list
• Displays the list
• Calls listMax
• Displays the result

Here are some examples of its usage:

make
...
./listMax
Enter list size: 5
Enter list values: 7 2 6 8 0
List: [7, 2, 6, 8, 0]
The maximum element is: 8
./listMax
Enter list size: 5
Enter list values: 9 6 1 8 8
List: [9, 6, 1, 8, 8]
The maximum element is: 9
./listMax
Enter list size: 4
Enter list values: 2 5 2 1
List: [2, 5, 2, 1]
The maximum element is: 5
./listMax
Enter list size: 1
Enter list values: 42
List: [42]
The maximum element is: 42

Your task is to implement this function in listShift.c:

struct node *listShift(struct node *list);

This function should use recursion to shift the given list to the right once and return a pointer to the start of the updated list. When a linked list is shifted to the right, the node at the end of the list is moved to the start.

Testing

listShift.c contains a main function which allows you to test your listShift function. The main function:

• Reads the size of the list
• Reads the values of the list
• Displays the list
• Calls listShift
• Displays the updated list

Here are some examples of its usage:

make
...
./listShift
Enter list size: 3
Enter list values: 16 5 2
List: [16, 5, 2]
List after shifting: [2, 16, 5]
./listShift
Enter list size: 5
Enter list values: 9 6 1 8 8
List: [9, 6, 1, 8, 8]
List after shifting: [8, 9, 6, 1, 8]

Often in this course, a list will be represented by two structures, one for the usual list node, and one which contains a pointer to the head of the list (along with other data about the list such as its size), usually called a wrapper or container struct. In this case, since we want to recurse on the nodes, not the wrapper struct, we need to implement a helper function which takes in a node pointer and then call it from the original function. For example:

int listFunc(struct list *list) {
	return listFuncHelper(list->head);
}

Your task is to implement this function in listSum.c:

int listSum(struct list *list);

This function should use a recursive helper function that takes in a node pointer to find the sum of a linked list. The function must not modify the list.

Testing

listSum.c contains a main function which allows you to test your listSum function. The main function:

• Reads the size of the list
• Reads the values of the list
• Displays the list
• Calls listSum
• Displays the result

Here are some examples of its usage:

make
...
./listSum
Enter list size: 9
Enter list values: 8 1 5 9 6 4 9 5 1
List: [8, 1, 5, 9, 6, 4, 9, 5, 1]
The sum of the values in the list is: 48
./listSum
Enter list size: 6
Enter list values: 2 4 3 7 0 4
List: [2, 4, 3, 7, 0, 4]
The sum of the values in the list is: 20
./listSum 
Enter list size: 5
Enter list values: 3 5 2 4 1
List: [3, 5, 2, 4, 1]
The sum of the values in the list is: 15
./listSum
Enter list size: 2
Enter list values: 42 -4
List: [42, -4]
The sum of the values in the list is: 38
./listSum
Enter list size: 0
List: []
The sum of the values in the list is: 0

Your task is to implement this function in listInsertOrdered.c:

void listInsertOrdered(struct list *list, int value);

This function should use recursion to insert the given value into an ordered linked list. The list should remain ordered after inserting the value. The function should be able to insert duplicates.

The given file contains a newNode function. You can use this in your solution.

Testing

listInsertOrdered.c contains a main function which allows you to test your listInsertOrdered function. The main function:

• Reads the size of the list
• Reads the values of the list
• Displays the list
• Reads the value to insert
• Calls listInsertOrdered
• Displays the updated list

Here are some examples of its usage:

make
...
./listInsertOrdered
Enter list size: 3
Enter list values (must be in ascending order): 2 5 7
List: [2, 5, 7]
Enter value to insert: 1
List after inserting 1: [1, 2, 5, 7]
./listInsertOrdered
Enter list size: 3
Enter list values (must be in ascending order): 2 5 7
List: [2, 5, 7]
Enter value to insert: 3
List after inserting 3: [2, 3, 5, 7]
./listInsertOrdered
Enter list size: 3
Enter list values (must be in ascending order): 2 5 7
List: [2, 5, 7]
Enter value to insert: 5
List after inserting 5: [2, 5, 5, 7]
./listInsertOrdered
Enter list size: 3
Enter list values (must be in ascending order): 2 5 7
List: [2, 5, 7]
Enter value to insert: 6
List after inserting 6: [2, 5, 6, 7]
./listInsertOrdered
Enter list size: 3
Enter list values (must be in ascending order): 2 5 7
List: [2, 5, 7]
Enter value to insert: 8
List after inserting 8: [2, 5, 7, 8]
./listInsertOrdered
Enter list size: 0
List: []
Enter value to insert: 42
List after inserting 42: [42]

Your task is to implement this function in listInsertNth.c:

void listInsertNth(struct list *list, int n, int value);

This function should use recursion to insert the given value before position n of the linked list. The list elements are numbered in the same manner as array elements, so the first element in the list is considered to be at position 0, the second element is considered to be at position 1, and so on. If there are less than n elements in the list, the new value should be inserted at the end of the list. You can assume that n is non-negative.

The given file contains a newNode function. You can use this in your solution.

Testing

listInsertNth.c contains a main function which allows you to test your listInsertNth function. The main function:

• Reads the size of the list
• Reads the values of the list
• Displays the list
• Reads the values of n and value
• Calls listInsertNth
• Displays the updated list

Here are some examples of its usage:

make
...
./listInsertNth
Enter list size: 3
Enter list values: 16 7 8
List: [16, 7, 8]
Enter position and value to insert: 0 12
List after inserting 12 at position 0: [12, 16, 7, 8]
./listInsertNth
Enter list size: 3
Enter list values: 16 7 8
List: [16, 7, 8]
Enter position and value to insert: 1 12
List after inserting 12 at position 1: [16, 12, 7, 8]
./listInsertNth
Enter list size: 3
Enter list values: 16 7 8
List: [16, 7, 8]
Enter position and value to insert: 2 12
List after inserting 12 at position 2: [16, 7, 12, 8]
./listInsertNth
Enter list size: 3
Enter list values: 16 7 8
List: [16, 7, 8]
Enter position and value to insert: 3 12
List after inserting 12 at position 3: [16, 7, 8, 12]
./listInsertNth
Enter list size: 3
Enter list values: 16 7 8
List: [16, 7, 8]
Enter position and value to insert: 4 12
List after inserting 12 at position 4: [16, 7, 8, 12]
./listInsertNth
Enter list size: 1
Enter list values: 42
List: [42]
Enter position and value to insert: 0 16
List after inserting 16 at position 0: [16, 42]
./listInsertNth
Enter list size: 0
List: []
Enter position and value to insert: 0 2
List after inserting 2 at position 0: [2]
./listInsertNth
Enter list size: 0
List: []
Enter position and value to insert: 10 2
List after inserting 2 at position 10: [2]