G6017编程代做代写、MATLAB编程设计代做

日期：2023-12-16 08:12

University of Sussex

Program Analysis G6017

Coursework 2

Due: XVAC Week 11 Thursday 21 December 2023 by 4PM

Format: Electronic submissions only by Canvas. You should write your

answers in the blanks in your answer sheet we have provided for

you and submit this answer sheet only. If you want to do your

work in a handwritten form, please print the answer sheet, fill it

properly, and then again scan it and upload the work as a single

PDF document. No paper copies of this submission will be

accepted.

Weighting 50.0 % of the coursework element for this module

25.0 % of the overall module mark

General instructions

1. Answer all of the questions.

2. Show your workings where appropriate. You can still get credit for a question

with an incorrect final answer if your workings show that you understood what

the problem was and how to solve it.

3. Do not copy the work of another student. Plagiarism is a very serious matter.

Discussion between students is to be encouraged – copying is an academic

disciplinary matter.

4. Check that you provide any working or information that the question asks for.

5. Hand your submission in on time. There are penalties for late submission.

6. If I cannot read your submission, I cannot mark it. It is your responsibility to

ensure that the presentation of your submission is appropriate for a University

student.

7. Do not forget to state units if they are relevant and apply to a question.

8. You should use any calculating aids your feel appropriate to help you solve

the problems including, although not limited to, calculators, spreadsheets

such as Excel and MATLAB.

9. If you do not understand the questions, you can get help at the workshop

sessions.

10.This assignment is marked out of a total of 100

Q1)

This question is concerned with the design and analysis of recursive algorithms.

You are given a problem statement as shown below. This problem is concerned

with performing calculations on a sequence ?? of real numbers. Whilst this could

be done using a conventional loop-based approach, your answer must be

developed using a recursive algorithm. No marks will be given if your answer

uses loops.

??????????????????????????????????????????(??1, … , ????) such that ?? > 1

Input: A sequence of real values ?? = (??1, … , ????

).

Output:, A 2-tuple (??????????????, ??????????????) containing the average (??????????????) of all the

values and the product (??????????????) of all the values of the elements in ??.

Your recursive algorithm should use a single recursive structure to find the

average and product values, and should not use two separate instances of a

recursive design. You should not employ any global variables.

(a) Produce a pseudo code design for a recursive algorithm to solve this

problem.

[5 marks]

(b) Draw a call-stack diagram to show the application of your recursive

algorithm when called using the sequence = (24, 8, ?4, 6, ?6, 3).

[5 marks]

(c) Write down the set of recurrence equations for your recursive algorithm.

Remember that one of the equations should correspond to the recursive

algorithm base case.

[4 marks]

(d) Using the recurrence equations you gave in your answer for part (c),

determine the running time complexity of your recursive algorithm.

[6 marks]

Q2)

A piece of code implementing a recursive algorithm has been produced, and a

student has analysed the recurrences. They have produced the recurrence

equations as shown below:

??(??) = ??(?? ? 3) + 2(?? ? 3) + ??1

??(3) = ??2

So the recursive algorithm features a base case when the size of the problem is

?? = 3. The values of ??1 and ??2 are constants. You should assume the initial value

of ?? (the size of the problem) is divisible by 3.

Determine the running time complexity of this recursive algorithm. To get the full

marks, your analysis should be as complete as possible. To get an idea of how to

perform a complete analysis, refer to the example recursive algorithm analysis on

Canvas. You can verify your analysis by modelling the recurrence equations in a

program like Excel or MATLAB. Your answer must include:

(a) Evidence of at least two cycles of substitutions to establish the running

time function ??(??).

(b) A clear statement of the generalisation of that pattern to ?? iterations of

the recursive step.

(c) A statement of the number of iterations required to solve a problem of

size ??.

(d) A statement of the final overall running time complexity that follows

from your previous algebra.

You may find it useful to know that the formula for a sum of an arithmetic

sequence of numbers of the form (1,2,3, … . ??) is given by the formula:

∑ ??

??=??

??=1

=

??(?? + 1)

2

[20 marks]

Q3)

This question is concerned with dynamic programming.

A bottom up dynamic programming method is to be used to solve the subset sum

problem. The problem is to find the optimal sum of weighted requests from a set

of requests ?? subject to a weight constraint W. The set of weighted requests ?? =

{??1, ??2, ??3, ??4, ??5, ??6} can be summarised as following:

Request ??(????)

??1 2

??2 2

??3 1

??4 7

??5 7

??6 1

The maximum weight constraint is 13.

Using the following algorithm (reproduced from the notes on Canvas):

(a) Produce a table showing the space of the problem and all of the sub

problems, and use that table to determine the optimal subset sum of

requests when the weight constraint of 13 is applied. The table should

take the form of a matrix with 7 rows (values of ?? in the range 0 to 6

inclusive) and 14 columns (values of ?? in the range 0 to 13 inclusive).

[20 marks]

Q4)

In this question, we consider the operation of the Ford-Fulkerson algorithm on

the network shown overleaf:

Each edge is annotated with the current flow (initially zero) and the edge’s

capacity. In general, a flow of ?? along an edge with capacity ?? is shown as ??/??.

(a) Show the residual graph that will be created from this network with the

given (empty) flow. In drawing a residual graph, to show a forward edge

with capacity ?? and a backward edge with capacity ??, annotate the original

edge ???; ??? .

[4 marks]

(b) What is the bottleneck edge of the path (??, ??1, ??3, ??5,??) in the residual

graph you have given in answer to part (a) ?

[2 marks]

(c) Show the network with the flow (??, ??1, ??3, ??5,??) that results from

augmenting the flow based on the path of the residual graph you have

given in answer to part (a).

[3 marks]

(d) Show the residual graph for the network flow given in answer to part (c).

[4 marks]

(e) What is the bottleneck edge of the path (??, ??3, ??4,??) in the residual graph

you have given in answer to part (d) ?

[2 marks]

(f) Show the network with the flow that results from augmenting the flow

based on the path (??, ??3, ??4,??) of the residual graph you have given in

answer to part (d).

[3 marks]

(g) Show the residual graph for the network flow given in answer to part (f).

[4 marks]

(h) What is the bottleneck edge of the path (??, ??2, ??3, ??1, ??4,??) in the residual

graph you have given in answer to part (g) ?

[2 marks]

(i) Show the network with the flow that results from augmenting the flow

based on the path (??, ??2, ??3, ??1, ??4,??) of the residual graph you have given

in answer to part (g).

[3 marks]

(j) Show the residual graph for the network flow given in answer to part (i).

[4 marks]

(k) Show the final flow that the Ford-Fulkerson Algorithm finds for this

network, given that it proceeds to completion from the flow rates you have

given in your answer to part (i), and augments flow along the edges

(??, ??1, ??3,??) and (??, ??2, ??5,??).

[4 marks]

(l) Identify a cut of the network that has a cut capacity equal to the maximum

flow of the network.

[5 marks]

Dr Kingsley Sage

Khs20@sussex.ac.uk

November 2023

END.