Question 1 [8 marks]

Let f(n) e O(na ) and g (n) e O(nb ) for real constants a and b, and function h(n) bedefined as f(n)xg(n) for all n.  Using the definition of O-notation, prove that the function h(n) e O(na+b ) for any real constants a and b. Show your working.

Question 2 [9 marks]

Solve the following recurrence equations to get a tight asymptotic bound on the complexity of the cor- responding 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.)

Question 3 [8 marks]

The breadth-first search procedure BFS, given below, assumes that the input graph G = (V, E) is repre- sented using an adjacency-list representation.

a.   [4 marks] Modify the breadth-first search procedure to assume that the input graph is represented using an adjacency-matrix representation instead.

b.   [4 marks] Assuming an efficient implementation of the queue (so that both enqueue and dequeue operations take constant time), and an input graph G with n vertices and m edges, describe the worst-case asymptotic time complexity of your procedure that assumes an adjacency-matrix repre- sentation of the graph, and how it compares to the worst-case asymptotic time complexity of the existing procedure that assumes an adjacency-list representation. Clearly justify your answer.

Question 5 [25 marks]

A festival consists of an opening ceremony event (the 0th  event), followed by a sequence of n further events, that take place one at a time, in sequential order.

There are m > 0 different venues, numbered from 1 tom, that can be used to host festival events.  The venues are connected via a transport network that is described by a weighted directed graph G = (V, E), with vertices G. V  representing each of the m different venues, with weight function weight, where for any venues u, v 2 G. V , weight(u, v) represents the cost of transporting festival participants directly from venue u to venue v.  For any venue u  2 G. V  we define weight(u, u) to be zero, and for any venues u, v 2 G. V , such that v G. Adj[u] and v u, we defineweight(u, v) = 1.

The opening ceremony (the 0th  event) must be hosted in venue number 1.  Each of the remaining events in the ceremony needs to be hosted at one of the m possible festival venues.  The i th  event  (for i  2 1, 2, ··· , n), can either be hosted at the venue that hosted the previous event, the (i − 1)th  event, or at a venue which is adjacent in graph G to the venue that hosted the previous event. This is so that the festival participants can get directly from one event to the next.

The cost of hiring venue j for the i th  event, for j 2 1, 2,... mandi 2 1, 2,...n, is given by hire[i][j].

Given a particular choice of venue for each event, the overall cost of hosting events 1 ton is defined to be the sum

where v0  =  1, the venue that the opening ceremony must be hosted at, and for i 2 1, 2,...n, vi  is the venue chosen to host the i th  event.

The problem is to find the minimum possible overall cost of hosting events 1 ton, for any choice of venues for events 1 ton. This problem can be solved by dynamic programming.

a.    [15 marks] For integers i and j such that 1 i n and 0 j m, let M(i, j) be the minimum

overall cost of hosting events i throughton, given that the venue chosen to host the (i − 1)thevent

was venue j. The solution we seek is M(1, 1).

Give a recurrence defining M(i, j) for 1 i n, 1 j m.

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 nand m. Briefly justify your answer.

Question 6 [20 marks]

This question involves performing an amortised analysis of a data structure that uses a linked list of integers called list, which is initialized to be empty when an instance of the data structure is created, and has two operations, INSERT (e) that takes an integer e as a parameter and appends it to the end of list:

INSERT (e)

1   list.ADD (e)

and an operation REMOVE (k), which takes an integer k as a parameter and removes the k first elements from list, removing all the elements from list if the list contains fewer thank elements. As well as removing elements from list, operation REMOVE (k) also creates and returns a linked list of integer products (where ⇥ is integer multiplication) that is dependent on the contents of list (see code for details):

REMOVE (k)

1   result = hi // initialize the result to be an empty linked list

2 while k > 0 and list.SIZE () > 0

3            e = list.REMOVEFIRST()

4            iterator = list.ITERATOR ()

5 while iterator.HASNEXT()

6                    result.ADD (e ⇥ iterator.NEXT ())

7           k = k − 1

8 return result

It is assumed that linked lists have operators ADD , that appends the specified element to the end of the list; SIZE (), that returns the number of elements in the list; REMOVEFIRST(), that removes and returns the first element in the linked list; and ITERATOR (), that returns an iterator over the linked list. An iterator over a linked list can be used to traverse the list in the forward direction from the front of the list to the end of the list.  It has operators HASNEXT(), that returns true if this list iterator has more elements when traversing the list in the forward direction; NEXT () that returns the next element in the list and advances the cursor position to the next element.

In the following analysis, measure the cost of the operations on the data structure in terms of the number of times that method ADD is called on any linked list. Using this measure of cost, the INSERT (e) operation has an actual cost of 1, and the REMOVE (k) operation has an actual cost which is the number of times that line 6 of that method (i.e. code result.ADD (e ⇥ iterator.NEXT ())) is executed.

a.   [5 marks] Using the definition of cost described, what is the actual cost of operation REMOVE (k), given that the size of list in the data structure isn before the operation is called. Your answer should be a precise count in the form of a summation, not an order of magnitude.

b.   [15 marks] Using the definition of cost described, use the potential method to prove that the worst-case cost of any sequence of m operations on the data structure (given that the data structure has been initialised immediately prior to performing the sequence of operations) is actually O(m2 ).  As part of your answer you need to (i) define a potential function, Φ , on the data structure;  (ii) calculate the amortised cost of the INSERT  and REMOVE  operations using the actual cost of the operations and the potential function; (iii) justify why the value of your potential function after any sequence of m operations, starting from a freshly initialised data structure, is bound below by the initial value of the potential function; (iv) use the amortised costs of the operations to prove that the worst-case cost of any sequence of m operations on the data structure is actually O(m2 ).