Question 1

(●◌◌◌)

:

Passing this question, or question 3, is sufficient to pass the linked lists hurdle.

(12 marks)

prac_q1.c uses the following familiar data type:

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

Your task is to add code to the function count_in_range. count_in_range is given one argument, head, which is a pointer to the first node of a linked list.

Add code to count_in_range so that it returns the count of how many nodes in the list have a value strictly between the first and the last nodes in the list.

For example, if the linked list contains these values:

2 -> 10 -> 5 -> 2 -> 7 -> 12 -> X

count_in_range should return 3, because:

• The first value is 2.
• The last value is 12.
• The middle node with value 2 equals the first node's value and is not counted.
• The values strictly between 2 and 12 are 10, 5, and 7.

For example, if the linked list contains these values:

12 -> 10 -> 11 -> 13 -> 14 -> X

count_in_range should return 1, because:

• The first value is 12.
• The last value is 14.
• The values strictly between 12 and 14 are 13.

If the list has fewer than three nodes, the function should return 0, as there are no nodes in a range. If the list is empty, it should return 0.

Testing

prac_q1.c also contains a main function which allows you to test your count_in_range function.

This main function:

• Converts the command-line arguments to a linked list.
• Assigns a pointer to the first node in the linked list to head.
• Calls count_in_range(head).
• Prints the result.

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

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

Here is how the main function allows you to test count_in_range:

dcc -o prac_q1 prac_q1.c
./prac_q1 2 10 5 2 7 12
3
./prac_q1 10 2 5 3
0
./prac_q1 5 7 10
1
./prac_q1 1 10 1 10 1
0
./prac_q1 10 1 10 1 10
0
./prac_q1 5 10
0
./prac_q1 7
0
./prac_q1
0

Assumptions/Restrictions/Clarifications

• count_in_range should return a single integer.
• A node whose value equals the first or last node's value is not counted — only values strictly between (exclusive) those two values are counted.
• If the first node's value is greater than or equal to the last node's value, count_in_range should return 0.
• count_in_range should not change the linked list it is given.
• count_in_range should not use arrays.
• count_in_range should not call malloc.
• count_in_range should not call scanf (or getchar or fgets).
• count_in_range should not print anything. It should not call printf.
• Do not change the supplied main function. It will not be tested or marked.

Question 2

(●◌◌◌)

:

Passing this question, or question 4, is sufficient to pass the arrays hurdle.

(12 marks)

sum_after_even, given a two-dimensional array of integers, should return a total sum calculated based on the position of the first even number in each row.

sum_after_even will be passed a two-dimensional array with:

