Question 1

(●◌◌◌)

:

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

(12 marks)

Note prac_q1.c uses the following familiar data type:

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

product is given two arguments, head1 and head2, which are pointers to the first node of linked lists.

product should return the sum of the elements in the first list multiplied by the corresponding element in the second list.

If one list is longer than the other, the extra elements should be ignored.

For example, if the two lists contain these values:

list1: 3, 1, 4, 1, 5, 9

list2: 2, 7, 9

product should return 49, because 3 * 2 + 1 * 7 + 4 * 9 = 49 .

For example, if the two lists contain these values:

list1: 2, 7

list2: 4, 42, 4242, 4242, 4242424242

product should return 302, because 2 * 4 + 7 * 42 = 302.

Testing

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

This main function:

• uses a command line argument of "-" to separate the values for two linked lists.
• converts the command-line arguments before the "-" to a linked list
• assigns a pointer to the first node in the linked list to head1
• converts the command-line arguments after the "-" to a linked list
• assigns a pointer to the first node in the linked list to head2
• calls product(head1, head2)
• prints the result.

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

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

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

dcc prac_q1.c -o prac_q1
./prac_q1 3 1 4 1 5 9 - 2 7 9 8
57
./prac_q1 16 7 8 12 - 13 19 21 12
653
./prac_q1 2 4 6 - 42
84
./prac_q1 - 1 2 3 4
0
./prac_q1 4 3 2 1 -
0
./prac_q1 -
0

Assumptions/Restrictions/Clarifications.

The lists may be different lengths.

The data fields of the lists may contain any integer.

product should return only a single integer.

product should not change the linked lists it is given.

product should not change the next or data fields of list nodes.

product should not use arrays.

product should not call malloc.

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

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

Do not change the definition of struct node.

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_netral_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)

Note prac_q3.c uses the following familiar data type:

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

mixed is given one argument: head a pointer to the first node of a linked list.

mixed should return 1 if the linked list contains both even and odd numbers, and return 0 otherwise.

For example if the linked list contains these elements:

16, 12, 8, 3, 6, 12

mixed should return 1, because the linked list contains 3 which is odd and 16 which is even.

For example if the linked list contains these elements:

16, 12, 8, 6, 12

mixed should return 0, because the linked list contains only even numbers.

Testing

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

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

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

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

dcc prac_q3.c -o prac_q3
./prac_q3 3 1 4
1
./prac_q3 3 1
0
./prac_q3 2 4 6 42
0
./prac_q3 1 2 3 4
1
./prac_q3 42
0
./prac_q3
0

Assumptions/Restrictions/Clarifications.

mixed should return only a single integer and this integer must one of two values: 1 or 0.

mixed should not change the linked list it is given.

mixed should not change the next or data fields of list nodes.

mixed should not use arrays.

mixed should not call malloc.

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

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

Do not change the definition of struct node.

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)

Write a C program prac_q4.c which reads integers from standard input until a 0 is scanned.

It should then print out every integer at an even index (that is, at index 0, 2, 4, ...), and then print out every integer at an odd index (that is, at index 1, 3, 5, ..). It should not print out the final 0.

Your program must exactly match the output below:

./prac_q4
44
3
42
5
49
100
0
44 42 49 3 5 100
./prac_q4
1
2
3
4
5
0
1 3 5 2 4

You can assume at least 1 integer will be entered before the final zero.

You can assume at most 10000 integers will be entered before the final zero.

You can assume an integer will be repeated before end-of-input is reached.

You can assume the only input to your program will be integers one per line.

Your program should not access command-line arguments (argc, argv).

Your program should only produce a single line of output.

You can assume no integer will be smaller than 1, except for the final zero.

No error checking is necessary.

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.