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)

In this task, you will determine the average capacity of all seminar rooms.

You have been given prac_q2.c, which contains a function average_capacity_room.

You have also been given the definition of a struct: room, and an enum: room_type which tells you some details about a room:

enum room_type {
  LECTURE,
  SEMINAR,
  LABORATORY
};

struct room {
  int capacity;
  enum room_type type;
};

The function average_capacity_room is given an array of room structs, where each struct contains:

• int capacity;, the capacity of the room.
• enum room_type type;, the type of the room.

Add code to the function average_capacity_room, so that it returns the average capacity of all SEMINAR rooms. The average should always be rounded down to the nearest integer. For example, if you have 5 / 2, you should return 2.If there were not any SEMINAR rooms, it should return 0.

For example, if the array of room structs contains the following:

{
      {.capacity = 10, .type = LECTURE},
      {.capacity = 25, .type = SEMINAR},
      {.capacity = 30, .type = LABORATORY},
      {.capacity = 40, .type = SEMINAR},
      {.capacity = 50, .type = LECTURE},
      {.capacity = 60, .type = LABORATORY}
}

Your function should return the value 32, because there are two SEMINAR rooms with capacity of 25 and 40 and the average will be (25 + 40) / 2 which is 32 due to rounding .

Testing

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

Your average_capacity_room function will be called directly in marking.

The main function is only to let you test your average_capacity_room function

You can change the test array of structs in main to test average_capacity_room with other values.

Any changes you make to the main function will be ignored in marking.

Assumptions/Restrictions/Clarifications.

• rooms will always have a type and capacity
• You must not change the arguments that average_capacity_room takes.
• average_capacity_room must return an int.
• You must not change the definition of enum room_type or struct room.
• You must not modify the array that average_capacity_room is passed.
• average_capacity_room should not call scanf, getchar or fgets.
• average_capacity_room should not call printf, putchar or any other function which prints something.
• You can assume, that you will always be given at least one room struct.
• Your submitted file may contain a main function. It will not be tested or marked.
• You may define extra functions and call them.

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)

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

find_triple should find the triple value in the given array, if one exists.

The array will either contain no triple values, or only a single value in the array will be tripled, i.e will occur three times.

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

find_triple should return a single integer: the value in the array that occurs three times, if one exists.

If there are no values that occur three times, find_triple should return NO_TRIPLE.

If the value occurs more than three times, this is not considered a triple.

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

3, 1, 4, 1, 5, 9, 1

find_triple should return the integer 1, as this is the element that occurred three times.

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

17, 17, 17, 17, 16, 17

find_triple should return the integer NO_TRIPLE, as none of the elements in the array occurred three times.

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

1, 2, 3, 4, 5, 6

find_triple should return NO_TRIPLE, as none of the elements in the array occurred three times.

Testing

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

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

Assumptions/Restrictions/Clarifications.

find_triple should return a single integer.

find_triple should not change the array it is given.

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

find_triple can assume the array contains at least one integer.

find_triple 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.