• num_rows rows and,
• NUM_COLS (#define'd to 5) columns.

For each row, your function must:

1. Find the first even number in that row.
2. Add all values that appear after the first even number in the row to the total sum.
3. If a row has no even numbers, it contributes 0 to the total.
4. If the first even number is the very last element in the row, that row contributes 0 to the total.

Examples

For example, if the 2D array contains these elements:

[1, 3, 2, 5, 7],
[1, 1, 1, 1, 1]

Your function should return 12:

1. Row 0: First even number is 2 at index 2. The values after are 5 and 7, which sum to 12.
2. Row 1: No even numbers, which sum to 0.
3. Final total: 12 + 0 = 12.

For example, if the 2D array contains these elements:

[4, 1, 1, 1, 1],
[3, 5, 7, 9, 2]

Your function should return 4:

1. Row 0: First even number is 4 at index 0. The values after are 1, 1, 1, 1, which sum to 4.
2. Row 1: First even number is 2 at index 4. There are no values after index 4, which sums to 0.
3. Final total: 4 + 0 = 4.

Assumptions/Restrictions/Clarifications.

• sum_after_even should return a single integer.
• sum_after_even should not change the array it is given.
• sum_after_even should not call scanf (or getchar or fgets).
• sum_after_even can assume the array contains at least one row.
• Array elements may be negative. A negative even number (e.g. -2) is still considered even. A negative odd number (e.g. -3) is still considered odd.
• 0 is considered even.
• sum_after_even function should not print anything. It should not call printf.
• Your submitted file may contain a main function. It will not be tested or marked.

Question 3

(●●◌◌)

:

Passing this question, or question 1, is sufficient to pass the linked lists hurdle.

(12 marks)

prac_q3.c uses the following familiar data type:

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

The function insert_between_diff is given two arguments, value and head, where head is a pointer to the first node in a linked list.

Add code to insert_between_diff to create a new node (using malloc) containing value and insert it after the first occurrence of two consecutive nodes where the absolute difference between their data is 6 or 7.

insert_between_diff should return a pointer to the head of the list.

In the case that the list is empty, insert_between_diff should return a pointer to the new node containing value.

If no two consecutive nodes have a difference of 6 or 7, the new node containing value should be inserted at the tail of the list.

For example, if value is 99 and the linked list contains these 4 elements:

1 -> 8 -> 2 -> 3 -> X

The first occurrence where the difference is 6 or 7 is between 1 and 8 (∣1 − 8∣ = 7). The value 99 is inserted between them, resulting in:

1 -> 99 -> 8 -> 2 -> 3 -> X

If the value is 19 and the linked list contains these 4 elements:

1 -> 2 -> 1 -> 2 -> X

There are no consecutive nodes with a difference of 6 or 7, so the 19 is inserted at the tail of the list, resulting in:

1 -> 2 -> 1 -> 2 -> 19 -> X

If the value is 8 and the linked list contains these 4 elements:

1 -> 3 -> 9 -> 16 -> X

The first occurrence where the difference is 6 or 7 is between 3 and 9 (∣3 − 9∣ = 6). The value 8 is inserted between them, resulting in:

1 -> 3 -> 8 -> 9 -> 16 -> X

Testing

prac_q3.c also contains a main function which allows you to test your insert_between_diff function.

This main function:

• Converts the command-line arguments to a linked list.
• Assigns a pointer to the first node in the linked list to head.
• Reads an integer from standard input and assigns it to value.
• Calls insert_between_diff(value, head).
• Prints the result.

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

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

dcc prac_q3.c -o prac_q3
./prac_q3 1 8 2 3
99
[1, 99, 8, 2, 3]
./prac_q3 10 6 1 8
9
[10, 6, 1, 9, 8]
./prac_q3 1 2 1 2
19
[1, 2, 1, 2, 19]
./prac_q3 5
3
[5, 3]

Assumptions/Restrictions/Clarifications.

• insert_between_diff should not use arrays.
• insert_between_diff should not call scanf (or getchar or fgets).
• insert_between_diff should not print anything. It should not call printf.
• If there are no consecutive nodes meeting the condition, the new node should be added to the end (tail) of the list.
• You may use the abs() function from stdlib.h to calculate differences.
• Do not change the supplied main function. It will not be tested or marked.

Question 4

(●●◌◌)

:

Passing this question, or question 2, is sufficient to pass the arrays hurdle.

(12 marks)

Your first_sorted_row function should determine if there exists a row in a 2D array where the elements are in strictly increasing order.

first_sorted_row will be passed:

• num_rows: the number of rows in the 2D array
• array: the two-dimensional array of integers (with NUM_COLS columns)

Add code so that the first_sorted_row function searches for the first row where every element is strictly greater than the element to its left. If such a row exists, return the index of that row. If no such row exists, return -1.

For example, if the 2D array has 4 rows and contains the following elements:

[10, 5, 8, 2,  1],
[ 1, 2, 3, 4,  5],
[ 2, 4, 6, 8, 10],
[ 5, 5, 5, 5,  5],

the function should return 1, because row 1 (1, 2, 3, 4, 5) is the first row where each element is strictly increasing.

For example, if the 2D array has 3 rows and contains the following elements:

[1, 2, 2, 3, 4],
[5, 4, 3, 2, 1],
[9, 8, 7, 6, 5],

the function should return -1, because no row is strictly increasing. Note that row 0 is not strictly increasing because 2 is not strictly greater than 2.

For example, if the 2D array has 2 rows and contains the following elements:

[10, 20, 30, 40, 50],
[ 1,  2,  3,  4,  5],

the function should return 0, because the very first row is strictly increasing.

Testing

prac_q4.c also contains a simple main function which allows you to test your first_sorted_row function.

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

Assumptions/Restrictions/Clarifications.

• first_sorted_row should return a single integer (the index or -1).
• first_sorted_row should not change the array it is given.
• first_sorted_row should not call scanf (or getchar or fgets).
• first_sorted_row should not print anything. It should not call printf.
• You may assume that num_rows will always be at least 1.
• The number of columns is fixed by the constant NUM_COLS.
• Your submitted file may contain a main function. It will not be tested or marked.

Question 5

(●◌◌◌)

:

(5 marks)

You have been provided with a file called prac_q5.c.

The code in prac_q5.c is meant to do the following:

1. Scan in 3 buses along with their bus number, maximum passenger capacity and current number of passengers. Storing the data in an array of type struct bus.
2. Scan in the number of passengers waiting for a bus.
3. Determine which buses have enough space for all the passengers.

Unfortunately, there are some problems with the provided program. Once fixed, your program should match the following examples exactly:

Examples

dcc prac_q5.c -o prac_q5
./prac_q5
Enter 3 buses and their information: 
Bus 1: 
Bus number: 370
Maximum capacity: 80
Current number of passengers: 35
Bus 2: 
Bus number: 380
Maximum capacity: 50
Current number of passengers: 10
Bus 3: 
Bus number: 390
Maximum capacity: 75
Current number of passengers: 60
How many passengers are waiting for the bus: 40
Checking bus capacity...
Buses that have enough space:
370
380
./prac_q5
Enter 3 buses and their information: 
Bus 1: 
Bus number: 120
Maximum capacity: 20
Current number of passengers: 15
Bus 2: 
Bus number: 150
Maximum capacity: 50
Current number of passengers: 50
Bus 3: 
Bus number: 180
Maximum capacity: 30
Current number of passengers: 29
How many passengers are waiting for the bus: 6
Checking bus capacity...
Oh no! None of the 3 buses have enough space!

There are currently a number of issues in the code that you must fix for the code to work correctly, and produce the desired output. This may include changing lines, moving lines, or removing lines. Submit your working version of the code.

Assumptions/Restrictions/Clarifications.

• If multiple buses, but not all buses have enough space for the waiting passengers, they should be printed in the order they were inputted.
• You may assume that all bus numbers entered will be unique.

Question 6

(●◌◌◌)

:

(5 marks)

You have been provided with a file called prac_q6.c.

The code in prac_q6.c is meant to do the following:

• take a double as input from the user representing some temperature in Kelvin,
• pass it to a function to convert the value into its equivalent temperature in Celsius (Celsius = Kelvin - 273.15),
• store the resulting value in a Celsius pointer variable, and
• print both the Kelvin and Celsius to 2 decimal places in the main function.

However, it has some issues that you need to fix.

Once fixed, your program should match the following example exactly:

dcc prac_q6.c -o prac_q6
./prac_q6
Enter temperature in Kelvin: 273.15
273.15 Kelvin is equal to 0.00 Celsius.
./prac_q6
Enter temperature in Kelvin: 300
300.00 Kelvin is equal to 26.85 Celsius.
./prac_q6
Enter temperature in Kelvin: 373.15
373.15 Kelvin is equal to 100.00 Celsius.
./prac_q6
Enter temperature in Kelvin: 0
0.00 Kelvin is equal to -273.15 Celsius.

There are currently a number of issues in the code that you must fix for the code to work correctly, and produce the desired output. This may include changing lines, adding lines, or removing lines. Submit your working version of the code.

Assumptions/Restrictions/Clarifications.

• You can assume that the given Kelvin value will be a valid double.
• You must not modify the prototype of void kelvin_to_celsius(double kelvin, double *celsius).

Question 7

(●◌◌◌)

:

(5 marks)

You have been provided with a file called prac_q7.c.

The code in prac_q7.c is meant to do the following:

• Scan in a string.
• Scan in a position for a character in the string.
• Remove the character from that position in the string.
• Print the updated string to the terminal.

Testing

Once fixed, your program should match the following example exactly:

dcc prac_q7.c -o prac_q7
./prac_q7
Enter a string: abcd
Enter a position to remove: 1
Result: bcd
./prac_q7
Enter a string: abcd
Enter a position to remove: 2
Result: acd
./prac_q7
Enter a string: abcd
Enter a position to remove: 3
Result: abd
./prac_q7
Enter a string: abcd
Enter a position to remove: 4
Result: abc
./prac_q7
Enter a string: The quick brown fox jumped over the lazy dog.
Enter a position to remove: 4
Result: Thequick brown fox jumped over the lazy dog.

There are currently a number of issues in the code that you must fix for the code to work correctly, and produce the desired output. This may include changing lines, adding lines, or removing lines. Submit your working version of the code.

Assumptions/Restrictions/Clarifications

• The input string will contain at least two characters.
• The position entered will correspond to a character in the string.

Question 8

(●◌◌◌)

:

(5 marks)

You have been provided with a file, prac_q8.c.

The code in list_delete_min is given one argument, head, which is a pointer to the first node of a linked list, and uses the following familiar data structure:

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

list_delete_min is intended to modify a linked list such that all instances of the minimum value in the list are removed. Thus, the program should find the minimum value in the linked list and then remove all instances of the minimum value in the list (deleted from the list and its memory freed). Once all instances are removed, list_delete_min should return a pointer to the head of the list.

For example, if the linked list contained the following values:

1 -> 2 -> 3 -> 1 -> 4 -> 5 -> 6 -> NULL

list_delete_min should return a pointer to the head of the following list:

2 -> 3 -> 4 -> 5 -> 6 -> NULL

This occurs because 1 is the smallest value in the list so the nodes containing 1 at positions 1 and 4 are removed.

Testing

prac_q8.c also contains a main function which allows you to test your list_delete_min function.

This main function:

• Converts the command-line arguments to a linked list,
• assigns a pointer to the first node in the linked list to head,
• calls list_delete_min(head),
• prints the resulting list.

Do not change this main function. This main function does not contain any bugs.

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

dcc prac_q8.c --leak-check -o prac_q8
./prac_q8 1 2 3 4 5
BEFORE: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
AFTER: 2 -> 3 -> 4 -> 5 -> NULL
./prac_q8 8 3 -2 -2 0 5 -2
BEFORE: 8 -> 3 -> -2 -> -2 -> 0 -> 5 -> -2 -> NULL
AFTER: 8 -> 3 -> 0 -> 5 -> NULL
./prac_q8 3 3 3 3
BEFORE: 3 -> 3 -> 3 -> 3 ->NULL
AFTER: NULL
./prac_q8 8
BEFORE: 8 -> NULL
AFTER: NULL
./prac_q8 
BEFORE: NULL
AFTER: NULL

There are currently a number of issues in the code that you must fix for the code to work correctly, and produce the desired output. This may include changing lines, adding lines, or removing lines. Submit your working version of the code.

Assumptions/Restrictions/Clarifications.

• Do not change the definition of struct node.
• list_delete_min should call free to free the memory of any nodes it deletes and must pass --leak-check.
• list_delete_min should return the new head of the list (it may change if the original head is deleted).
• The list may be empty (head may be NULL).
• If the list contains only one node, the value at that node is the minimum and therefore should be removed.
• Do not print anything in the list_delete_min function. The function should not call printf.
• Do not call scanf, getchar, fgets or otherwise read input inside your function.
• list_delete_min should not use arrays.
• Do not change the supplied main function. It will not be tested or marked.

Question 9

(●●●◌)

:

(11 marks)

Write a C program prac_q9.c that scans a target word and a string, then removes every occurrence of that target word from the string.

A word is defined as a contiguous sequence of non-whitespace characters (the sequence of non-whitespace characters are all next to each other). The comparison is case-sensitive.

The program should output the remaining words in their original order, separated by a single space, with no leading or trailing whitespace.

For example, if the target word is hello and the input string is hello world hello, the program will output world.

• The first word is "hello", which matches the target, so it is removed.
• The second word is "world", which does not match the target, thus it is kept.
• The third word is "hello", which matches the target, so it is removed.

In another example, if the target word is a and the input string is a b a c b, the program will output b c b.

• The first word is "a", which matches the target, so it is removed.
• The second word is "b", which does not match the target, thus it is kept.
• The third word is "a", which matches the target, so it is removed.
• The fourth word is "c", which does not match the target, thus it is kept.
• The fifth word is "b", which does not match the target, thus it is kept.

In another example, if the target word is the and the input string is The cat and the Cat, the program will output The cat and Cat.

• The first word is "The", which does not match the target "the" (capital T vs lowercase t), thus it is kept.
• The second word is "cat", which does not match the target, thus it is kept.
• The third word is "and", which does not match the target, thus it is kept.
• The fourth word is "the", which exactly matches the target, so it is removed.
• The fifth word is "Cat", which does not match the target (capital C vs lowercase c), thus it is kept.

Examples

dcc prac_q9.c -o prac_q9
./prac_q9
hello
hello world hello
world
./prac_q9
a
a a a

./prac_q9
the
The cat and the Cat
The cat and Cat
./prac_q9
hello
hello hhelloo hello
hhelloo
./prac_q9
COMP1511
x y COMP1511 comp1511 COMP1511
x y comp1511

Assumptions/Restrictions/Clarifications

• The target word will not exceed 4096 characters in length.
• The input line will not exceed 4096 characters in length.
• Only words that exactly match the target word are removed. Words that merely contain the target as a substring are kept.
• If all words are removed (or the string is empty or only whitespace), the program should print a single newline for the outputted string.
• The output string should not have any leading or trailing spaces.
• You cannot use the string.h library. If you do so, you will receive a 0 in this question.

Question 10

(●●●◌)

:

(11 marks)

You are planning your course progression at university. There are a total of num_courses courses you need to complete, labelled from 0 to num_courses - 1. Some courses have prerequisites, meaning you must complete certain courses before you can take others. Your task is to determine a valid ordering in which to complete all courses.

The first command line argument (after the program name) is num_courses, the total number of courses. The remaining arguments are provided as pairs in the format: a1 b1 a2 b2 ...

• Each pair [ai, bi] indicates that you must complete course bi before you can take course ai.

Your program should print a valid ordering of all courses in the format Order: [c1, c2, ...]. If there are multiple valid orderings, always take the lowest-numbered available course first. If it is impossible to complete all courses, your program should print Order: [].

For example if you were provided the following input: 4 1 0 2 0 3 1 3 2 This input has num_courses = 4. The courses that need to be taken are course 0, course 1, course 2 and course 3. The pairs then provide you with the prerequisite requirements:

• Prerequisite: [1, 0]
  • To take course 1, you must first complete course 0.
• Prerequisite: [2, 0]
  • To take course 2, you must first complete course 0.
• Prerequisite: [3, 1]
  • To take course 3, you must first complete course 1.
• Prerequisite: [3, 2]
  • To take course 3, you must first complete course 2.

Course 0 has no prerequisites, so it is taken first. Then courses 1 and 2 both become available, and since we always take the lowest-numbered course first, we take course 1 next, then course 2. Finally, course 3 can be taken since both of its prerequisites are complete.

The resulting ordering is: [0, 1, 2, 3].

Examples

dcc prac_q10.c --leak-check -o prac_q10
./prac_q10 4 1 0 2 0 3 1 3 2
Order: [0, 1, 2, 3]
./prac_q10 4 1 0 3 0 2 1
Order: [0, 1, 2, 3]
./prac_q10 2 1 0
Order: [0, 1]
./prac_q10 1
Order: [0]
./prac_q10 2 1 0 0 1
Order: []

You may find the following interactive helpful for visualising course dependencies:

Assumptions/Restrictions/Clarifications.

• If multiple courses have no remaining prerequisites, always take the lowest-numbered course first.
• As soon as a course is completed, any course whose only remaining prerequisite was that course immediately becomes available for selection.
• If circular dependencies exist (e.g. course A requires B and course B requires A), it is impossible to complete all courses and the output should be Order: [].
• All course numbers are integers in the range 0 to num_courses - 1.
• There may be zero prerequisites (only num_courses is provided).
• There is no maximum number of courses or prerequisites.
• The program will always be provided valid input in the correct format.
• Your code must pass --leak-check with no memory leaks.

Question 11

(●●●●)

:

(10 marks)

You are given a collection of boxes, where each box has a width and a height. Your task is to determine the maximum number of boxes that can fit inside each other, like Russian dolls.

A box can fit inside another box if and only if both the width and the height of the inner box are strictly less than the width and height of the outer box. You cannot rotate a box.

The dimensions of each box are provided as command line arguments in the format: w1 h1 w2 h2 ... wi hi ...

• wi is the width of the i^th box.
• hi is the height of the i^th box.

Your program should print the maximum number of boxes that can be nested in the format:

Max boxes: N

where N is the result.

For example, if you were provided the following input 5 4 6 4 6 7 2 3, you would interpret it as:

• Box 1: [5, 4]
  • Width = 5
  • Height = 4
• Box 2: [6, 4]
  • Width = 6
  • Height = 4
• Box 3: [6, 7]
  • Width = 6
  • Height = 7
• Box 4: [2, 3]
  • Width = 2
  • Height = 3

In this case:

• Box 4 [2, 3] fits inside Box 1 [5, 4] because Box 4's width of 2 is strictly less than Box 1's width of 5, and Box 4's height of 3 is strictly less than Box 1's height of 4.
• Box 1 [5, 4] fits inside Box 3 [6, 7] because Box 1's width of 5 is strictly less than Box 3's width of 6, and Box 1's height of 4 is strictly less than Box 3's height of 7.
• However, Box 1 [5, 4] does not fit inside Box 2 [6, 4] because although Box 1's width of 5 is strictly less than Box 2's width of 6, the heights are equal (4 is not strictly less than 4).

Thus, the longest chain of nested boxes is: Box 4 [2, 3] -> Box 1 [5, 4] -> Box 3 [6, 7], giving a maximum of 3.

Examples

dcc prac_q11.c --leak-check -o prac_q11
./prac_q11 5 4 6 4 6 7 2 3
Max boxes: 3
./prac_q11 1 1 1 1 1 1
Max boxes: 1
./prac_q11 1 2 3 4 5 6 7 8
Max boxes: 4

You may find the following interactive helpful for visualising nested boxes:

Assumptions/Restrictions/Clarifications.

• A box can only fit inside another if both of its dimensions are strictly greater (not equal to) the other box.
• You cannot rotate a box (you cannot swap the width and height of a box).
• Boxes can be entered in any order.
• There is no maximum number of boxes.
• You will always be given at least one box.
• All widths and heights are positive integers (greater than 0).
• The program will always be provided valid input in the correct format.
• Your code must pass --leak-check with no memory leaks.