COMP1511 Practice Questions

Question 1Count Negative Numbers

Estimated time: 10-15 minutes

A finance application processes an array of transaction amounts (where negative values represent withdrawals) and wants a quick summary of how many withdrawals occurred. Write a function that counts how many elements of an array of n integers are strictly negative.

Zero should not be counted as negative, since it represents neither a deposit nor a withdrawal.

Your task is to complete the function int count_negative(int arr[], int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q1.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q1.c:

gcc -Wall -Wextra -o prac_q1 prac_q1.c
./prac_q1
6
-3 5 -1 0 8 -9
3

./prac_q1
3
1 2 3
0

./prac_q1
0
0

Assumptions / Restrictions / Clarifications

• n may be 0, in which case the function should return 0.
• Zero is not considered negative and must not be counted.
• arr may contain any mixture of negative, zero and positive values.
• Do not call scanf, getchar or fgets inside count_negative; all input is provided by main via arr and n.
• Do not print anything inside count_negative; only main should print.

Optional extension challenge

Also return the sum of the negative values via a second int pointer parameter, without changing the return type of the count.

You can re-fetch the starter code for this question: prac_q1.c.

Question 2Count Uppercase Letters

Estimated time: 10-15 minutes

A password-strength checker wants to verify that a candidate password contains a reasonable number of uppercase letters. Write a function that counts the number of uppercase alphabetic characters in a null-terminated string.

The function should examine every character in the string once and only count letters in the range 'A' to 'Z'.

Your task is to complete the function int count_upper(char *s), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q2.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q2.c:

gcc -Wall -Wextra -o prac_q2 prac_q2.c
./prac_q2
Hello World
2

./prac_q2
no capitals here
0

./prac_q2
SHOUTING
8

Assumptions / Restrictions / Clarifications

• Non-alphabetic characters (digits, spaces, punctuation) should be ignored.
• Lowercase letters should not be counted.
• The string may be empty, in which case the function returns 0.
• Do not call scanf, getchar or fgets inside count_upper; the string is passed in as an argument.
• count_upper must not modify the string it is given.

Optional extension challenge

Return the count of uppercase letters minus lowercase letters to measure the 'shoutiness' of the text.

You can re-fetch the starter code for this question: prac_q2.c.

Question 3Count Occurrences of a Character

Estimated time: 10-15 minutes

A text-analysis tool wants to know how frequently a particular character (for example a punctuation mark or a specific letter) appears within a block of text. Write a function that counts how many times a given character occurs within a null-terminated string.

The function should scan the entire string once and tally every exact match of the target character.

Your task is to complete the function int count_char(char *s, char target), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q3.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q3.c:

gcc -Wall -Wextra -o prac_q3 prac_q3.c
./prac_q3
banana
a
3

./prac_q3
banana
z
0

./prac_q3
Banana
B
1

Assumptions / Restrictions / Clarifications

• Comparison is case-sensitive, so 'a' and 'A' are considered different characters.
• The string may be empty, in which case the function returns 0.
• target may be any valid char, including the space character or a digit.
• Do not call scanf, getchar or fgets inside count_char; both arguments are passed in directly.

Optional extension challenge

Make the comparison case-insensitive by adding an int flag parameter, treating 'a' and 'A' as equal only when the flag is set.

You can re-fetch the starter code for this question: prac_q3.c.

Question 4String Length Without strlen

Estimated time: 10-15 minutes

As an exercise in understanding how C strings work under the hood, you are to write your own version of the standard library's strlen function, which returns the number of characters in a null-terminated string, not counting the null terminator itself.

You may not call the real strlen (or any other library function that computes string length) to implement this; you must count the characters yourself by scanning until the null terminator.

Your task is to complete the function int my_strlen(char *s), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q4.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q4.c:

gcc -Wall -Wextra -o prac_q4 prac_q4.c
./prac_q4
hello
5

./prac_q4

0

./prac_q4
a b c
5

Assumptions / Restrictions / Clarifications

• The string may be empty, in which case the function returns 0.
• s is always a valid, non-NULL, null-terminated string.
• The count does not include the null terminator character itself.
• You must not call strlen (or any equivalent library function) inside my_strlen.

Optional extension challenge

Write a companion that returns the length up to the first space, or the full length if there is no space.

You can re-fetch the starter code for this question: prac_q4.c.

Question 5Swap Two Integers via Pointers

Estimated time: 10-15 minutes

As part of learning how pointers let a function modify variables in the caller's scope, you are to write a small utility that exchanges the values of two integer variables. Write a function that swaps the values pointed to by two int pointers.

Because C passes arguments by value, the function must take pointers to the two integers so that it can modify the caller's original variables rather than local copies.

Your task is to complete the function void swap_ints(int *a, int *b), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q5.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q5.c:

gcc -Wall -Wextra -o prac_q5 prac_q5.c
./prac_q5
3 8
8 3

./prac_q5
-1 -9
-9 -1

./prac_q5
5 5
5 5

Assumptions / Restrictions / Clarifications

• a and b are always valid, non-NULL pointers to int.
• a and b may point to the same address, in which case the values should be unchanged after the call.
• The values pointed to may be negative, zero, or positive.
• swap_ints must not return a value; it communicates entirely through the pointers it is given.

Optional extension challenge

Write a three-way rotate function rotate3(int *a, int *b, int *c) that moves a->b->c->a using only pointer dereferences.

You can re-fetch the starter code for this question: prac_q5.c.

Question 6Largest of Three

Estimated time: 10-15 minutes

A simple scoring system needs to determine the winning score out of three competitors in a round. Write a function that takes three integers and returns the largest of them.

Your function should handle any combination of positive, negative and equal values correctly.

Your task is to complete the function int largest_of_three(int a, int b, int c), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q6.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q6.c:

gcc -Wall -Wextra -o prac_q6 prac_q6.c
./prac_q6
3 7 5
7

./prac_q6
-1 -1 -2
-1

./prac_q6
4 4 4
4

Assumptions / Restrictions / Clarifications

• a, b and c may be any valid int value, including negative numbers.
• If two or more values are tied for largest, return that value (ties do not matter).
• You should not use any library sorting or max functions; a few comparisons are enough.

Optional extension challenge

Generalise to return the largest of an int array of length n instead of exactly three fixed arguments.

You can re-fetch the starter code for this question: prac_q6.c.

Question 7Sum of Digits

Estimated time: 10-15 minutes

A checksum utility needs to compute a simple digit sum of a number as part of validating identifiers. Write a function that returns the sum of the decimal digits of a non-negative integer. For example the digits of 4325 are 4, 3, 2 and 5, which sum to 14.

Your function should work using arithmetic (division and modulo) rather than converting the number to a string.

Your task is to complete the function int sum_of_digits(int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q7.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q7.c:

gcc -Wall -Wextra -o prac_q7 prac_q7.c
./prac_q7
4325
14

./prac_q7
7
7

./prac_q7
0
0

./prac_q7
1000
1

Assumptions / Restrictions / Clarifications

• n is always non-negative.
• sum_of_digits(0) should return 0.
• n may have any number of digits that fits within a normal int.
• You should not use sprintf or any string conversion to solve this.

Optional extension challenge

Return the repeated digital root (keep summing digits until a single digit remains) instead of a single pass.

You can re-fetch the starter code for this question: prac_q7.c.

Question 8Array Contains Value

Estimated time: 10-15 minutes

A ticket booking system keeps a list of already-booked seat numbers in an array and needs a quick way to check whether a particular seat number has already been taken. Write a function that returns 1 if a given target value appears anywhere in an array of n integers, and 0 otherwise.

The array is not assumed to be sorted, so the search should check elements in order until either a match is found or the whole array has been examined.

Your task is to complete the function int array_contains(int arr[], int n, int target), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q8.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q8.c:

gcc -Wall -Wextra -o prac_q8 prac_q8.c
./prac_q8
6
4 8 15 16 23 42
15
1

./prac_q8
6
4 8 15 16 23 42
7
0

./prac_q8
0
5
0

Assumptions / Restrictions / Clarifications

• n may be 0, in which case the function should return 0.
• arr may contain duplicate values.
• target may or may not appear in arr, and may be any valid int value.

Optional extension challenge

Return the index of the first match (or -1 if absent) instead of a boolean, without scanning the array twice.

You can re-fetch the starter code for this question: prac_q8.c.

Question 9Temperature Converter

Estimated time: 10-15 minutes

Weather stations around the country record temperatures in degrees Celsius, but an international reporting system your team is building needs everything converted to degrees Fahrenheit before it is displayed. Write a function that converts a temperature given in degrees Celsius into degrees Fahrenheit. The formula for the conversion is F = C * 9 / 5 + 32.

Your function should work correctly for any valid temperature, including negative values (below freezing) and fractional values (e.g. 36.6 degrees for a body temperature reading).

Your task is to complete the function double celsius_to_fahrenheit(double celsius), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q9.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q9.c:

gcc -Wall -Wextra -o prac_q9 prac_q9.c
./prac_q9
0.0
32

./prac_q9
100.0
212

./prac_q9
-40.0
-40

./prac_q9
36.6
97.88

Assumptions / Restrictions / Clarifications

• You may assume celsius is a valid finite double.
• Do not round the result; return the exact computed value.
• celsius may be negative, zero, or positive, and may be a fractional value.
• You do not need to validate that celsius is within any particular physical range.

Optional extension challenge

Add the reverse conversion (Fahrenheit to Celsius) and a Celsius-to-Kelvin conversion as extra functions.

You can re-fetch the starter code for this question: prac_q9.c.

Question 10Digit Count

Estimated time: 10-15 minutes

A form-validation routine needs to check that a numeric ID entered by a user has exactly the expected number of digits. Write a function that returns the number of decimal digits in a non-negative integer.

The number 0 has 1 digit (not 0 digits), since it is still written using a single digit character.

Your task is to complete the function int digit_count(int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q10.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q10.c:

gcc -Wall -Wextra -o prac_q10 prac_q10.c
./prac_q10
4325
4

./prac_q10
0
1

./prac_q10
7
1

Assumptions / Restrictions / Clarifications

• n is non-negative.
• digit_count(0) should return 1, not 0.
• n may have any number of digits that fits within a normal int.

Optional extension challenge

Count digits in an arbitrary base b (2..16) passed as a parameter rather than always base 10.

You can re-fetch the starter code for this question: prac_q10.c.

Question 11Array Average

Estimated time: 10-15 minutes

A teacher has recorded a class's quiz scores in an array of integers and wants to display the average score to two or three decimal places. Write a function that computes the average (mean) of an array of n integers, as a double.

Because the average of integers is often not itself a whole number, the function must return a double rather than truncating to an int.

Your task is to complete the function double array_average(int arr[], int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q11.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q11.c:

gcc -Wall -Wextra -o prac_q11 prac_q11.c
./prac_q11
4
1 2 3 4
2.5

./prac_q11
1
7
7

./prac_q11
4
-2 4 -6 8
1

Assumptions / Restrictions / Clarifications

• You may assume n is greater than 0.
• arr may contain negative values, zero, and positive values in any combination.
• The result should be computed using floating-point division, not integer division.

Optional extension challenge

Return a trimmed average that ignores the single smallest and single largest values (when n is large enough).

You can re-fetch the starter code for this question: prac_q11.c.

Question 12Is Even Array

Estimated time: 10-15 minutes

A quality-control check on a batch of measurements needs to confirm that every reading in an array is an even number before proceeding with further processing. Write a function that returns 1 if every element of an array of n integers is even, and 0 otherwise.

Your function should be able to stop early as soon as it finds an odd element, since at that point the answer is already known.

Your task is to complete the function int all_even(int arr[], int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q12.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q12.c:

gcc -Wall -Wextra -o prac_q12 prac_q12.c
./prac_q12
4
2 4 6 8
1

./prac_q12
3
2 3 6
0

./prac_q12
0
1

Assumptions / Restrictions / Clarifications

• If n is 0, the function should return 1 (vacuously true, since there is no counter-example).
• arr may contain negative numbers; negative even numbers such as -4 still count as even.
• arr may contain zero, which is considered even.

Optional extension challenge

Return the index of the first odd element (or -1 if all are even) instead of a plain boolean.

You can re-fetch the starter code for this question: prac_q12.c.

Question 13Reverse an Array In Place

Estimated time: 10-15 minutes

A playlist shuffler feature needs to be able to play a list of track indices in reverse order without using any extra memory for a second list. Write a function that reverses the order of elements in an array of n integers in place (i.e. modifying the original array, using no extra array).

After the function returns, the caller's array should contain the same values but in reverse order; no new array should be allocated or returned.

Your task is to complete the function void reverse_array(int arr[], int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q13.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q13.c:

gcc -Wall -Wextra -o prac_q13 prac_q13.c
./prac_q13
5
1 2 3 4 5
5 4 3 2 1

./prac_q13
4
10 20 30 40
40 30 20 10

./prac_q13
0

Assumptions / Restrictions / Clarifications

• n may be 0, in which case the function should do nothing.
• You must not allocate a second array to perform the reversal.
• arr may contain duplicate values.
• The array should be reversed using swaps working inward from both ends.

Optional extension challenge

Reverse only a sub-range [lo, hi] of the array given two extra index parameters.

You can re-fetch the starter code for this question: prac_q13.c.

Question 14Find Minimum in Array

Estimated time: 10-15 minutes

A weather logging system stores a day's temperature readings in an array and needs to quickly identify the coldest reading of the day. Write a function that returns the smallest value in an array of n integers.

The array is not guaranteed to be sorted, so your function must examine every element to be sure it has found the true minimum.

Your task is to complete the function int find_min(int arr[], int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q14.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q14.c:

gcc -Wall -Wextra -o prac_q14 prac_q14.c
./prac_q14
5
5 3 8 1 9
1

./prac_q14
3
-4 -10 -2
-10

./prac_q14
1
42
42

Assumptions / Restrictions / Clarifications

• You may assume n is greater than 0; the function is never called on an empty array.
• arr may contain negative numbers, zero, positive numbers, or duplicate values.
• You should not modify the contents of arr.

Optional extension challenge

Return both the minimum and maximum in a single pass using two output pointer parameters.

You can re-fetch the starter code for this question: prac_q14.c.

Question 15Factorial (Iterative)

Estimated time: 10-15 minutes

A combinatorics teaching tool needs to compute factorials to demonstrate permutation counts to students. Write a function that computes n! for a non-negative integer n using iteration (a loop), returning the result as a long long.

Recall that n! is the product of all positive integers from 1 up to n, and that 0! is defined to be 1.

Your task is to complete the function long long factorial(int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q15.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q15.c:

gcc -Wall -Wextra -o prac_q15 prac_q15.c
./prac_q15
5
120

./prac_q15
0
1

./prac_q15
1
1

./prac_q15
20
2432902008176640000

Assumptions / Restrictions / Clarifications

• You may assume 0 <= n <= 20 (so the result always fits in a long long).
• factorial(0) should return 1, by definition.
• You must use iteration (a loop); a recursive solution is not required for this problem.
• The return type is long long, not int, to avoid overflow on both native and browser compilers.

Optional extension challenge

Rewrite it recursively, then compare which version overflows first as the input grows.

You can re-fetch the starter code for this question: prac_q15.c.

Question 16Is Prime

Estimated time: 10-15 minutes

A cryptography teaching tool needs a basic building block to test whether small integers are prime numbers before using them in further calculations. Write a function that determines whether a given integer greater than 1 is prime, returning 1 if it is prime and 0 otherwise.

Recall that a prime number is a number greater than 1 whose only positive divisors are 1 and itself.

Your task is to complete the function int is_prime(int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q16.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q16.c:

gcc -Wall -Wextra -o prac_q16 prac_q16.c -lm
./prac_q16
7
1

./prac_q16
8
0

./prac_q16
2
1

./prac_q16
9973
1

Assumptions / Restrictions / Clarifications

• You may assume n > 1; the function is never called with n <= 1.
• An efficient solution only needs to check divisors up to sqrt(n), rather than all the way up to n.
• 2 is the smallest prime and should be correctly identified as prime.

Optional extension challenge

Print all prime factors of n instead of just a boolean yes/no.

You can re-fetch the starter code for this question: prac_q16.c.

Question 17Count Vowels

Estimated time: 10-15 minutes

A simple spell-checking tool needs to estimate how vowel-heavy a piece of text is as a rough heuristic. Write a function that counts the number of vowels ('a', 'e', 'i', 'o', 'u', case insensitive) in a null-terminated string.

The count should include both lowercase and uppercase vowels, and should ignore all other characters, including consonants, digits, spaces and punctuation.

Your task is to complete the function int count_vowels(char *s), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q17.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q17.c:

gcc -Wall -Wextra -o prac_q17 prac_q17.c
./prac_q17
Hello World
3

./prac_q17
xyz
0

./prac_q17
AEIOU
5

./prac_q17

0

Assumptions / Restrictions / Clarifications

• The string may be empty, in which case the function should return 0.
• Only the characters 'a', 'e', 'i', 'o', 'u' and their uppercase forms count as vowels.
• The letter 'y' is never counted as a vowel.
• Non-alphabetic characters (digits, spaces, punctuation) must be ignored.

Optional extension challenge

Return counts of each individual vowel via five output parameters, not just the total.

You can re-fetch the starter code for this question: prac_q17.c.

Question 18Convert Cents to Coins

Estimated time: 10-15 minutes

A vending machine's change-making logic needs to work out the fewest coins possible to return to a customer as change. Write a function that, given a non-negative number of cents, returns the minimum number of Australian coins ($2, $1, 50c, 20c, 10c, 5c) needed to make up that amount using a greedy approach (always use the largest coin that fits).

Because Australian coin denominations happen to form a 'canonical' coin system, the greedy approach (repeatedly subtracting the largest coin that still fits) is guaranteed to produce the true minimum number of coins.

Your task is to complete the function int min_coins(int cents), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q18.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q18.c:

gcc -Wall -Wextra -o prac_q18 prac_q18.c
./prac_q18
85
4

./prac_q18
0
0

./prac_q18
500
3

Assumptions / Restrictions / Clarifications

• cents is non-negative.
• Coin values in cents are: 200, 100, 50, 20, 10, 5.
• cents is guaranteed to be exactly representable using these coin denominations (i.e. it is a multiple of 5).

Optional extension challenge

Report the individual coin counts as well, and handle an arbitrary list of denominations passed as an array.

You can re-fetch the starter code for this question: prac_q18.c.

Question 19Is Palindrome String

Estimated time: 10-15 minutes

A word-puzzle game wants to highlight palindromic words that players enter, such as "level" or "racecar". Write a function that determines whether a given null-terminated string reads the same forwards and backwards, returning 1 if it is a palindrome and 0 otherwise.

Comparison is case-sensitive and includes all characters exactly as they appear in the string, so spaces and capitalisation matter.

Your task is to complete the function int is_palindrome(char *s), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q19.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q19.c:

gcc -Wall -Wextra -o prac_q19 prac_q19.c
./prac_q19
level
1

./prac_q19
hello
0

./prac_q19

1

./prac_q19
Level
0

Assumptions / Restrictions / Clarifications

• The empty string and single-character strings are palindromes.
• Comparison is case-sensitive; no case-folding is performed.
• Every character, including spaces and punctuation, is compared exactly as given.

Optional extension challenge

Ignore spaces, punctuation and letter case so that 'A man a plan a canal Panama' is recognised as a palindrome.

You can re-fetch the starter code for this question: prac_q19.c.

Question 20Absolute Value Without abs

Estimated time: 8-12 minutes

A signal-processing routine needs the magnitude of a reading regardless of its sign, but the coding standard for this project forbids calling the standard library function abs. Write a function that returns the absolute value of an integer using only basic arithmetic and a comparison.

Your task is to complete the function int my_abs(int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q20.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q20.c:

gcc -Wall -Wextra -o prac_q20 prac_q20.c
./prac_q20
-7
7

./prac_q20
0
0

./prac_q20
42
42

Assumptions / Restrictions / Clarifications

• Do not call the library function abs.
• n may be negative, zero or positive.
• You may assume n is never INT_MIN (whose negation would overflow).
• Do not print anything inside my_abs.

Optional extension challenge

Write a my_labs for long and observe how the INT_MIN overflow problem behaves at the long boundary.

You can re-fetch the starter code for this question: prac_q20.c.

Question 21Clamp a Value to a Range

Estimated time: 8-12 minutes

A volume control must never let the level go below a minimum or above a maximum, no matter what the user requests. Write a function that clamps a value into the inclusive range [lo, hi]: values below lo become lo, values above hi become hi, and values already in range are returned unchanged.

Your task is to complete the function int clamp(int value, int lo, int hi), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q21.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q21.c:

gcc -Wall -Wextra -o prac_q21 prac_q21.c
./prac_q21
5 0 10
5

./prac_q21
-3 0 10
0

./prac_q21
15 0 10
10

Assumptions / Restrictions / Clarifications

• You may assume lo <= hi.
• The range is inclusive of both lo and hi.
• Do not print anything inside clamp.

Optional extension challenge

Write a float version and a wrap version that, instead of clamping, wraps out-of-range values around the interval.

You can re-fetch the starter code for this question: prac_q21.c.

Question 22Is Leap Year

Estimated time: 8-12 minutes

A calendar application must decide whether February has 28 or 29 days. Write a function that returns 1 if the given year is a leap year and 0 otherwise.

A year is a leap year if it is divisible by 4, except that years divisible by 100 are not leap years unless they are also divisible by 400.

Your task is to complete the function int is_leap_year(int year), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q22.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q22.c:

gcc -Wall -Wextra -o prac_q22 prac_q22.c
./prac_q22
2000
1

./prac_q22
1900
0

./prac_q22
2024
1

./prac_q22
2023
0

Assumptions / Restrictions / Clarifications

• You may assume year is a positive integer.
• Return exactly 1 for a leap year and 0 otherwise.
• Do not print anything inside is_leap_year.

Optional extension challenge

Return the number of days in a given month of a given year, using the leap-year test for February.

You can re-fetch the starter code for this question: prac_q22.c.

Question 23Integer Power (Iterative)

Estimated time: 8-12 minutes

A fixed-point maths helper needs to raise an integer base to a non-negative integer power without calling pow from the maths library. Write a function that computes base raised to the power exp using a loop.

Your task is to complete the function int int_pow(int base, int exp), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q23.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q23.c:

gcc -Wall -Wextra -o prac_q23 prac_q23.c
./prac_q23
2 10
1024

./prac_q23
5 0
1

./prac_q23
3 4
81

Assumptions / Restrictions / Clarifications

• You may assume exp >= 0.
• Recall that any base raised to the power 0 is 1, including 0 to the power 0 which you should treat as 1.
• Do not call pow or any maths-library function.
• You may assume the result fits in an int.

Optional extension challenge

Implement fast exponentiation by squaring, which uses O(log exp) multiplications instead of O(exp).

You can re-fetch the starter code for this question: prac_q23.c.

Question 24Count Even Digits

Estimated time: 10-15 minutes

A number-styling tool wants to know how many of a number's decimal digits are even (0, 2, 4, 6 or 8). Write a function that returns the count of even digits in the given integer.

The sign of a negative number should be ignored; only its digits matter.

Your task is to complete the function int count_even_digits(int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q24.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q24.c:

gcc -Wall -Wextra -o prac_q24 prac_q24.c
./prac_q24
2468
4

./prac_q24
13579
0

./prac_q24
0
1

./prac_q24
-2040
4

Assumptions / Restrictions / Clarifications

• A negative number has the same even-digit count as its absolute value.
• The number 0 has a single digit, which is even.
• You may assume n is not INT_MIN.
• Do not print anything inside count_even_digits.

Optional extension challenge

Return the count of even digits minus odd digits, so the sign of the result reveals which kind dominates.

You can re-fetch the starter code for this question: prac_q24.c.

Question 25GCD (Recursive)

Estimated time: 10-15 minutes

A fraction-simplifying routine needs the greatest common divisor of two numbers so it can reduce fractions to lowest terms. Write a RECURSIVE function that computes the greatest common divisor of two non-negative integers using Euclid's algorithm.

Euclid's algorithm relies on the fact that gcd(a, b) equals gcd(b, a % b), and that gcd(a, 0) equals a.

Your task is to complete the function int gcd(int a, int b), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q25.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q25.c:

gcc -Wall -Wextra -o prac_q25 prac_q25.c
./prac_q25
48 36
12

./prac_q25
17 5
1

./prac_q25
100 0
100

./prac_q25
13 13
13

Assumptions / Restrictions / Clarifications

• You may assume a and b are non-negative and not both zero.
• Your solution must be recursive (it must call gcd).
• gcd(a, 0) is a.
• Do not print anything inside gcd.

Optional extension challenge

Extend it to also return the least common multiple, computed as a / gcd(a, b) * b to avoid overflow.

You can re-fetch the starter code for this question: prac_q25.c.

Question 26Sum From 1 to N (Recursive)

Estimated time: 8-12 minutes

As an exercise in recursion, write a function that returns the sum of all integers from 1 up to and including n, but you must compute it RECURSIVELY rather than with a loop or a closed-form formula.

Your task is to complete the function int sum_to_n(int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q26.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q26.c:

gcc -Wall -Wextra -o prac_q26 prac_q26.c
./prac_q26
5
15

./prac_q26
0
0

./prac_q26
100
5050

Assumptions / Restrictions / Clarifications

• You may assume n >= 0.
• sum_to_n(0) is 0 (the empty sum).
• Your solution must be recursive and must not use the n * (n + 1) / 2 formula.
• Do not print anything inside sum_to_n.

Optional extension challenge

Rewrite it to sum only the even numbers from 1 to n recursively, without changing the return type.

You can re-fetch the starter code for this question: prac_q26.c.

Question 27Max Consecutive Equal Elements

Estimated time: 10-15 minutes

A monitoring dashboard wants to report the longest streak of identical readings in a log. Write a function that returns the length of the longest run of equal values that appear consecutively in an array of n integers.

Your task is to complete the function int max_run(int arr[], int n), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q27.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q27.c:

gcc -Wall -Wextra -o prac_q27 prac_q27.c
./prac_q27
6
1 1 2 2 2 3
3

./prac_q27
3
7 8 9
1

./prac_q27
0
0

Assumptions / Restrictions / Clarifications

• If n is 0 the function returns 0.
• A run is a maximal sequence of equal values in adjacent positions.
• A single element counts as a run of length 1.
• Do not print anything inside max_run.

Optional extension challenge

Also return the value that forms the longest run via an output pointer, breaking ties by earliest run.

You can re-fetch the starter code for this question: prac_q27.c.

Question 28Count Nodes In A Linked List

Estimated time: 10-15 minutes

Note prac_q28.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A playlist is stored as a linked list, one node per track, and the player needs to show how many tracks are queued. Write a function that walks a linked list and returns the number of nodes in it.

The list may be empty, in which case there are no nodes to count.

Your task is to complete the function int list_length(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q28.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q28.c:

gcc -Wall -Wextra -o prac_q28 prac_q28.c
./prac_q28
5
4 8 15 16 23
5

./prac_q28
1
7
1

./prac_q28
0
0

Assumptions / Restrictions / Clarifications

• An empty list is represented by head being NULL, and the answer is then 0.
• Do not modify the list. Your function must not change any next or value field.
• Do not call malloc or free inside list_length.
• Do not print anything inside list_length; only main should print.

Optional extension challenge

Write a second function that returns the number of nodes without using a loop, by calling itself on head->next.

You can re-fetch the starter code for this question: prac_q28.c.

Question 29Largest Value In A Linked List

Estimated time: 10-15 minutes

Note prac_q29.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A weather station appends each hour's temperature reading to a linked list. Write a function that returns the largest value stored in the list.

You may assume the list contains at least one node, so there is always an answer to return.

Your task is to complete the function int list_max(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q29.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q29.c:

gcc -Wall -Wextra -o prac_q29 prac_q29.c
./prac_q29
5
3 9 2 9 1
9

./prac_q29
4
-8 -2 -40 -5
-2

./prac_q29
1
6
6

Assumptions / Restrictions / Clarifications

• The list is guaranteed to contain at least one node.
• Values may be negative, so do not assume the largest value is positive.
• Do not modify the list.
• Do not call malloc or free inside list_max.
• Do not print anything inside list_max.

Optional extension challenge

Return the smallest value as well, through a second int pointer parameter, in a single pass.

You can re-fetch the starter code for this question: prac_q29.c.

Question 30Search A Linked List

Estimated time: 10-15 minutes

Note prac_q30.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A door system keeps the ID of every card that is allowed through in a linked list. Write a function that reports whether a given value appears anywhere in the list.

Return 1 if the value is found and 0 if it is not.

Your task is to complete the function int list_contains(struct node *head, int value), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q30.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q30.c:

gcc -Wall -Wextra -o prac_q30 prac_q30.c
./prac_q30
5
2 4 6 8 10
6
1

./prac_q30
4
1 2 3 4
9
0

./prac_q30
0
5
0

Assumptions / Restrictions / Clarifications

• An empty list contains nothing, so the answer for an empty list is always 0.
• Return as soon as the value is found; there is no need to keep walking.
• Do not modify the list.
• Do not call malloc or free inside list_contains.
• Do not print anything inside list_contains.

Optional extension challenge

Return the position of the first match instead, counting from 0, and -1 when the value is absent.

You can re-fetch the starter code for this question: prac_q30.c.

Question 31Count Occurrences In A Linked List

Estimated time: 10-15 minutes

Note prac_q31.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A vending machine logs every coin it accepts into a linked list. Write a function that counts how many nodes hold a particular value.

If the value never appears, the count is 0.

Your task is to complete the function int count_value(struct node *head, int value), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q31.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q31.c:

gcc -Wall -Wextra -o prac_q31 prac_q31.c
./prac_q31
6
1 2 1 3 1 4
1
3

./prac_q31
4
5 6 7 8
9
0

./prac_q31
0
3
0

Assumptions / Restrictions / Clarifications

• An empty list gives a count of 0.
• Every matching node counts, not just the first one.
• Do not modify the list.
• Do not call malloc or free inside count_value.
• Do not print anything inside count_value.

Optional extension challenge

Count how many nodes hold a value strictly between two bounds passed as extra parameters.

You can re-fetch the starter code for this question: prac_q31.c.

Question 32Count Even Values In A Linked List

Estimated time: 10-15 minutes

Note prac_q32.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A turnstile records the number of people in each group entering a venue, one node per group. Write a function that counts how many nodes hold an even number.

Zero is even and must be counted.

Your task is to complete the function int count_even(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q32.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q32.c:

gcc -Wall -Wextra -o prac_q32 prac_q32.c
./prac_q32
6
1 2 3 4 5 6
3

./prac_q32
4
-4 -3 0 7
2

./prac_q32
0
0

Assumptions / Restrictions / Clarifications

• Zero counts as even.
• Negative even numbers count too, so -4 is even.
• Do not modify the list.
• Do not call malloc or free inside count_even.
• Do not print anything inside count_even.

Optional extension challenge

Return the count of odd values as well, through an int pointer parameter.

You can re-fetch the starter code for this question: prac_q32.c.

Question 33Sum A Linked List From A Position

Estimated time: 15-20 minutes

Note prac_q33.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A bank statement is stored newest-first as a linked list. Write a function that adds up every value from a given position to the end of the list, counting positions from 0.

If the position is past the end of the list there is nothing to add, and the total is 0.

Your task is to complete the function int sum_from(struct node *head, int position), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q33.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q33.c:

gcc -Wall -Wextra -o prac_q33 prac_q33.c
./prac_q33
5
1 2 3 4 5
2
12

./prac_q33
4
10 20 30 40
0
100

./prac_q33
3
1 2 3
9
0

Assumptions / Restrictions / Clarifications

• Positions are counted from 0, so position 0 means the whole list.
• A position past the end of the list gives a total of 0.
• You may assume position is not negative.
• Do not modify the list.
• Do not print anything inside sum_from.

Optional extension challenge

Take an end position too, and sum only the nodes between the two positions.

You can re-fetch the starter code for this question: prac_q33.c.

Question 34Value At A Position

Estimated time: 10-15 minutes

Note prac_q34.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A queue of print jobs is held in a linked list. Write a function that returns the value stored at a given position, counting from 0.

If the position does not exist in the list, return -1.

Your task is to complete the function int value_at(struct node *head, int position), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q34.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q34.c:

gcc -Wall -Wextra -o prac_q34 prac_q34.c
./prac_q34
5
7 8 9 10 11
2
9

./prac_q34
3
4 5 6
0
4

./prac_q34
3
4 5 6
7
-1

Assumptions / Restrictions / Clarifications

• Positions count from 0, so position 0 is the first node.
• Return -1 if the position is past the end of the list.
• You may assume position is not negative.
• Do not modify the list.
• Do not print anything inside value_at.

Optional extension challenge

Return the value at a position counted from the END of the list instead.

You can re-fetch the starter code for this question: prac_q34.c.

Question 35Add To The Front Of A Linked List

Estimated time: 10-15 minutes

Note prac_q35.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A browser keeps its history newest-first in a linked list. Write a function that adds a new node holding a given value to the front of the list and returns the new head.

Adding to the front works even when the list is empty.

Your task is to complete the function struct node *push_front(struct node *head, int value), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q35.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q35.c:

gcc -Wall -Wextra -o prac_q35 prac_q35.c
./prac_q35
4
2 3 4 5
1
1 2 3 4 5

./prac_q35
0
9
9

./prac_q35
1
5
7
7 5

Assumptions / Restrictions / Clarifications

• Allocate the new node with malloc.
• Return the new head of the list, which is the node you just created.
• Adding to an empty list gives a list of one node.
• Do not print anything inside push_front.

Optional extension challenge

Write the matching pop_front, which removes and frees the first node and returns the new head.

You can re-fetch the starter code for this question: prac_q35.c.

Question 36Add To The End Of A Linked List

Estimated time: 15-20 minutes

Note prac_q36.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A ticket queue is stored as a linked list with the next person to serve at the front. Write a function that adds a node holding a given value to the END of the list and returns the head.

If the list is empty the new node becomes the head.

Your task is to complete the function struct node *push_back(struct node *head, int value), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q36.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q36.c:

gcc -Wall -Wextra -o prac_q36 prac_q36.c
./prac_q36
3
1 2 3
4
1 2 3 4

./prac_q36
0
7
7

./prac_q36
1
5
6
5 6

Assumptions / Restrictions / Clarifications

• Allocate the new node with malloc and set its next to NULL.
• If the list is empty, return the new node as the head.
• Otherwise return the original head unchanged.
• Do not print anything inside push_back.

Optional extension challenge

Keep a tail pointer so appending does not need to walk the list every time.

You can re-fetch the starter code for this question: prac_q36.c.

Question 37Delete The First Node

Estimated time: 10-15 minutes

Note prac_q37.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A task list is stored as a linked list and the front task has just been completed. Write a function that removes the first node, frees it, and returns the new head.

Deleting from an empty list leaves it empty.

Your task is to complete the function struct node *delete_first(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q37.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q37.c:

gcc -Wall -Wextra -o prac_q37 prac_q37.c
./prac_q37
5
1 2 3 4 5
2 3 4 5

./prac_q37
1
9


./prac_q37
0

Assumptions / Restrictions / Clarifications

• Call free on the node you remove.
• Return the new head, which is the second node of the original list.
• If the list is empty, return NULL.
• If the list had one node, the result is an empty list, so return NULL.
• Do not print anything inside delete_first.

Optional extension challenge

Delete the first node only when it holds a given value, otherwise leave the list alone.

You can re-fetch the starter code for this question: prac_q37.c.

Question 38Count Values Above A Threshold

Estimated time: 10-15 minutes

Note prac_q38.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A monitoring system stores each temperature reading in a linked list. Write a function that counts how many nodes hold a value strictly greater than a given limit.

A value exactly equal to the limit does not count.

Your task is to complete the function int count_above(struct node *head, int limit), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q38.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q38.c:

gcc -Wall -Wextra -o prac_q38 prac_q38.c
./prac_q38
6
1 5 9 5 12 3
5
2

./prac_q38
3
1 2 3
10
0

./prac_q38
0
0
0

Assumptions / Restrictions / Clarifications

• Only values strictly greater than limit count; equal values do not.
• An empty list gives 0.
• Do not modify the list.
• Do not print anything inside count_above.

Optional extension challenge

Count values below a second limit too, so the function reports how many fall outside a range.

You can re-fetch the starter code for this question: prac_q38.c.

Question 39Sum Of Negative Values In A Linked List

Estimated time: 10-15 minutes

Note prac_q39.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

An account keeps every transaction in a linked list, with withdrawals stored as negative numbers. Write a function that adds up only the negative values and returns that total.

The total will be zero or negative. If there are no withdrawals, return 0.

Your task is to complete the function int sum_negative(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q39.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q39.c:

gcc -Wall -Wextra -o prac_q39 prac_q39.c
./prac_q39
6
10 -5 3 -20 0 -1
-26

./prac_q39
3
1 2 3
0

./prac_q39
0
0

Assumptions / Restrictions / Clarifications

• Zero is not negative and must not be included.
• If no value is negative, return 0.
• Do not modify the list.
• Do not print anything inside sum_negative.

Optional extension challenge

Return the count of withdrawals as well, through an int pointer parameter.

You can re-fetch the starter code for this question: prac_q39.c.

Question 40Last Value In A Linked List

Estimated time: 10-15 minutes

Note prac_q40.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A sensor appends each new reading to the end of a linked list, so the most recent reading is the last node. Write a function that returns the value in the last node.

You may assume the list has at least one node.

Your task is to complete the function int last_value(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q40.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q40.c:

gcc -Wall -Wextra -o prac_q40 prac_q40.c
./prac_q40
4
3 6 9 12
12

./prac_q40
1
42
42

./prac_q40
2
-7 -8
-8

Assumptions / Restrictions / Clarifications

• The list is guaranteed to have at least one node.
• A one-node list means the first node is also the last.
• Do not modify the list.
• Do not print anything inside last_value.

Optional extension challenge

Return the last value without a loop, by having the function call itself on head->next.

You can re-fetch the starter code for this question: prac_q40.c.

Question 41Count Words in a Sentence

Estimated time: 12-18 minutes

A basic writing-assistant tool wants to give users a live word count as they type a sentence. Write a function that counts the number of words in a null-terminated string, where words are separated by one or more single space characters.

Leading and trailing spaces should not create extra (empty) words, and runs of multiple consecutive spaces between words should still only count as a single separator.

Your task is to complete the function int count_words(char *s), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q41.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q41.c:

gcc -Wall -Wextra -o prac_q41 prac_q41.c
./prac_q41
the quick brown fox
4

./prac_q41
  hello   world 
2

./prac_q41

0

./prac_q41
     
0

Assumptions / Restrictions / Clarifications

• Words are only separated by the space character ' ', not tabs or other whitespace.
• An empty string, or a string containing only spaces, has 0 words.
• Multiple consecutive spaces between words do not create extra empty words.
• Punctuation attached to a word (e.g. "fox.") is still counted as part of that word.
• Do not call scanf, getchar or fgets inside count_words; the string is passed in as an argument.

Optional extension challenge

Extend it to also treat tab and newline characters as word separators, not just the space character.

You can re-fetch the starter code for this question: prac_q41.c.

Question 42Struct Rectangle Area and Perimeter

Estimated time: 12-18 minutes

Note prac_q42.c uses the following data type:

struct rectangle {
    int width;
    int height;
};

A simple floor-planning tool represents each room as a rectangle and needs to report both its floor area (for cost estimation) and its perimeter (for skirting board length). A struct rectangle (see the provided starter header) stores an integer width and height.

Write two functions: one that computes the area of a rectangle, and one that computes its perimeter.

Your task is to complete the functions int rect_area(struct rectangle r) and int rect_perimeter(struct rectangle r), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q42.c also contains a main function which allows you to test your functions. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your functions and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your functions will be called directly during marking. The main function is only to let you test your functions.

Here is how the main function allows you to test prac_q42.c:

gcc -Wall -Wextra -o prac_q42 prac_q42.c
./prac_q42
4 5
20 18

./prac_q42
3 3
9 12

./prac_q42
1 10
10 22

Assumptions / Restrictions / Clarifications

• width and height are always positive.
• The rectangle is passed by value, so the functions should not need to modify it.
• Area is width * height; perimeter is 2 * (width + height).

Optional extension challenge

Add a function that returns 1 if one rectangle fits entirely inside another (ignoring rotation).

You can re-fetch the starter code for this question: prac_q42.c.

Question 43Struct Distance Between Two Points

Estimated time: 12-18 minutes

Note prac_q43.c uses the following data type:

struct point {
    int x;
    int y;
};

A simple 2D geometry library needs a way to measure how far apart two points are, for example to compute how far a game character has moved. A struct point represents a location in 2D space with integer x and y coordinates (see the provided starter header). Write a function that computes the Euclidean separation between two points as a double.

Both points are passed by value (as whole structs), so your function should not need to use pointers to access their fields.

Your task is to complete the function double distance(struct point p1, struct point p2), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q43.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q43.c:

gcc -Wall -Wextra -o prac_q43 prac_q43.c -lm
./prac_q43
0 0 3 4
5

./prac_q43
-2 -2 2 1
5

./prac_q43
7 7 7 7
0

Assumptions / Restrictions / Clarifications

• The formula is sqrt((x2 - x1)^2 + (y2 - y1)^2).
• You must #include <math.h> to use sqrt, and link with -lm if compiling manually.
• x and y coordinates may be negative, zero, or positive.
• p1 and p2 may refer to the same coordinates, in which case the result is 0.

Optional extension challenge

Add a function that, given an array of points, returns the pair that are closest together.

You can re-fetch the starter code for this question: prac_q43.c.

Question 44Compass Direction Turn

Estimated time: 10-15 minutes

Note prac_q44.c uses the following data type:

enum direction {
    NORTH,
    EAST,
    SOUTH,
    WEST
};

A robot navigation module tracks which way a robot is facing using the four compass points. Write a function that, given the current facing direction, returns the direction after turning 90 degrees clockwise (to the right).

The compass points are defined by an enum in clockwise order, so turning right advances to the next point and wraps around from WEST back to NORTH.

Your task is to complete the function enum direction turn_right(enum direction d), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q44.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q44.c:

gcc -Wall -Wextra -o prac_q44 prac_q44.c
./prac_q44
0 1
EAST

./prac_q44
0 4
NORTH

./prac_q44
3 1
NORTH

Assumptions / Restrictions / Clarifications

• The only valid directions are the four enum direction values NORTH, EAST, SOUTH and WEST.
• Turning right from WEST wraps around to NORTH.
• Do not print anything inside turn_right.
• You must return an enum direction value, not a plain int printed by the function.

Optional extension challenge

Add turn_left and a turn_to function that returns the fewest 90-degree turns needed to face a target direction.

You can re-fetch the starter code for this question: prac_q44.c.

Question 45Translate a Point

Estimated time: 10-15 minutes

Note prac_q45.c uses the following data type:

typedef struct {
    int x;
    int y;
} Point;

A 2D drawing library represents positions with a Point type and needs to move points around the canvas. Write a function that returns a new Point obtained by shifting the given point by dx along the x axis and dy along the y axis.

The Point type is a typedef, so you can use it directly as Point without writing struct each time.

Your task is to complete the function Point translate(Point p, int dx, int dy), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q45.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q45.c:

gcc -Wall -Wextra -o prac_q45 prac_q45.c
./prac_q45
1 2 3 4
(4, 6)

./prac_q45
0 0 -1 -1
(-1, -1)

./prac_q45
5 5 0 0
(5, 5)

Assumptions / Restrictions / Clarifications

• Return a new Point; you do not need to modify the caller's original point.
• dx and dy may be negative, moving the point left or down.
• Do not print anything inside translate.

Optional extension challenge

Add scale(Point p, int factor) and manhattan_distance(Point a, Point b) using the same Point type.

You can re-fetch the starter code for this question: prac_q45.c.

Question 46Delete The Last Node

Estimated time: 15-20 minutes

Note prac_q46.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

An undo stack is stored as a linked list with the oldest action at the front. Write a function that removes the LAST node, frees it, and returns the head of the list.

Removing the last node of a one-node list leaves the list empty.

Your task is to complete the function struct node *delete_last(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q46.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q46.c:

gcc -Wall -Wextra -o prac_q46 prac_q46.c
./prac_q46
4
1 2 3 4
1 2 3

./prac_q46
1
9


./prac_q46
0

Assumptions / Restrictions / Clarifications

• Call free on the node you remove.
• If the list is empty, return NULL.
• If the list has exactly one node, free it and return NULL.
• Otherwise the head does not change, so return it.
• Do not print anything inside delete_last.

Optional extension challenge

Return the value that was removed through an int pointer parameter, as well as the new head.

You can re-fetch the starter code for this question: prac_q46.c.

Question 47Count Nodes Before A Value

Estimated time: 15-20 minutes

Note prac_q47.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A race result is stored as a linked list of runner numbers in finishing order. Write a function that counts how many runners finished before a given runner number.

If the number does not appear in the list, return -1.

Your task is to complete the function int count_before(struct node *head, int value), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q47.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q47.c:

gcc -Wall -Wextra -o prac_q47 prac_q47.c
./prac_q47
5
8 3 5 9 1
9
3

./prac_q47
4
2 4 6 8
2
0

./prac_q47
3
1 2 3
7
-1

Assumptions / Restrictions / Clarifications

• Return -1 if the value never appears in the list.
• Only the FIRST occurrence matters, so stop counting there.
• If the value is in the first node, the answer is 0.
• Do not modify the list.
• Do not print anything inside count_before.

Optional extension challenge

Count how many nodes come AFTER the first occurrence instead.

You can re-fetch the starter code for this question: prac_q47.c.

Question 48Is A Linked List Increasing

Estimated time: 15-20 minutes

Note prac_q48.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A leaderboard is stored as a linked list and should always be in strictly increasing order. Write a function that returns 1 if every value is strictly greater than the one before it, and 0 otherwise.

A list with fewer than two nodes is trivially in order, so return 1.

Your task is to complete the function int is_increasing(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q48.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q48.c:

gcc -Wall -Wextra -o prac_q48 prac_q48.c
./prac_q48
5
1 3 7 8 20
1

./prac_q48
4
1 5 5 9
0

./prac_q48
0
1

Assumptions / Restrictions / Clarifications

• Strictly increasing means equal neighbours are NOT in order, so 3 3 returns 0.
• An empty list and a one-node list both return 1.
• Do not modify the list.
• Do not use an array, and do not call malloc.
• Do not print anything inside is_increasing.

Optional extension challenge

Return 1 for a list that is sorted in EITHER direction, increasing or decreasing.

You can re-fetch the starter code for this question: prac_q48.c.

Question 49Delete Every Node With A Value

Estimated time: 20-25 minutes

Note prac_q49.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A spam filter keeps a linked list of message IDs and needs to purge every entry matching a blocked ID. Write a function that removes ALL nodes holding a given value, frees them, and returns the head of the resulting list.

If every node matches, the result is an empty list.

Your task is to complete the function struct node *delete_all(struct node *head, int value), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q49.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q49.c:

gcc -Wall -Wextra -o prac_q49 prac_q49.c
./prac_q49
7
1 2 1 3 1 4 1
1
2 3 4

./prac_q49
3
5 5 5
5


./prac_q49
4
1 2 3 4
9
1 2 3 4

Assumptions / Restrictions / Clarifications

• Every matching node must be removed, not just the first.
• Call free on each node you remove.
• If the list becomes empty, return NULL.
• Matching nodes may be at the front, the end, or adjacent to each other.
• Do not print anything inside delete_all.

Optional extension challenge

Return the number of nodes removed through an int pointer parameter.

You can re-fetch the starter code for this question: prac_q49.c.

Question 50Delete The Node At A Position

Estimated time: 20-25 minutes

Note prac_q50.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A playlist is a linked list and the user has asked to remove the track at a given position, counting from 0. Write a function that removes and frees that node and returns the head of the list.

If the position does not exist, leave the list unchanged.

Your task is to complete the function struct node *delete_at(struct node *head, int position), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q50.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q50.c:

gcc -Wall -Wextra -o prac_q50 prac_q50.c
./prac_q50
5
10 20 30 40 50
2
10 20 40 50

./prac_q50
3
1 2 3
0
2 3

./prac_q50
3
1 2 3
7
1 2 3

Assumptions / Restrictions / Clarifications

• Positions count from 0, so position 0 removes the first node.
• If position is past the end of the list, change nothing and return the head.
• You may assume position is not negative.
• Call free on the node you remove.
• Do not print anything inside delete_at.

Optional extension challenge

Insert a value at a given position instead, shifting the rest of the list along.

You can re-fetch the starter code for this question: prac_q50.c.

Question 51Second Largest Value In A Linked List

Estimated time: 20-25 minutes

Note prac_q51.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A scoreboard is stored as a linked list and needs to show the runner-up as well as the winner. Write a function that returns the second largest DISTINCT value in the list.

If every node holds the same value there is no runner-up, so return -1.

Your task is to complete the function int second_largest(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q51.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q51.c:

gcc -Wall -Wextra -o prac_q51 prac_q51.c
./prac_q51
6
4 9 2 9 7 1
7

./prac_q51
3
5 5 5
-1

./prac_q51
4
-3 -8 -1 -1
-3

Assumptions / Restrictions / Clarifications

• Distinct means duplicates of the largest value do not count as second, so 9 9 4 gives 4.
• If the list has fewer than two distinct values, return -1.
• Values may be negative.
• Do not modify the list, do not use an array, and do not call malloc.
• Do not print anything inside second_largest.

Optional extension challenge

Return the Nth largest distinct value, with N as a parameter.

You can re-fetch the starter code for this question: prac_q51.c.

Question 52Copy A Linked List

Estimated time: 20-25 minutes

Note prac_q52.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

Before running a risky operation, a program wants a private copy of a linked list so the original is untouched. Write a function that builds and returns a brand new list holding the same values in the same order.

The copy must be independent: changing one list must not affect the other.

Your task is to complete the function struct node *copy_list(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q52.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q52.c:

gcc -Wall -Wextra -o prac_q52 prac_q52.c
./prac_q52
4
1 2 3 4
1 2 3 4

./prac_q52
1
9
9

./prac_q52
0

Assumptions / Restrictions / Clarifications

• Every node in the copy must be freshly allocated with malloc.
• Do not reuse any node from the original list.
• Copying an empty list gives an empty list, so return NULL.
• Do not modify the original list.
• Do not print anything inside copy_list.

Optional extension challenge

Copy the list in reverse order instead, without a second pass.

You can re-fetch the starter code for this question: prac_q52.c.

Question 53Are Two Linked Lists Equal

Estimated time: 20-25 minutes

Note prac_q53.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A sync tool compares a local list with a remote one to decide whether an upload is needed. Write a function that returns 1 if two linked lists hold exactly the same values in the same order, and 0 otherwise.

Lists of different lengths are never equal.

Your task is to complete the function int lists_equal(struct node *a, struct node *b), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q53.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q53.c:

gcc -Wall -Wextra -o prac_q53 prac_q53.c
./prac_q53
3
1 2 3
3
1 2 3
1

./prac_q53
3
1 2 3
4
1 2 3 4
0

./prac_q53
0
0
1

Assumptions / Restrictions / Clarifications

• Two empty lists are equal, so return 1.
• Lists of different lengths are not equal, even if one is a prefix of the other.
• Do not modify either list.
• Do not use an array, and do not call malloc.
• Do not print anything inside lists_equal.

Optional extension challenge

Return 1 when one list is a prefix of the other, rather than requiring exact equality.

You can re-fetch the starter code for this question: prac_q53.c.

Question 54Join Two Linked Lists

Estimated time: 20-25 minutes

Note prac_q54.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

Two queues are being merged into one. Write a function that attaches the second list to the end of the first and returns the head of the combined list.

No new nodes should be created: the existing nodes are relinked.

Your task is to complete the function struct node *join_lists(struct node *a, struct node *b), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q54.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q54.c:

gcc -Wall -Wextra -o prac_q54 prac_q54.c
./prac_q54
3
1 2 3
2
8 9
1 2 3 8 9

./prac_q54
0
3
4 5 6
4 5 6

./prac_q54
2
7 8
0
7 8

Assumptions / Restrictions / Clarifications

• Do not call malloc; reuse the existing nodes.
• If the first list is empty, the result is simply the second list.
• If the second list is empty, the result is the first list unchanged.
• The result must be a single list ending in NULL.
• Do not print anything inside join_lists.

Optional extension challenge

Join the lists alternately instead, taking one node from each in turn.

You can re-fetch the starter code for this question: prac_q54.c.

Question 55Insert At A Position

Estimated time: 20-25 minutes

Note prac_q55.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A queue system lets staff insert an urgent job partway down the list. Write a function that inserts a new node holding a given value so that it ends up at a given position, counting from 0, and returns the head.

If the position is past the end of the list, add the new node at the end.

Your task is to complete the function struct node *insert_at(struct node *head, int position, int value), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q55.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q55.c:

gcc -Wall -Wextra -o prac_q55 prac_q55.c
./prac_q55
4
1 2 4 5
2
3
1 2 3 4 5

./prac_q55
3
1 2 3
0
9
9 1 2 3

./prac_q55
2
1 2
7
8
1 2 8

Assumptions / Restrictions / Clarifications

• Positions count from 0, so position 0 puts the new node at the front.
• A position past the end of the list appends to the end.
• You may assume position is not negative.
• Allocate the new node with malloc.
• Do not print anything inside insert_at.

Optional extension challenge

Insert so the list stays sorted, ignoring the position argument entirely.

You can re-fetch the starter code for this question: prac_q55.c.

Question 56Remove Duplicates From A Sorted Linked List

Estimated time: 20-25 minutes

Note prac_q56.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A sorted list of student IDs has picked up repeats after a merge. Write a function that removes every repeated node so each value appears exactly once, and returns the head.

The list is already sorted, so equal values are always next to each other.

Your task is to complete the function struct node *remove_duplicates(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q56.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q56.c:

gcc -Wall -Wextra -o prac_q56 prac_q56.c
./prac_q56
7
1 1 2 3 3 3 4
1 2 3 4

./prac_q56
3
5 5 5
5

./prac_q56
0

Assumptions / Restrictions / Clarifications

• You may assume the list is sorted in non-decreasing order.
• Keep the FIRST of each run of equal values and free the rest.
• Call free on every node you remove.
• An empty list stays empty.
• Do not print anything inside remove_duplicates.

Optional extension challenge

Remove duplicates from an UNSORTED list, which needs a different approach entirely.

You can re-fetch the starter code for this question: prac_q56.c.

Question 57Delete The Second Last Node

Estimated time: 20-25 minutes

Note prac_q57.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

An editor keeps a linked list of saved revisions and wants to discard the one just before the newest. Write a function that removes the second-last node, frees it, and returns the head.

A list with fewer than two nodes has no second-last node, so leave it unchanged.

Your task is to complete the function struct node *delete_second_last(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q57.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q57.c:

gcc -Wall -Wextra -o prac_q57 prac_q57.c
./prac_q57
5
1 2 3 4 5
1 2 3 5

./prac_q57
2
7 8
8

./prac_q57
1
9
9

Assumptions / Restrictions / Clarifications

• If the list has fewer than two nodes, change nothing.
• In a two-node list the second-last node is the head.
• Call free on the node you remove.
• Do not print anything inside delete_second_last.

Optional extension challenge

Remove the Nth node from the end, with N as a parameter.

You can re-fetch the starter code for this question: prac_q57.c.

Question 58Count Distinct Values In A Linked List

Estimated time: 20-25 minutes

Note prac_q58.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A survey stores every response in a linked list and needs to know how many different answers were given. Write a function that counts how many DISTINCT values appear in the list.

The list is not sorted, so equal values may be anywhere.

Your task is to complete the function int count_distinct(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q58.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q58.c:

gcc -Wall -Wextra -o prac_q58 prac_q58.c
./prac_q58
6
1 2 1 3 2 4
4

./prac_q58
3
5 5 5
1

./prac_q58
0
0

Assumptions / Restrictions / Clarifications

• A value that appears several times counts once.
• An empty list has 0 distinct values.
• Do not modify the list, do not use an array, and do not call malloc.
• Do not print anything inside count_distinct.

Optional extension challenge

Return the value that appears most often, rather than the number of distinct values.

You can re-fetch the starter code for this question: prac_q58.c.

Question 59Swap The First And Last Values

Estimated time: 15-20 minutes

Note prac_q59.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A rota is stored as a linked list and the first and last people on it need to trade places. Write a function that swaps the VALUES held in the first and last nodes and returns the head.

Lists with fewer than two nodes need no change.

Your task is to complete the function struct node *swap_ends(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q59.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q59.c:

gcc -Wall -Wextra -o prac_q59 prac_q59.c
./prac_q59
5
1 2 3 4 5
5 2 3 4 1

./prac_q59
2
7 8
8 7

./prac_q59
1
9
9

Assumptions / Restrictions / Clarifications

• Swap the values, not the nodes; no relinking and no malloc.
• A list with fewer than two nodes is returned unchanged.
• Do not call free.
• Do not print anything inside swap_ends.

Optional extension challenge

Swap the nodes themselves rather than their values, which is considerably harder.

You can re-fetch the starter code for this question: prac_q59.c.

Question 60Rotate A Linked List Forward

Estimated time: 20-25 minutes

Note prac_q60.c uses the following data types:

struct node, a singly linked list node with an int value and a struct node *next (with helper functions build_list, print_list and free_list already provided for you in node.h)

A rota rotates each week so the person at the front moves to the back. Write a function that moves the first node to the end of the list and returns the new head.

Lists with fewer than two nodes come back unchanged.

Your task is to complete the function struct node *rotate_forward(struct node *head), whose behaviour is described above. This is the only code you need to write; it will be called directly during marking.

Testing

prac_q60.c also contains a main function which allows you to test your function. It reads its input from standard input — exactly the lines shown being typed in the session below — then calls your function and prints the result. You type the input directly at the keyboard (or redirect a file into the program); nothing is passed on the command line.

Do not change this main function. If you want to change it, you have misread the question.

Your function will be called directly during marking. The main function is only to let you test your function.

Here is how the main function allows you to test prac_q60.c:

gcc -Wall -Wextra -o prac_q60 prac_q60.c
./prac_q60
5
1 2 3 4 5
2 3 4 5 1

./prac_q60
2
7 8
8 7

./prac_q60
1
9
9