answer allqustions
Program Analysis University of Sussex Program Analysis G6017 Coursework 2 Due: Semester 1 Week 11 Wednesday 9 December by 4PM Format: Electronic submissions only by Canvas. Your submission does not need to be typed, although handwritten scripts must be legible. If you do the work in a handwritten form, please 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 12.5 % 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 A 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, … , ??) Input: A sequence of real values ? = (?1, … , ??) Output: Where no element in A is equal to 0, a pair (???, ???????) containing the sum and product values of the elements in A. Where an element in A is equal to zero, the output should be the pair (????, ????) Your recursive algorithm should use a single recursive structure to find the sum and product values, and should not use two separate instances of a recursive design. (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 = (8,3,1,3,2,6) and the sequence = (8,3,0,3,2,6) . [5 marks] (c) Write down the set of recurrence equations for your recursive algorithm. The recurrence equations should take a form like this: ?(?) = { (??????????) ?? (??????????) (??????????) ??ℎ?????? The “otherwise” case here refers 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: ?(?) = ?(? − 1) + 2(? − 1) + ?1 ?(2) = ?2 So the recursive algorithm features a base case when the size of the problem is ? = 2. The values of ?1 and ?2 are constants. (a) 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. You will 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 1 ?3 3 ?4 5 ?5 1 ?6 3 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 6 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 below: 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
[email protected] September 2020 END. mailto:
[email protected]