Question 1

(●◌◌◌)

:

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

(12 marks)

You have been given prac_q1.c, which contains a function count_favourite.

count_favourite is given one argument, head, which is the pointer to the first node in a linked list.

Add code to count_favourite so that its returns the number of elements divisible by 17 in the list.

For example if the linked list contains these 8 elements:

51, 7, 8, 9, 34, 19, 34, 42

count_favourite should return 3 because 51, 34 and 34 are divisible by 17.

Testing

prac_q1.c also contains a main function which allows you to test your count_favourite 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_favourite(head) - prints the result.

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

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

Examples

Here is how you use main function allows you to test prac_q1:

dcc prac_q1.c -o prac_q1
./prac_q1 51 7 8 9 34 19 34 42
3
./prac_q1 2 4 6 5 8 9
0
./prac_q1 17 34 51 68 85 102 119 136 153
9
./prac_q1
0

Assumptions/Restrictions/Clarifications

• count_favourite should return a single integer.
• count_favourite should not change the linked list it is given.
• Your function should not change the next or data fields of list nodes.
• count_favourite should not use arrays.
• count_favourite should not call malloc.
• count_favourite should not call scanf (or getchar or fgets).
• count_favourite 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)

count_neutral_rows will be passed a two dimensional array with 4 rows and length columns. Add code so that count_neutral_rows returns the number of neutral rows in the array. A neutral row is a row that adds up to 0.

Examples

If the array contains these elements:

{16, 16, 16, 16, 16},
{2,   2,  2, -4, -2},
{2,  -2,  1, -4,  3},
{2,   2,  1, -3, -2},

Your function should return 3, since every row except the first adds up to 0.

For example if the array contains these elements:

{17},
{2},
{0},
{4-},

Your function should return 1, because only the third row adds up to 0.

Testing

prac_q2.c also contains a simple main function which allows you to test your count_neutral_rows function.

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

Assumptions/Restrictions/Clarifications.

Your function should return a single integer; between 0 and 4 (inclusive).

count_neutral_rows should not change the array it is given.

count_neutral_rows should not call scanf (or getchar or fgets).

count_neutral_rows can assume the array always has 4 rows, and has at least 1 column.

count_neutral_rows should not print anything. It should not call printf.

Your starter code contains a main function. You can change it for your own testing, but it will not be autotested or marked.

Question 3

(●●◌◌)

:

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

(12 marks)

You have been given prac_q3.c, which contains a function delete_negatives.

Given a linked list, your task is to delete any nodes which have a value strictly less than 0. Any nodes which are deleted must be properly free’d. 

This program uses the familiar data type below

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

prac_q3 is given a pointer to a linked list.

prac_q3 should return a pointer to the head of the linked list.

Only this specific function will be called in marking, the main function is only provided for your testing, however you can create more functions if it is helpful.

Your function should operate normally with an empty linked list.

Your function should not change the list if there are no negative numbers within the list.

You function should not call malloc.

Your function should not have any memory leaks and should pass a leak-check.

For example, if the linked list had the values

Head => [3, 4, -5, 10, -10]

Your function should return a pointer to a linked list with the following values

Head => [3, 4, 10]

Additionally, if the linked list had the values

Head => [-2, -2, 6]

Your function should return a pointer to a linked list with the following values

Head => [6]

Examples

dcc prac_q3.c -o prac_q3
./prac_q3
4 -> -2 -> 6 -> X
4 -> 6 -> X

Question 4

(●●◌◌)

:

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

(12 marks)

You have been given prac_q4.c, which contains a function find_duplicate.

find_duplicate should find the duplicate value in the given array, if one exists.

The array will either contain no duplicate values, or a single value in the array will be duplicated, i.e will occur more than once.

find_duplicate should take two parameters: the length of the array, and the array itself.

find_duplicate should return a single integer: the value in the array that occurs more than once. if one exists.

If there are no values that occur more than once, find_duplicate should return NO_DUPLICATE.

For example, if the array contained the following 6 elements:

3, 1, 4, 1, 5, 9

find_duplicate should return the integer 1, as this is the element that occurred more than once.

As another example, if the array contained the following 6 elements:

17, 17, 17, 17, 16, 17

find_duplicate should return the integer 17, as this is the element that occurred more than once.

As another example, if the array contained the following 6 elements:

1, 2, 3, 4, 5, 6

find_duplicate should return NO_DUPLICATE, as none of the elements in the array occurred more than once.

Testing

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

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

