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. CourseNana.COM

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. CourseNana.COM

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: CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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

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. CourseNana.COM

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: CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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

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

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

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

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

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

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. CourseNana.COM

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... CourseNana.COM

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: CourseNana.COM

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: CourseNana.COM

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. CourseNana.COM

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

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. CourseNana.COM

Testing

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

• 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: CourseNana.COM

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: CourseNana.COM

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. CourseNana.COM

Testing

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

• 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: CourseNana.COM

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

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: CourseNana.COM

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

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

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. CourseNana.COM

Testing

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

• 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: CourseNana.COM

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: CourseNana.COM

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. CourseNana.COM

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

Testing

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

• 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: CourseNana.COM

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: CourseNana.COM

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. CourseNana.COM

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

Testing

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

• 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: CourseNana.COM

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]