本次澳洲代写主要为算法相关的两个task

Task 1: Among Us [50 marks]

You are playing your favourite social deduction game, Among Us, and it has nally come time to accuse

the imposters. You have kept track of which players have been cleared and by who, which players have

been accused and by who, and how sus each player is in general. You trust that any crewmate would only

clear a crewmate, and any crewmate would only accuse an imposter, but imposters cannot be trusted at

all. You must determine a group of players that could be imposters such that the sum of their sus is at

least some threshold.

Formally, you are given

n: the number of players

k: the number of imposters

t: sus threshold

s1; s2; :::sn: a number representing the sus of each player

C: a list of ordered pairs (p; q) indicating player p has cleared player q

A: a list of ordered pairs (p; q) indicating player p has accused player q

A subset I of the players f1; 2; : : : ; ng could be imposters if

I contains exactly k players

For any clear (p; q) in C, if p is not in I then q is not in I

For any accusation (p; q) in A, if p is not in I, then q is in I

The sus of a subset I of the players is the sum of the sus of each player, ie

Pi2I si. The Among Us

decision problem is to determine if there exists a subset of players that could be imposters with sus at

least the threshold t.

Figure 1: Example: Top = batman, right = cat, bottom = mini, left = shrek.

In Figure 1, each of the 4 players has sus, red double-arrows indicate accusations, blue single-arrows

indicate clears, and we are trying to nd 2 imposters. Formally:

n = 4

k = 2

t = 105

sbatman = 69; scat = 0; smini = 100; sshrek = 42

C = [(shrek; batman); (cat;mini); (batman; shrek)]

A = [(shrek; cat); (mini; shrek); (batman; cat)]

There are 6 subsets of size 2:

fbatman; shrekg could be imposters, total sus: 111

fbatman; catg could not be imposters because mini is accusing shrek, and because shrek is clearing

batman

fbatman;minig could not be imposters because shrek is clearing batman, and because cat is clearing

mini, and because shrek is accusing cat

fshrek; catg could not be imposters because batman is clearing shrek

fshrek;minig could not be imposters because batman is clearing shrek, and because cat is clearing

mini, and because batman is accusing cat

fcat;minig could be imposters, total sus: 100

Since there are two subsets that could be imposters with total sus 100 and 111, the answer to the Among

Us decision problem is YES.

Task 1a: Prove decision problem is in NP

(a) Describe a certicate and a verier.

(b) Give a brief justication of the correctness of the verier.

(c) Give a brief justication that the verier runs in polynomial time.

Task 1b: Prove decision problem is NP-hard

Your task is to give a polynomial-time Karp reduction from an NP-complete problem (see Appendix) to

the Among Us decision problem

(a) Describe how you transform an instance of the NP-complete problem into an instance of the Among

Us decision problem.

(b) Prove the correctness of your reduction, i.e. the instance of the NP-complete problem is a YES-

instance if and only if the instance of the Among Us decision problem created by your reduction is

a YES-instance.

(c) Prove that your reduction is polynomial-time.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** itcsdx@outlook.com **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。