Mastery Test 2

Mastery Test 2 must be solved individually. No collaboration is allowed, and you
are not allowed to discuss the test with other students until after the oral presentations are
completed. See further the EECS Code of Honour.

The problems of Mastery Test 2 are available in the following pdf: mas2-2020.pdf Download mas2-2020.pdf

Good luck!

Clarification Apr 20:

• Problem 4: if you are uncomfortable working with Turing machines, you can instead choose to view a program M as being a text string giving the source code of a function M(x) written in a normal programming language such as Python or Java.  (And when the problem talks about "run M on x" this simply means running the function defined by the given source code, with x as input.)
  
  (Because these programming languages are what is called Turing-Complete Links to an external site., proving that the MemoryLeak problem is undecidable for any of these programming languages is equivalent to proving that it is undecidable when the programs M are Turing machines.)

Clarifications Apr 17:

• In this Mastery Test, it is not a formal requirement to provide pseudo code (e.g. for the reduction in Problem 1). The main thing is that the reduction is clear.
• However you should still prove that your solutions are correct.  For instance in Problem 2 where you are supposed to construct an algorithm with a given time complexity you have to argue that your solution satisfies this requirement, and in Problem 1 you have to argue that your reduction is correct.
• In Problem 2, you can think of the parameter n as the number of people in the social network.
• If you are having trouble understanding the definition of the Influencers problem:
  • There is no distinction between "influencer" and "person" in this problem. Every person influences some other people (maybe just themselves if they do not have any followers), and is a potential candidate influencer for us to choose.
  • The problem is asking whether it is possible to select a subset of all the people in the given social network, where this subset must have some properties (at most k people in the subset, but reaching at least m people in total)
  • Here is an example: suppose there are only four people, A, B, C, and D, and that
    • A is a follower of B and C
    • B is a follower of C and D
    • C is a follower of B
    • D is a follower of noone
  • Then for instance:
    • the set consisting only of person A reaches only A (because A has no followers)
    • the set consisting only of person D reaches B and D (but not A or C).
    • the set consisting of B and C reaches A, B, and C (but not D).
    • If k=2 and m=3, the answer is YES, because we can pick 2 of the people and reach at least 3 (e.g. as noted in the previous bullet item we could pick B and C as above and then reach A, B, and C).

Clarifications Apr 14:

• General reminder: to prove that a problem is NP-complete, we need to prove two things:
  
  1. That the problem is in NP.
  2. That the problem is NP-hard.
• The sentence "A set S of people..." should be interpreted as follows:
  Here S is just a name for some arbitrary set of people, think of it as a potential set of influencers that we can pay to distribute our information, and the statement is simply defining "these are the set of people that would get the information, if we chose this particular set S of influencers"
  (The sentence has been slightly updated in the pdf and now starts with "For any set S of people..." to hopefully make this more clear.)
• In Question 2, you may assume that the running time of the hypothetical algorithm for the decision version satisfies T(n) >= n (since any algorithm must in general look at the entire input).