Assumptions/Restrictions/Clarifications.

You cannot assume anything about the number of times the duplicate value occurs, i.e. there may not be any duplicates, or conversely, the entire array may be the same value.

find_duplicate should return a single integer.

find_duplicate should not change the array it is given.

find_duplicate should not call scanf (or getchar or fgets).

find_duplicate can assume the array contains at least one integer.

find_duplicate can assume the array contains only positive integers.

find_duplicate 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 5

(●◌◌◌)

:

(5 marks)

The code provided in prac_q5.c is meant to

• ask the user to enter a string,
• print out what the user has entered, then
• repeat this until the user enters Ctrl + d.

So for example, for the following inputs, the program should output exactly what has been shown:

dcc prac_q5.c -o prac_q5
./prac_q5
Enter string: hello
Input received: hello
Enter string: bye
Input received: bye
Enter string: 
./prac_q5
Enter string: 

There are currently three lines with issues in the provided code that you must fix for the code to work correctly to produce the desired output. Submit your working version of the code.

Question 6

(●◌◌◌)

:

(5 marks)

The code provided in prac_q6.c is meant to read in a length, followed by an array of integers of the given length from the user. It should then find the minimum and maximum values in the array.

Examples

dcc prac_q6.c -o prac_q6
./prac_q6
How many numbers: 5
Please enter numbers: -6 3 0 7 9
Minimum: -6
Maximum: 9
./prac_q6
How many numbers: 1
Please enter numbers: 1
Minimum: 1
Maximum: 1
./prac_q6
How many numbers: 0
Please enter numbers:

There are currently five lines with issues in the code that you must fix for the code to work correctly to produce the desired output. Submit your working version of the code.

Question 7

(●◌◌◌)

:

(5 marks)

The following code is meant to increment the time of 3 days, 4 hours and 59 minutes represented in a `struct time` variable and print out the resulting time:

dcc prac_q7.c -o prac_q7
./prac_q7
One minute ago: 3 days, 4 hours and 59 minutes
Now: 3 days, 5 hours and 0 minutes

There are currently nine lines with issues in the code that you must fix for the code to work correctly to produce the desired output. Submit your working version of the code.

Question 8

(●◌◌◌)

:

(5 marks)

The following code is meant to ask the user to enter a size, followed by size many numbers for a linked list. The last element of the linked list is removed, then the resulting list is printed out. The size of the list can be anywhere between 0 and 100.

For example:

dcc prac_q8.c -o prac_q8
./prac_q8
Total numbers: 4
4 3 2 1
4 -> 3 -> 2 -> X
./prac_q8
Total numbers: 1
1
X
./prac_q8
Total numbers: 0
X

There are currently a number of issues in the code (specifically in the delete_last function) 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.

Question 9

(●●●◌)

:

(11 marks)

Write a C program prac_q9.c which reads two lines of input.

It should then print a single integer between 0 and 26 inclusive.

This should be a count of how many letters occur in both lines.

The case of letters should be ignored (for example, if 'A' occurs in the first line and 'a' in the second line this counts as occurring in both lines).

For example:

 dcc prac_q9.c -o prac_q9
./prac_q9
hello world
World Hello
7
./prac_q9
hello
OLLEH
4
./prac_q9
likeable
possums
0
./prac_q9
likeable
echidnas
3
./prac_q9
AbCd
ABcD
4
./prac_q9
AbCdAbCdAbCdAbCd
cBADcBAD
4
./prac_q9
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaargh
ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha
2
./prac_q9
abcdefghijklmnopqrstuvwxyz
ZYXWVUTSRQPONMLKJIHGFEDCBA
26

Assumptions/Restrictions/Clarifications.

Your program should print a single integer and nothing else.

This integer should in the range 0..26 inclusive.

You can assume each line contains no more than 256 characters.

You can assume your input always contains two lines.

No error checking is necessary.

You are free to write this program in any way you wish: there is no specific function that you need to implement. Note that your program will need to have a `main` function.

Question 10

(●●●◌)

:

(11 marks)

"Snap!" is a popular card game where players go around in a circle, placing playing cards from their "hand" (the stack of cards they are holding) into a pile of cards in the centre. If the card placed matches the card currently at the top of the pile, then the first player to shout "Snap!" claims the pile, and adds it to the bottom of their hand.

In this question, we will write a program to simulate a restricted game of Snap. In our version of snap, there will only be 2 players, and the "cards" will be represented by integers (provided by the players at the start of the game). The provided code already scans in until a -1 is read, and creates 2 linked lists of struct cards. The given linked lists will have the first card entered as the head of that linked list.

