COMP9024 (19T0) Sample Midterm Exam

Question 1 (6 marks)

In the q1 directory, you will find the following files/directories:

subsetList.c: the only file you need to modify and submit.
autotest: simple auto testing script, important: this script only tests simple cases, you need to extensively test your program for a wide range of test cases.
DLList.h and DLList.o: an implementation of a simple doubly-linked list ADT, similar to (but not the same as) the one you used in your lab exercises. Please open and read DLList.h for the available functions for this question. Please note that DLList.c is NOT available for this exam.
testSubsetList.c: the program to test your function.The program uses the available function getDLList to read a list from stdin, calls the function you implement subsetList, and outputs the answer to stdout.
Makefile: to build the required files.
tests: the directory containing input (*.in) and expected output (*.exp) files for few simple test cases.

Your task for this question is to implement the subsetList() function in the file subsetList.c. The subsetList() function has two arguments: a doubly-linked list L1 and a doubly-linked list L2. The function subsetList() returns 1 if L1 contains all the values in L2, and returns 0 otherwise.

Time complexity: What is the time complexity of your algorithm in big-Oh notation? Wrire the time complexity of your algorithm in big-Oh notation as a part of the comments just before the function header. Also, briefly explain your answer as a part of the comments just before the function header.

The following examples show how the function works:

subsetList( [4, 8, 10, 5] , [5, 8])  →  returns 1
subsetList( [4, 3, 10, 5, 1, 7], [9])  →  returns 0 
subsetList( [3, 16, 20], [20, 3, 16])  →  returns 1
subsetList( [4, 16, 9, 12, 45], [])  →  returns 1

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

$ make    # builds the required program testSubsetList
$ ./autotest  # apply all the tests in the tests directory to the program testSubsetList
$ ./autotest <test-number>   # apply only one given test case from the tests directory to the program testSubsetList

You can find out more about the behaviour of the testSubsetList program by looking at the files testSubsetList.c, autotest and the files in the tests directory. The files named tX.in are input files for the test program testSubsetList and the corresponding expected output are in tX.exp.

If you want to run say test case 2, use the following command:

$ ./autotest 2

If you want to run all the sample test cases provided, use the following command:

$ ./autotest

After you run the tests, additional files will appear in the tests directory: tX.out contains the output (from your function) of running test tX.

IMPORTANT: You can add debugging code to subsetList.c or testSubsetList.c if you want, 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. You can also add any auxiliary functions to subsetList.c that you think are necessary.

Once you are satisfied with your program, submit it using the command:

$ submit q1

This will make a copy of the subsetList.c file from the q1 directory as your answer for this question. You can run the submit command as many times as you like, but make sure that your final submission compiles without any errors or warnings.

Testing: Test your program thoroughly, possibly using test cases additional to those supplied. Your program will be tested using test cases different to the example test cases provided in the tests directory.