COMP2521 21T1 Final Exam

We say that a sequence of integers seq1 contains another sequence seq2 if all the integers in seq2 also appear in seq1, in the same order as they appear in seq2. If seq2 is empty, then seq1 contains seq2 regardless of what is contained in seq1.

Implement the following function in the file containsSequence.c:

int containsSequence(List seq1, List seq2);

containsSequence should return 1 if the sequence represented by seq1 contains the sequence represented by seq2, and 0 otherwise. For example:

seq1: 10, 5, 23, 56, 8, 92, 5, 7
seq2: 5, 8, 92
containsSequence(seq1, seq2) should return 1.

seq1: 10, 5, 23, 56, 8, 92, 5, 7
seq2: 8, 5, 92
containsSequence(seq1, seq2) should return 0.

seq1: 10, 5, 23, 56, 8, 92, 5, 7
seq2: 25, 23, 56, 8
containsSequence(seq1, seq2) should return 0.

seq1: 10, 5, 23, 56, 8, 92, 5, 7
seq2: 10, 7
containsSequence(seq1, seq2) should return 1.

seq1: 10, 5, 23, 56, 8, 92, 5, 7
seq2: 8, 92, 7
containsSequence(seq1, seq2) should return 1.

seq1: 10, 5, 23, 56, 8, 92, 5, 7
seq2: 56
containsSequence(seq1, seq2) should return 1.

seq1: 10, 5, 23, 56, 8, 92, 5, 7
seq2: 5, 5, 7
containsSequence(seq1, seq2) should return 1.

seq1: 10, 5, 23, 56, 8, 92, 5, 7
seq2: 5, 7, 5
containsSequence(seq1, seq2) should return 0.

Constraints

• The given lists must not be modified.
• The time complexity of your solution must be O(m + n), where m and n represent the number of nodes in seq1 and seq2 respectively. If your solution is slower than O(m + n), the maximum mark you can attain for this question will be 3 (out of 5).
• You must not use arrays or any variant of malloc, either directly or indirectly. If you don't satisfy this requirement, you will receive zero for this question.

Download

Click here to download a zip of the files.

If you are connected to CSE, you can download and unzip the files using the following commands:

$ mkdir q1 # create directory for q1
$ cd q1    # change into q1 directory
$ cp /web/cs2521/21T1/exam/downloads/q1.zip .
$ unzip q1.zip

The Files

list.c	Contains the implementation of basic linked list functions.
list.h	Contains the definition of the linked list data structure and function prototypes.
testContainsSequence.c	The testing program. The program reads list data from stdin, calls containsSequence, and outputs the result to stdout. You must carefully study how your function is tested by testContainsSequence.c.
containsSequence.c	Contains containsSequence, the function you must implement. This is the only file you should modify.
Makefile	A Makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic test cases
autotest	A script that uses the tests in the tests directory to test your solution.

Testing

You can compile and test your function using the following commands:

$ make                                  # compiles the program
$ ./testContainsSequence                # tests with manual input, outputs to terminal
$ ./testContainsSequence < input-file   # tests with input from a file, outputs to terminal
$ ./testContainsSequence < tests/1.in   # for example, tests with input from tests/1.in
$ sh autotest                           # runs all provided tests
$ sh autotest test-number               # runs a specific provided test
$ sh autotest 2                         # for example, runs test 2

You can find out more about the behaviour of the testContainsSequence program by looking at the files testContainsSequence.c, autotest and the files in the tests directory. The files named X.in contain inputs for the provided tests and the corresponding expected outputs are in X.exp.

After you run the autotest script, additional files named X.out will appear in the tests directory. X.out contains the output of running test X.

You can create more tests by creating input files similar to the provided X.in files.

You can add debugging code to containsSequence.c and testContainsSequence.c if you wish. However, make sure that you remove it before testing and submitting, otherwise your output won't match the expected output and you'll fail all the tests.

Submit

Submit your code through the give command or via WebCMS (click here).

The give command is:

$ give cs2521 final_q1 containsSequence.c

Please note that the submission script does not run any tests on your program. Thus, it is important that you test your program on the CSE system before submitting.

Make sure to thoroughly test your program, if time permits. We will run further tests on your submission after the exam which may test different cases from the tests provided to you.

Important: Do not leave submissions to the last minute - submit as soon as you complete each question.

Implement the following function in the file isBST.c:

int isBST(Tree t);

isBST takes one argument: a binary tree t of records. It should return 1 if t is a binary search tree with respect to its comparison function, and 0 otherwise.

The following two ADTs are provided:

