COMP4500/COMP7500 Semester Two Examinations, 2022

Question 1   [9 marks]

Solve the following recurrence equations to get a tight asymptotic bound on the complexity of the corre- sponding functions. You do not need to show your working: in your answer you only need to give a tight asymptotic bound on the complexity of each function.  You may assume that T(n)  = Θ(1) for suitable constant n.

(You may leave logarithmic expressions in your answers if they evaluate to nonintegral values. Asymptotic notation should be used correctly and the asymptotic complexity should be simplified to remove lower order terms and unnecessary constant factors.)

Question 2    [10 marks]

Given the recurrence

T(n)   =   6                        for 0  n < 2

T(n)   =   3T(n 一 2) + n   for n ≥ 2

prove that T(n) e O(n x 3(n/2)) using the substitution method.  Clearly describe your inductive assump- tions and boundary conditions, and show your working. Justify that what you have proven is sufficient to show that T(n) e O(n x 3(n/2)) by referring to the definition of O-notation.

Question 3    [21 marks]

Recall that for a graph G with vertices G. V and edges G. E, a path p from v1  to vn  in graph G is a se- quence of vertices,〈v1, v2, v3,...,vn）, such that for i from 1 ton一1, (vi, vi+1) e G.E . For an unweighted graph G, the length of a pathis the number of edges in that path (e.g. the length of〈v1, v2, v3）is 2); and a shortest path from a vertex u e G. V to a vertex v e G. V  is a path from u to v in G of minimum length (i.e. a path from u to v that has no more edges than any other path from u to v).

a.   [18 marks] Given an unweighted graph G with vertices G. V and edges G. E , and vertices u e G. V and v e G. V , give an efficient algorithm in pseudocode that returns the number of shortest paths from u to v.

b.   [3 marks] Indicate which graph representation you would use to implement your algorithm from the previous part in the most time efficient way, and assuming that choice of graph representation, give the time complexity of your algorithm in terms of the number of vertices in the graph |V | and the number of edges in the graph |E| . Briefly justify your answer.

Question 4    [20 marks]

This question involves performing an amortised analysis of a data structure.

Consider an array-based data structure that can be used to implement a resizable, n⇥n square matrix. A two-dimensional array, with the same dimensions as the matrix, is used to store elements that have been inserted into the matrix. Initially the order n of the square matrix is set to 1 (i.e. initially the matrix is a 1⇥1 square matrix), and the matrix is empty (i.e. no elements are currently stored in the matrix).

The data structure has one operation to insert an element into the matrix. If the matrix is not full when an insert operation occurs, then the element is inserted into a free place in the array used to store the matrix, and the dimensions of the matrix (and the underlying array used to store it) are not changed. Otherwise, if the matrix is full, the order n of the matrix is doubled (so that the matrix becomes a (2n)⇥(2n) square matrix), and the array used to store the matrix is resized:

•a new larger array of dimension (2n)⇥(2n) is allocated,

•all of the elements from the old n⇥n array are copied to the new array, and the reference to the old array is updated to refer to the new array,

before the element is inserted into (a free place in) the new array used to store the matrix.

Let the actual cost of an insert operation be the number of elements that are copied from one array to another during the operation.  For example, the first insert operation has a cost of 0, because the 1⇥1 square matrix is not full, and so the element can be inserted into the (only) free place in the array used to store the matrix.  However, the second insert operation has a cost of 1 = 1⇥1 because the matrix is full, and so all of the elements from the old 1⇥1 array must be copied to a new 2⇥2 array, before the element can be inserted into the array.  The third and fourth insert operation also have a cost of 0, however the fifth insert operation has a cost of 4 = 2⇥2 (the cost of copying all of the elements from a 2⇥2 array to a 4⇥4 array).

a.   [4 marks] For arbitrary i ≥ 1, write an expression ci, for the actual cost of the ith  insert operation on the data structure.

b.   [6 marks] Starting from a freshly initialized data structure, how many array resizes are there in a sequence of m insert operations (for m ≥ 1)? What is the actual cost of the jth array resize operation (for j ≥ 1)?

c.   [10 marks] Using the aggregate method, calculate the worst-case actual cost of performing m (for m ≥ 1) consecutive insert operations on the data structure (starting from a freshly initialized data structure).

Question 5    [28 marks]

There are two workers, worker w0  and w1 .  Worker w0  and w1  are rostered on to work for H0  and H1 (whole) hours, respectively, in the coming week (where H0  ≥ 0 and H1  ≥ 0).

There are n available jobs j1 , j2 , ··· , jn that could be performed by either worker during the week, where the ith job, ji, takes h[i] whole hours to complete.

Given the set of available jobs, {j1 ,..., jn}, an assignment of jobs A0  to worker w0  and jobs A1  to worker w1 , is valid if and only if

•A0 and A1 are both subsets of the available jobs, i.e. A0  己 {j1 , j2 , ··· , jn} and A1  己 {j1 , j2 , ··· , jn}; • Each job is allocated to at most one worker, i.e. A0U A1  = {};

• No worker can be allocated to more jobs in the week than they will have the time to complete within their rostered working hours for the week,i.e. H0  ≥Pji=A0  h[i] and H1  ≥Pji=A1  h[i].

Note that we do not require that A0  a A1   =  {j1 ,..., jn}.  That is, not every available job needs to be allocated to a worker.

Given a valid assignment of jobs A0  to worker w0  and A1  to worker w1 , the rating for the job allocation is given by:

(The rating is designed to take into consideration both the overall number of unused rostered hours, as well as how evenly the work is distributed between the workers.)

The objective is to find the maximum rating possible given any valid assignment of the available jobs {j1 ,..., jn} to workers w0  and w1 , given that workers w0  and w1  are rostered on to work for H0  and H1 (whole) hours, respectively. This problem can be solved by dynamic programming.

a.   [15 marks] For integer i such that 0   i   n, and integers h0  and h1  such that 0    h0     H0 , 0  h1    H1, let M(i,h0 , h1 ) be the maximum rating possible given any valid assignment of available jobs {j1 ,..., ji} to workers w0  and w1  given that none of the jobs in {j1 ,..., ji} have already been allocated to either worker, and workers w0  and w1  currently have h0  and h1  (whole) rostered hours left, respectively, that are not already allocated to jobs. The solution (to the overall problem) we seek is M(n, H0 , H1 ).

Give a recurrence defining M(i,h0 , h1 ) for 0  i  n, 0  h0    H0 , 0  h1    H1 . You do NOT have to give a dynamic programming solution, just the recurrence.

Be sure to define the base cases of the recurrence as well as the more general cases.

b.   [10 marks] For the dynamic programming solution indicate in what order the elements of the table M corresponding to the recurrence should be calculated.  As part of answering this question, give pseudocode indicating the evaluation order. Give both the time and space complexity of the dynamic programming solution (based on recurrence M) in terms of n, H0 and H1. Briefly justify your answer.

c.   [3 marks]  Explain what the important properties are that a problem must satisfy for dynamic programming to provide a relatively fast solution to an algorithmic problem.