Search for question
Question

(a) State the Master Theorem for giving asymptotics of recurrence relations, as seen in this course, and the conditions under which it applies. [6 marks] (b) Estimate the asymptotics of the following recurrence relations. You may use the master theorem. \text { i. } T(n)=3 T(n / 3)+O\left(n^{2}\right) \text { ii. } T(n)=T(2 n / 3)+O(1) \text { iii. } T(n)=4 T(n / 3)+O(n) (c) The Maximum Subarray problem consists of an input array A of n integers(positive and negative) and the question is to find a subarray A[a... b] such that the sum of entries in the subarray is maximum. Describe an algorithm for the problem that runs in time O(n logn) or better.[10 marks] (d) Consider a project planning problem with the following specifications. • There are 5 tasks A-E to perform, with completion times as follows: Task A takes 3 days, task B takes 5 days, task C takes 7 days, task D takes 2 days, and task E takes 4 days. • Additionally, there are precedence constraints: Tasks A and B must be finished before task C can start, task C must be finished before task Dcan start, and task B must be finished before task E can start. Use the Critical Path Method (CPM) to find a shortest possible project schedule for this problem, assuming that tasks can be executed in parallel. i. Construct and draw the associated digraph with edge lengths. [E ii. Solve the planning problem and present a resulting schedule and iden-[6 marks]tify a critical path.

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5

Fig: 6

Fig: 7

Fig: 8

Fig: 9

Fig: 10

Fig: 11

Fig: 12