• Tree ADT (Tree.h and Tree.c).
• Record ADT (Record.h and Record.c).

Assumptions

• You should assume that the tree's comparison function behaves as an ordinary comparison function as you have used in the first assignment.

Constraints

• The given tree must not be modified.
• The time complexity of your solution must be O(n), where n represents the number of nodes in the tree. If your solution is slower than O(n), the maximum mark you can attain for this question will be 5 (out of 7.5).
• You must not use arrays or any variant of malloc, either directly or indirectly. If you don't satisfy this requirement, you will receive zero for this question.

Download

Click here to download a zip of the files.

If you are connected to CSE, you can download and unzip the files using the following commands:

$ mkdir q2 # create directory for q2
$ cd q2    # change into q2 directory
$ cp /web/cs2521/21T1/exam/downloads/q2.zip .
$ unzip q2.zip

The Files

Tree.c	Contains the implementation of the Tree ADT.
Tree.h	Contains the definition of the tree data structure and function prototypes.
testIsBST.c	The testing program. The program takes a single command-line argument which is the test number, creates a tree (determined by the test number), calls isBST, and outputs the result to stdout. You must carefully study how your function is tested by testIsBST.c.
isBST.c	Contains isBST, the function you must implement. This is the only file you will submit.
Makefile	A Makefile to compile your code
tests/	A directory containing the expected outputs for some basic test cases
autotest	A script that uses the tests in the tests directory to autotest your solution.

Examples

Using comparison function: compareByZid

Tree:
50|Smith|John
+--L: X
+--R: 65|Ng|Rita
      +--L: X
      +--R: X

isBST returned: 1

Using comparison function: compareByZid

Tree:
50|Smith|John
+--L: 14|Brown|Kylie
|     +--L: X
|     +--R: X
+--R: 65|Ng|Rita
      +--L: X
      +--R: X

isBST returned: 1

Using comparison function: compareByZid

Tree:
50|Jones|Ram
+--L: 65|Singh|Samuel
|     +--L: 12|Zhou|Layla
|     |     +--L: X
|     |     +--R: X
|     +--R: X
+--R: 80|Lee|Emma
      +--L: 72|Brown|Olivia
      |     +--L: X
      |     +--R: X
      +--R: 91|Yang|Sophia
            +--L: X
            +--R: X

isBST returned: 0

Explanation: For these particular tests, the tree uses the comparison function compareByZid, which compares records by zid (see testIsBST.c). The last tree is not a BST, because the record in the root node contains a smaller zid (50) than the record in its left child (65), which violates the ordering of a BST. The other trees are BSTs. Note that the tests used in marking may use different comparison functions.

Testing

You can compile and test your function using the following commands:

$ make                      # compiles the program
$ ./testIsBst test-number   # runs a specific test, outputs to terminal
$ ./testIsBst 2             # for example, runs test 2, outputs to terminal
$ sh autotest               # runs all provided tests
$ sh autotest test-number   # runs a specific provided test
$ sh autotest 2             # for example, runs test 2

You can find out more about the behaviour of the testIsBST program by looking at the files testIsBST.c, autotest and the files in the tests directory. The files named X.exp contain expected outputs for the provided tests.

After you run the autotest script, additional files named X.out will appear in the tests directory. X.out contains the output of running test X.

You can create more tests by modifying testIsBST.c at the places marked in comments.

You can add debugging code to isBST.c and testIsBST.c if you wish. However, make sure that you remove it before testing and submitting, otherwise your output won't match the expected output and you'll fail all the tests.

Submit

Submit your code through the give command or via WebCMS (click here).

The give command is:

$ give cs2521 final_q2 isBST.c

Please note that the submission script does not run any tests on your program. Thus, it is important that you test your program on the CSE system before submitting.

Make sure to thoroughly test your program, if time permits. We will run further tests on your submission after the exam which may test different cases from the tests provided to you.

Important: Do not leave submissions to the last minute - submit as soon as you complete each question.

Implement the following function in the file calculateViralTransmission.c:

void calculateViralTransmission(Graph g, int src, int srcViralLoad, double *trasmissionArray);

The function calculateViralTransmission takes four arguments: an undirected graph g, a source node src, the viral load at the source node srcViralLoad (where 0 ≤ srcViralLoad ≤ 100) and an array trasmissionArray. For each node reachable from src (and only these nodes), the function should calculate the viral load transmitted to that node and store it in the array trasmissionArray. For example, trasmissionArray[2] should contain the viral load transmitted to node 2 if node 2 is reachable from src.

