代写Algorithm | 代写assignment – recurrence

2022-06-26

recurrence

代写Algorithm | 代写assignment – 这道题目是利用Algorithm进行的编程代写任务, 是比较典型的Algorithm等代写方向, 这个项目是assignment代写的代写题目

ass代做 assignment代写 代写assignment

Due 28th July 2022 at 4pm Sydney time In this assignment we apply dynamic programming. There arefour problemseach worth 20 marks, for a total of 80 marks. Your solutions must be typed, machine readable PDF files. All submissions will be checked for plagiarism! For each question requiring you to design an algorithm, youmustjustify the correctness of your algorithm. If a time bound is specified in the question, you alsomustargue that your Algorithm meets this time bound. To describe a dynamic programming algorithm, you must include:

  • the subproblem specification,
  • the recurrence,
  • any base cases,
  • how the overall answer is calculated, including (if necessary) the order in which the subprob- lems are solved and
  • the time complexity analysis. The recurrence, base cases and final answer calculation must each be accompanied with (often brief) worded reasoning to justify the correctness of the algorithm. Partial credit will be awarded for progress towards a solution.

Question 1

You are playing a video game, where you control a character in a grid withmrows andncolumns. The character starts at the square in the top left corner (1,1), and must walk to the square in the bottom right corner (m, n). The character can only move one square at a timedownwards or rightwards. Every square (i, j), other than the starting square and the ending square, contains a known number of coinsai,j.

1.1 [10 marks]Design an algorithm which runs inO(mn) time and determines the maximum number of coins that your character can accumulate by walking from (1,1) to (m, n) using a combination of downwards and rightwards moves.

1.2 [10 marks]After playing this game many times, you have broken the controller, and you can no longer control your character. They now walk randomly as follows:

  • if there is only one possible square to move to, they move to it;
  • otherwise, they move right with probabilitypand down with probability 1p. Note that this guarantees that the character arrives at (m, n). Design an algorithm which runs inO(mn) time and determines theexpectednumber of coins that your character will accumulate by walking from (1,1) to (m, n) according to the random process above. Recall that for a discrete random variableXwhich attains valuesx 1 ,… , xnwith probabilities p 1 ,… , pn, theexpected valueofXis defined as
E(X) =
Xn
i=

pixi.

Question 2

You are managing a garage with two mechanics, named Alice and Bob. Each mechanic can serve at most one customer at a time. There will bencustomers who come in during the day. Theith customer wants to be served for the entire period of time starting at timesiand ending at timeei. You may assume that the customers are indexed by their order of arrival, i.e.s 1 < s 2 <… < sn. For each customeri, the business will:

  • makeaidollars if customeriis served by Alice;
  • makebidollars if customeriis served by Bob;
  • losecidollars if customeriis not served. Your task is to maximise the net earnings of the garage, which is calculated as the total amount made minus the total amount lost.

2.1 [8 marks]Consider the following greedy algorithm. Process each customeriin order of arrival as follows.

  • If both Alice and Bob are available at timesi:
    • ifaibi, assign customerito Alice;
    • otherwise, assign the customer to Bob.
  • If only one mechanic is available at timesi, assign customerito that mechanic.
  • If neither mechanic is available at timesi, do not serve customeri. Design an instance of the problem which is not correctly solved by this algorithm. You must:
  • specify a number of customersn,
  • for each customer, provide values forsi,ei,ai,biandci,
  • apply the greedy algorithm to this instance and calculate the net earnings achieved, and
  • show that a higher net earnings figure can be achieved.

2.2 [12 marks]Design an algorithm which runs inO(n^2 ) time and determines the maximum net earnings of the garage.

Question 3

You are given a simple directed weighted graph withnvertices andmedges. The edge weights maybe negative, but there are no cycles whose sum of edge weights is negative.

3.1 [10 marks]An edgeeis said to beusefulif there is some pair of verticesuandvsuch that ebelongs toat least oneshortest path fromutov. Design an algorithm which runs inO(n^3 ) and determines the set of useful edges.

3.2 [10 marks]An edge is said to bevery usefulif there is some pair of verticesuandvsuch thatebelongs toeveryshortest path fromutov. Design an algorithm which runs inO(n^3 ) and determines the set of very useful edges.

Question 4

There are 2nplayers who have signed up to a chess tournament. For all 1i 2 n, theith player has a known skill level ofsi, which is a non-negative integer. LetS=P^2 i=1n si, the total skill level of all players. In the tournament, there will benmatches. Each match is between two players, and each player will play in exactly one match. Theimbalanceof a match is the absolute difference between the skill levels of the two players. That is, if a match is played between theith player and thejth player, its imbalance is|sisj|. Thetotal imbalanceof the tournament is the sum of imbalances of each match. The organisers have provided you with a valuemwhich they consider to be the ideal total imbalance of the tournament. Design an algorithm which runs inO(n^2 S) time and determines whether or not it is possible to arrange the matches in order to achieve a total imbalance ofm, assuming:

4.1 [4 marks]allsiare either 0 or 1;

4.2 [16 marks]thesiare distinct non-negative integers.