Algorithm | 代写assignment – Algorith


Algorithm | 代写assignment – 这是一个关于Algorithm的题目, 主要考察了关于Algorithm的内容,是一个比较经典的题目, 是比较典型的Algorithm等代写方向, 这是值得参考的assignment代写的题目

算法代写 代写算法 Algorithm代写 代写Algorithm  算法作业代写

COMP3121/9101 22T2 assignment 4, Question 4 (Algo Rhythm, z1234567)

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 n i=1si, 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;

Problem:find the maximum total imbalance of tournament with total skill levelSand 2n
Subproblems:for all 0sSand 1kn, letP(s, k) be the problem determining
opt(s, k) which is the maximum total imbalance of tournament with total skill levelsand 2k
opt(s, k) = max{opt(s 2 , k1),1 +opt(s 1 , k1), opt(s, k1)}
Base cases:opt( 1 , k) =opt(0, k) = 0,for all 0kn, andopt(s,0) = 0,for all  1 
We can solve the subproblems in increasing order ofsor in increasing order ofk. The overall
solution isopt(S, n). EachO(Sn) subproblems can be solved in constant time, so the time
complexity isO(nS).
An arrange the matches can be defined as a bijection mapmatchfrom{ 1 , 2 ,... , 2 n}to itself,
such thatmatch(i) be the unique playerjwho is in the same match with playeri.
Given such a map, we can define two players sets
P 0 (match) ={ 1 i 2 n|si= 1, sj= 0, match(i) =j}
P 1 (match) ={ 1 i 2 n|si= 1, sj= 1, match(i) =j}
M={ 0 iopt(S, n)|iS mod 2}
then a numbermis total imbalance if and only ifmM.
Ifmis total imbalance, then there is a mapmatchsuch thatm=|P 0 (match)|and
since|P 1 (match)|is always an even number, thusm=|P 0 | S=|P 0 |+|P 1 | mod 2, and
0 mopt(S, n) by definition, that ismM.


COMP3121/9101 22T2 Assignment 4, Question 4 (Algo Rhythm, z1234567)

Sinceopt(S, n) is the maximum total imbalance, then there is a mapmatchsuch that the
total imbalance equals toopt(S, n). we can find another arrange of matches such that the
total imbalance equals to anymMas follows:
Given a mapmatch, denoteP 0 =P 0 (match) for simplicity, then if|P 0 | 2 we can always
select two playersi 1 , i 2 P 0 , letj 1 =match(i 1 ), j 2 =match(i 2 ), rearrange the match gives a
new mapmatchsuch thatmatch(i 1 ) =i 2 andmatch(j 1 ) =j 2 , andmatch(i) =match(i)
for any otheri{i 1 , i 2 , j 1 , j 2 }, then the total imbalance formatchwill be reduced by two.
Since the elements inMis not exceedS, thus we can check ifmis a total imbalance inO(S)
time, thus the total runtime isO(nS) +O(S) =O(nS).

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

Your answer here.