Important: If a node is not reachable from src, the function should not calculate and store the viral load transmitted to that node. Only nodes reachable from src should be considered. In the test program testTransmissionAmts.c, all values in the trasmissionArray are initialised to -1.0. If a node v is not reachable, transmissionArray[v] should remain as -1.0. If you change the value, you will fail the test.

Assumptions

• You can assume that the array trasmissionArray has size n, where n is the number of nodes in the graph.

Constraints

• You must correctly use a suitable graph traversal algorithm (DFS or BFS) in your solution. Otherwise, the maximum mark you can attain for this question will be 5 (out of 7.5).
• The time complexity of your solution must be O(n²), where n represents the number of nodes in the graph. If your solution is slower than O(n²), the maximum mark you can attain for this question will be 5 (out of 7.5).

Download

Click here to download a zip of the files.

If you are connected to CSE, you can download and unzip the files using the following commands:

$ mkdir q3 # create directory for q3
$ cd q3    # change into q3 directory
$ cp /web/cs2521/21T1/exam/downloads/q3.zip .
$ unzip q3.zip

The Files

Graph.c	Contains the implementation of basic Graph ADT functions.
Graph.h	Contains the definition of the Graph ADT and function prototypes.
Queue.c	Contains the implementation of basic Queue ADT functions.
Queue.h	Contains the definition of the Queue ADT and function prototypes.
testTransmissionAmts.c	The test program. The program reads data, creates a graph, calls the function calculateViralTransmission, and outputs the results to stdout. You must carefully study how your function is tested by testTransmissionAmts.c.
calculateViralTransmission.c	Contains calculateViralTransmission, the function you must implement. This is the only file you will submit.
Makefile	A Makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic test cases
autotest	A script that uses the tests in the tests directory to autotest your solution.

Examples

For example, consider the following graph:

Suppose that src = 0 and srcViralLoad = 70. The viral load transmitted to each node is:

• transmissionArray[0] = srcViralLoad * (0.6 ^ 0) = 70.00, because 0 is the source node.
• transmissionArray[1] = srcViralLoad * (0.6 ^ 2) = 25.20, because the length of the shortest path from 0 to 1 is 2.
• transmissionArray[2] = srcViralLoad * (0.6 ^ 1) = 42.00, because the length of the shortest path from 0 to 2 is 1.
• transmissionArray[3] = srcViralLoad * (0.6 ^ 1) = 42.00, because the length of the shortest path from 0 to 3 is 1.
• transmissionArray[4] = srcViralLoad * (0.6 ^ 2) = 25.20, because the length of the shortest path from 0 to 4 is 2.
• transmissionArray[5] = srcViralLoad * (0.6 ^ 2) = 25.20, because the length of the shortest path from 0 to 5 is 2.
• transmissionArray[6] is unchanged (-1), because node 6 is not reachable from src node 0.
• transmissionArray[7] = 0, because the length of the shortest path from 0 to 7 is 4, and srcViralLoad * (0.6 ^ 4) = 9.072, which is less than 10.
• transmissionArray[8] = srcViralLoad * (0.6 ^ 3) = 15.12, because the length of the shortest path from 0 to 8 is 3.

Testing

You can compile and test your function using the following commands:

$ make                                  # compiles the program
$ ./testTransmissionAmts < input-file   # tests with input from a file, outputs to terminal
$ ./testTransmissionAmts < tests/1.in   # for example, tests with input from tests/1.in
$ sh autotest                           # runs all provided tests
$ sh autotest test-number               # runs a specific provided test
$ sh autotest 2                         # for example, runs test 2

You can find out more about the behaviour of the testTransmissionAmts program by looking at the files testTransmissionAmts.c, autotest and the files in the tests directory. The files named X.in contain inputs for the provided tests and the corresponding expected outputs are in X.exp.

After you run the autotest script, additional files named X.out will appear in the tests directory. X.out contains the output of test X.

You can create more tests by creating input files similar to the provided X.in files.

You can add debugging code to calculateViralTransmission.c and testTransmissionAmts.c if you wish. However, make sure that you remove it before testing and submitting, otherwise your output won't match the expected output and you'll fail all the tests.

Submit

Submit your code through the give command or via WebCMS (click here).

The give command is:

$ give cs2521 final_q3 calculateViralTransmission.c

Please note that the submission script does not run any tests on your program. Thus, it is important that you test your program on the CSE system before submitting.

Make sure to thoroughly test your program, if time permits. We will run further tests on your submission after the exam which may test different cases from the tests provided to you.

Important: Do not leave submissions to the last minute - submit as soon as you complete each question.