COMP1927 13s1 COMP1927 13s1 Final Exam Computing 2
[Instructions] [C language]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8] [Q9]

Question 1 (9 marks)

In the q1 directory (in the file q1.c), is a program which reads a sequence of integers into an array, and then calls a function ArrayMax() to find the largest value in the array. This could be achieved by a simple linear scan of the array, but the ArrayMax() function invokes another function max() which is intended to compute the maximum recursively.

The max(A,lo,hi) function finds the maximum value in a segment of the array A, starting from index lo (i.e. element A[lo]) up to index hi. You are required to implement the max() function so that its recursive behaviour is as follows:

max(A,lo,hi):
	find the maximum value in the lower half of the array
	find the maximum value in the upper half of the array
	choose the larger of these two values

You need to work out the base case yourself. You may implement any additional functions that you want, but you must maintain the current max() function interface.

Implementing the max() function iteratively (i.e. not recursively), even if correct and passes all tests, is worth zero marks.

As well as q1.c, the q1 directory also contains a Makefile which has two major behaviours:

make q1    # build the q1 program
make test  # apply the tests in q1/tests to the q1 program

You can find out more about the behaviour of the q1 program by looking at the test files in q1/tests directory. The files named X.in are inputs to the program. Each input has a corresponding file X.exp which contains the expected output from a correct implementation of q1.

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

submit q1

This will make a copy of the q1.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. Test your program thoroughly, possibly using test cases additional to those supplied. Your program will be tested using inputs which are different to the examples in the q1/tests directory.

If, at some stage, you need to "re-install" the files (although you should not need to), you can copy all of the original files into the q1 directory by running the command:

re-start q1

Beware: this will overwrite all of your exsting files for this question, so only do it if you seriously mess things up.