• kth.se
  • Studentwebben
  • Intranät
  • kth.se
  • Studentwebben
  • Intranät
Logga in
DD2352 VT20 (60319)
Mastery Test 2
Hoppa över till innehåll
Översikt
  • Logga in
  • Översikt
  • Kalender
  • Inkorg
  • Historik
  • Hjälp
Stäng
  • Min översikt
  • DD2352 VT20 (60319)
  • Uppgifter
  • Mastery Test 2
  • Startsida
  • Uppgifter
  • Sidor
  • Filer
  • Kursöversikt
  • Quiz
  • Media Gallery
  • Course Evaluation

Mastery Test 2

  • Inlämningsdatum 24 apr 2020 av 12:00
  • Poäng 4
  • Lämnar in en filuppladdning
  • Filtyper pdf
  • Tillgänglig 10 apr 2020 kl 12:00–24 apr 2020 kl 13:00
Den här uppgiften låstes 24 apr 2020 kl 13:00.

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).
1587722400 04/24/2020 12:00pm
Inkludera en beskrivning
Ytterligare kommentarer:
Maxresultat för gradering till > poäng
Inkludera en bedömningstitel

Matris

 
 
 
 
 
 
 
     
Det går inte att ändra en matris efter att du börjat använda den.  
Hitta en matris
Hitta matris
Inkludera en titel
Titel
Du har redan bedömt studenter med den här matrisen. Större ändringar kan påverka resultaten för deras uppgifter.
Titel
Kriterier Bedömningar Poäng
Redigera beskrivning av kriterium Ta bort kriterium rad
Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
tröskel: 5 poäng
Redigera ranking Radera ranking
5 till >0 poäng
Full poäng
blank
Redigera ranking Radera ranking
0 till >0 poäng
Inga poäng
blank_2
Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
poäng
  / 5 poäng
--
Ytterligare kommentarer
Redigera beskrivning av kriterium Ta bort kriterium rad
Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
tröskel: 5 poäng
Redigera ranking Radera ranking
5 till >0 poäng
Full poäng
blank
Redigera ranking Radera ranking
0 till >0 poäng
Inga poäng
blank_2
Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
poäng
  / 5 poäng
--
Ytterligare kommentarer
Poängsumma: 5 av 5