struct card {
    int num;
    struct card *next;
};

Your task for this program is to simulate the game, up until the first "snap" occurs, or one player loses. Starting with Player 1, each player should take turns placing the card from the top of their hand onto the pile. When a "snap" occurs, you must print the message "Snap! Matched card X" (where "X" is the value of the matched card), and end the program, printing out the contents of the two players' hands, and the contents of the pile, using the provided print_deck function.

If the game ends before a snap has occured, (i.e when one player has no cards remaining in their hand), your program should print the message "Player X has won!" (where "X" is the player whose hand still has cards remaining), before printing the contents of both decks and the pile.

Some examples follow:

dcc prac_q10.c -o prac_q10
./prac_q10
Enter Player 1's deck values:
1 2 3 -1
Enter Player 2's deck values:
9 2 8 -1
Snap! Matched card 2
Player 1's deck: 3 -> X
Player 2's deck: 8 -> X
Pile: 2 -> 2 -> 9 -> 1 -> X

The following diagram shows the operation of the previous example:

./prac_q10
Enter Player 1's deck values:
1 2 2 1 -1
Enter Player 2's deck values:
1 2 3 2 -1
Snap! Matched card 1
Player 1's deck: 2 -> 2 -> 1 -> X
Player 2's deck: 2 -> 3 -> 2 -> X
Pile: 1 -> 1 -> X
./prac_q10
Enter Player 1's deck values:
1 3 2 -1
Enter Player 2's deck values:
9 2 8 -1
Snap! Matched card 2
Player 1's deck: X
Player 2's deck: 8 -> X
Pile: 2 -> 2 -> 3 -> 9 -> 1 -> X
./prac_q10
Enter Player 1's deck values:
1 -1
Enter Player 2's deck values:
2 2 -1
Player 2 has won!
Player 1's deck: X
Player 2's deck: 2 -> 2 -> X
Pile: 1 -> X

Assumptions/Restrictions/Clarifications

• You can assume that BOTH player's hands will contain cards initially.
• Player One will always go first
• The -1 scanned at the end of each hand should NOT be included in the hand.

Question 11

(●●●●)

:

(10 marks)

The Trouble with Tribonacci

The Tribonacci series is very similar to the Fibonacci series. The only difference between the two is that in the Tribonacci series, you add the previous three terms instead of the previous two.

The first three values in the Tribonacci series are, by definition, 1.

After the first three values each value is the sum of the previous three.

Hence, the Tribonacci series commences: 1,1,1,3,5,9,17,31,57,105, ...

Write a C program prac_q11.c which prints the n-th member of the Tribonacci series.

Unfortunately, the Tribonacci series grows quickly and your program may be asked to calculate any of the first 5000 Tribonacci values.

This means the values that your program must calculate are far too large to fit in any standard C numeric data type.

Make your program behave exactly as indicated by the examples below.

./prac_q11 10
105
./prac_q11 42
30883847113
./prac_q11 100
69087442470169316923566147
./prac_q11 500
500237804560509131893591727526401989182661042205677906540392389451576520114592708719307417633802136063199710847361660727835027581923
./prac_q11 1000
1056569942836970422279284954750098236519342255152919675406067018213960747393817667095588725995948973722417422227477589614070393820954716814070302286673551230293560940674846367367520224538342482630207080905846768675790903553645664897731604869996342518016379904334431

Assumptions/Restrictions/Clarifications

The only C numeric data type you are permitted to use is int. You are not permitted to use other integer data types such as long or long long. You are not permitted to use floating point data types such as double.

You are permitted to use arrays.

Partial marks will be only be given to approaches which would calculate and print large values (n >= 500) of the Tribonacci series exactly.

No marks will be given for approaches which calculate the smaller Tribonacci sequence values (n < 500) which fit in an int variable (or a long variable or long long variable).

No marks will be given for calculating approximating sequence values e.g. using double.

You are permitted to use the functions printf, atoi and exit. You are not permitted to use any other library functions, from the standard C library or any other library.

Your answer may be penalized if it takes more than 60 seconds to calculate a Tribonacci number, when compiled with dcc --valgrind.

You can assume your program is given exactly one argument, an integer between 1 and 5000 inclusive.

You can assume that the largest Tribonacci value you will be asked to calculate has at most 1500 digits.

No error-checking is necessary.