Mästarprov 2

Mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Inget samarbete är tillåtet, se vidare hederskodexen. Du ska alltså inte diskutera lösningar med någon annan fram till dess att alla muntliga redovisningar är avklarade. Detta är något som vi tar allvarligt på. Misstänkt otillåtet samarbete måste enligt KTH:s regler anmälas till rektor. Inlämningarna plagiatgranskas.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; inskannade handskrivna lösningar går bra) senast torsdag 3 december 2020 klockan 15.00. Det är viktigt att du lämnar in i tid! Om du inte ser någon inlämningsknapp på denna sida så ska du se till att du är inloggad i Canvas genom att klicka på inloggningsikonen i den gråa vänstermenyn.

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på dina lösningar inför den muntliga redovisningen som kommer att ske mellan 7 och 11 december i Zoom för någon av assistenterna eller lärarna. Boka tid för en femton minuters muntlig redovisning i Canvas senast 3 december klockan 15.00. Bokningslistorna läggs upp den 1 december sist på denna sida. Om du inte hinner göra uppgiften så avbokar du enkelt din bokning.

Det är viktigt att du förbereder dig inför den muntliga redovisningen. För att en uppgift ska godkännas ska du kunna förklara och motivera reduktionen/algoritmen muntligt och reda ut eventuella oklarheter.

Läs uppgifterna mycket noga så att du inte råkar basera dina lösningar på en missuppfattning. Fråga en lärare på kursen om något är oklart. Uppgiftslydelserna kommer också att gås igenom på föreläsningarna 24 november (uppgift 1 och 3) och 25 november (uppgift 2). 

Mästarprovet är ett obligatoriskt moment i kursen. Det består av tre uppgifter som motsvarar betygskriterierna för E, C respektive A. För godkänt (betyg E) krävs helt rätt på uppgift 1 eller 2. Helt rätt på uppgift 1 och 2 ger betyg C och alla rätt ger betyg A. Ett mindre fel på en uppgift sänker betyget ett steg. Läs mer om betyg här.

Den som blir godkänd på uppgift 3 men bara en av uppgift 1 och 2 får betyg E eller D, men resultatet för uppgift 3 sparas i Canvas, så det går sedan att munta till betyg A genom att endast göra en muntauppgift för betyg C på mästarprov 2 (eftersom den därmed har visat uppfyllelse av betygskriterierna för alla nivåer). 

För att se exempel på hur utförliga lösningarna bör vara kan du titta på lösningar till tidigare mästarprov, både autentiska studentlösningar och mönsterlösningar. Där finns också tips om hur man formulerar och genomför matematiska bevis, som du bör läsa innan du bevisar dina reduktioner. Format/datastruktur för indata och utdata ska du välja själv om det inte står specificerat i uppgiften.

Uppgift 1 Trött robot

Betygskriterium: förklara principerna, utföra enklare reduktioner mellan givna problem.

Vi ska studera en variant av problem 2 från mästarprov 1.

En robot befinner sig i övre hörnet på ett sluttande plan i form av ett kvadratiskt rutnät av storlek n gånger n. Hela planet är täckt av tjock snö och roboten har inte så mycket laddning kvar, så den behöver utnyttja planets lutning för att orka genomföra sitt uppdrag innan batteriet tar slut. Uppdraget är att samla ihop en viss angiven mängd osmium, varken mer eller mindre, och transportera det till det nedersta hörnet på det sluttande planet. I varje steg kan roboten röra sig antingen en ruta snett ned till vänster eller en ruta snett ned till höger, vilket innebär att den från ruta (i,j) kan röra sig antingen till (i+1,j) eller (i,j+1), se bilden. Men vid ett (och endast ett) tillfälle under vandringen orkar roboten backa till rutan som den just kom ifrån (vilket innebär att den åker i uppförsbacke - att det ens är möjligt beror på att snön är nedtrampad av roboten i alla rutor som den passerat). Roboten kan aldrig röra sig utanför planet (rutnätet).

Som tur är känner vi till exakt hur mycket osmium som finns att hämta i varje ruta i rutnätet. I ruta (x,y) finns Os[x,y] gram osmium (ett ickenegativt heltal). Första gången roboten når en ruta samlar den in allt osmium som finns i den rutan, så om roboten återkommer till samma ruta en andra gång så finns det inget osmium kvar i rutan att samla in. Det kan ändå vara givande för roboten att backa tillbaka till rutan som den just kom ifrån eftersom den då har möjlighet att välja en annan väg än den tog förra gången. Som sagt orkar den bara backa vid ett tillfälle så det gäller att välja det tillfället väl.

Tröttarobotproblemet är att, givet heltal n och m samt matrisen Os[1..n, 1..n], avgöra om det är möjligt för roboten att samla in exakt m gram osmium på sin väg från startrutan (1,1) till slutrutan (n,n).

Visa att tröttarobotproblemet är NP-fullständigt genom att dels visa att det ligger i NP och dels utforma en polynomisk Karpreduktion mellan det känt NP-fullständiga problemet delmängdssumma (se föreläsning 25) och tröttarobotproblemet.

I uppgift 1 är det viktigt att du visar att du kan principerna för NP-fullständighet och reduktioner. Ett fullständigt bevis för reduktionens korrekthet krävs inte.

I exemplet nedan har roboten rört sig ned till ruta (5,4) och kan nu backa tillbaka till ruta (4,4):

Uppgift 2 Färggrann kub av tärningar

Betygskriterium:  visa NP-fullständighet eller oavgörbarhet.

Visa att följande problem är oavgörbart.

Givet m stycken 6-sidiga typtärningar som har en färg per sida, går det, för varje positivt heltal n,  att bygga en n x n x n-kub av tärningar av dessa typer så att sidor som ligger emot varandra i kuben har samma färg? Du kan använda så många tärningar av varje typ som du behöver för att bygga en kub, men tärningarna får inte roteras, dvs färgerna måste vara i samma positioner som dom är i motsvarande typtärning i indata.

Använd Karpreduktion, inte Turingreduktion, när du visar att problemet är oavgörbart. Du får använda vilket som helst av dom känt oavgörbara problemen i föreläsning 23 i din reduktion.

Visa också att det, givet en instans och en "lösning" (eller snarare motexempel), i ändlig tid går att verifiera om det är en nej-instans till problemet. (Därmed kommer du att ha visat att problemet är co-R.E.-fullständigt.)

Uppgift 3 Konstruktion av väg för trött robot

Betygskriterium: utföra konstruktionsreduktioner.

Åter till tröttarobotproblemet i uppgift 1. Anta att det finns en algoritm CanGetExactAmount(n, m, Os[1..n,1..n]) som löser (det NP-fullständiga) beslutsproblemet. Din uppgift är nu att ta fram en algoritm som med hjälp av anrop till CanGetExactAmount löser konstruktionsproblemet, alltså problemet att ta fram en väg genom det sluttande planet (inklusive eventuell backning) som ger exakt m gram osmium.

Konstruera en effektiv Turingreduktion av konstruktionsproblemet till beslutsproblemet. Antalet anrop till CanGetExactAmount ska vara linjärt i indatas storlek, och för övrigt ska reduktionen ta polynomisk tid. Beskriv reduktionen med pseudokod. Om det finns en lösning ska en sträng som beskriver robotens väg genom matrisen returneras. Om det inte finns någon lösning ska tomma strängen returneras. Även om det finns flera möjliga lösningar så ska bara en returneras. Analysera tidskomplexiteten för din reduktion och motivera att den är korrekt.

Detaljerade bedömningskriterier

Mästarprov 2 betygsätts efter betygskriterierna för målen jämföra problem med hänsyn till komplexitet med hjälp av reduktioner samt analysera algoritmer med avseende på effektivitet och korrekthet. Dessutom kommer målet definiera och översätta centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet naturligt att övas vid redovisningen.

För att det ska bli extra tydligt hur dom tre uppgifterna bedöms och för att dom assistenter som tar emot redovisningar ska hålla precis samma kravnivå finns det detaljerade bedömningskriterier, som assistenterna bedömer både skriftligt och muntligt i ett bedömningsprotokoll.

Följande tabell visar kraven för dom olika uppgifterna.

Bedömningsgrund	Krav för uppgift 1	Krav för uppgift 2	Krav för uppgift 3
Fullständighet
Förklarar principerna för fullständighetsbevis	ja	nej	-
Förklarar vad en lösning/motexempel består av	ja	ja	-
Visar NP-tillhörighet/verifierbarhet	ja	ja	-
Motiverar att verifikationsalgoritmen (motsv.) är tillräckligt effektiv	ja, polynomisk	ja, ändlig	-
Reduktionsalgoritm
Beskriver reduktionen övergripande i ord och ev. i bild	måttliga	måttliga	höga
Beskriver reduktionen tydligt	ja	ja	ja, med pseudokod
Reduktionen är korrekt	ja	ja	ja
Tidskomplexitet för reduktionen
Reduktionen är tillräckligt effektiv	ja	ja	ja
Anger tidskomplexitet i lämpliga variabler	ja	ja	ja
Motiverar tidskomplexitet	måttliga	höga	höga
Korrekthetsresonemang
Redogör för vad som i allmänhet behöver visas i ett korrekthetsbevis av denna typ	ja	ja	ja
Framställer grundläggande idé för  korrekthetsresonemanget	nej	ja, åtminstone  åt ena hållet i den skriftliga inlämningen	ja
Genomför ett fullständigt korrekthetsresonemang	nej	ja, åtminstone muntligt	ja

Ovanstående krav ska vara uppfyllda efter den muntliga redovisningen. Kraven på den skriftliga lösningen är något lägre.

Bokning av muntlig redovisning

Boka senast den 3 december kl 15 en tid för 15 minuters muntlig redovisning 7-11 december i någon av bokningslistorna som anslås här 1 december.

Länk till bokningslistorna. Läs instruktionerna nedan innan du bokar!

Den tid som står på bokningslistesidan är tiden för den första redovisningen det aktuella redovisningspasset. Det är en tid var tjugonde minut. När du bokar en tid ska du därför notera vilken tid du får. Anmäl dig inte för redovisning för en assistent som du är nära vän med eller nära släkt med, på grund av jäv.

Bokningslistorna stängs för ändring efter deadline, så du kan inte byta redovisningstid efter 3 december.

Redovisningarna sker i Zoom. På bokningslistan står vilket Zoomrum  du ska gå till vid redovisningen. Du behöver ha kamera på vid redovisningen så att ID kan kontrolleras.

Redovisningen är 15 minuter, oavsett om du ska redovisa en, två eller tre av uppgifterna. Det är viktigt att du förbereder dig inför den muntliga redovisningen så att du snabbt kan svara på assistentens frågor. För att en uppgift ska godkännas ska du kunna förklara och motivera reduktioner och algoritmer muntligt och reda ut eventuella oklarheter.

Lösningsförslag

Lösningsförslag till mästarprov 2 kommer att publiceras här Download här

när alla muntliga redovisningar genomförts. Fram till dess är det inte tillåtet att diskutera uppgifterna med någon annan.

English version of the Swedish text

(Note: this is an English translation of the Swedish text. In case of any discrepancies between the two versions, the Swedish version is the authoritative one.)

The mastery test must be solved individually and presented both in writing and orally. No collaboration is allowed, see further the code of honour. In other words you must not discuss solutions with anyone
until all oral presentations have been conducted. This is something we take seriously. According to KTH regulations, suspected forbidden collaboration must be reported to the rector. The submissions are
checked for plagiarism.

Written solutions must be handed in in Canvas (as PDF; scanned handwritten solutions are fine) by Thursday December 3, 2020, at 15:00 (Stockholm time). It is important that you submit on time! If you do not see a submission button on this page, check that you are logged in to Canvas by clicking the login icon in the grey menu to the left.

Write your name and KTH address at the top of the front page of your solution. Read through your solutions before the oral presentation, which will be over Zoom between December 7 and 11 with one of the
assistants or teachers of the course. Book a time for a 15 minute oral presentation in Canvas no later than December 3, 15:00 (Stockholm time). The booking slots are published on December 1 at the bottom of
this page. If you book a slot but do not have time to finish the tasks you should simply cancel your booked slot.

It is important that you prepare for the oral presentation. In order for you to pass you should be able to explain and motivate the reduction/algorithm clearly and sort out any unclear parts.

Read the problems very carefully so that you do not accidentally base your solutions on a misconception. Ask a teacher on the course if something is unclear. The problem statements will also be discussed (in Swedish) at the lectures November 24 (problems 1 and 3) and November 25 (problem 2).

The mastery test is a mandatory part of the course. It consists of three problems corresponding to the grading criteria for E, C and A respectively. For a passing grade (E) you need to solve problem 1 or
2 completely and correctly. Solving both problems 1 and 2 completely and correctly gives grade C, and solving all problems gives grade A.
A smaller error on one problem lowers the grade one step. Read more about grades here.

If you solve problem 3 but only one of problems 1 and 2, you get a grade of E or D, but the result for problem 3 is saved in Canvas so you can later raise the grade to A by taking the oral exam problem for
grade C on mastery test 2 (since you thereby have shown fulfillment of the grading critera for all levels).

To see examples of how extensive the solutions should be you can look at solutions for earlier mastery tests, both authentic student solutions and model solutions. At that page there is also advice on how to formulate and execute mathematical proofs, which you should read before proving your reductions. Format/data structure for input and output can be choosen freely unless otherwise specified in the problem.

PROBLEM 1 TIRED ROBOT

Grading criteria: explain the principles, perform simpler reductions between given problems.

We will study a variant of problem 2 from mastery test 1.

A robot is located in the upper corner of a sloped plane shaped like a quadratic grid of size n-by-n. The entire plane is covered with thick snow and the robot does not have much battery charge left, so it needs
to use the slope of the plane to perform its mission before it runs out of battery. The mission is to collect a certain given amount of osmium, no more and no less, and then transport it to the lower corner
of the sloped plane. In each step the robot can move either one square down and to the left, or one square down and to the right, which means it can move from square (i, j) to either (i+1, j) or (i,j+1), see picture. But at one (and only one) step during the walk, the robot can back up and return to the square it just came from
(which means that it is going uphill - that this is even possible is because the snow in the squares passed by the robot have been flattened). The robot can never move outside the plane (the grid).

Luckily we know the exact amount of osmium available in each square in the grid. In grid (x,y) there is Os[x,y] grams of osmium (a non-negative integer). The first time the robot reaches a square, it gathers all the available osmium from that square, so if the robot returns to that square a second time there is no more osmium to gather there. It could still be beneficial for the robot to back up and return to the previous square since it then has a possibility to take a different route than the one it took the previous time. As mentioned, it can only back upwards a single time, so it is important to choose this time well.

The TiredRobot problem is, given integers n and m as well as the matrix Os[1..n, 1..n], decide if it is possible for the robot to gather exactly m grams of osmium on its way from the starting square (1,1) to the final square (n,n).

Show that the TiredRobot problem is NP-complete by (i) showing that it is in NP and (ii) designing a polynomial time Karp reduction between the known NP-complete problem Subset Sum (se lecture 25) and the TiredRobot problem.

In problem 1 it is important that you demonstrate that you know the principles of NP-completeness and reductions. A complete proof of correctness for the reduction is not needed.

In the example below the robot has moved to square (5,4) and can now back up to square (4,4):

PROBLEM 2 Colorful Cube of Dice

Grading criteria: show NP-completeness or undecidability.

Prove that the following problem is undecidable.

Given are m types of 6-side dice, each having a color per side, is it possible, for every integer n, to build an n-by-n-by-n cube of dice such that sides that are adjacent to each other have the same color? You can use as many dice as needed of each type to build a cube, but the dice cannot be rotated, i.e. the colors of the sides must be in the same positions as they are given in the input.

Use a Karp reduction, not a Turing reduction, when proving that the problem is undecidable. You may use any of the known undecidable problems from lecture 23 in your reduction.

Also show that, given an instance and a "solution" (or rather a counter-example), in finite time is possible to verify that the instance is a no-instance to the problem. (You will thereby have shown that the problem is co-RE-complete.)

 

PROBLEM 3 Construction of path for tired robot

Grading criteria: perform search reductions

We return to the TiredRobot problem from problem 1. Assume that there is an algorithm CanGetExactAmount(n, m, Os[1..n,1..n]) which solves the (NP-complete) decision problem. Your problem is now to design an algorithm which using calls to CanGetExactAmount solves the search problem, i.e., the problem of finding a path through the sloped plane (including a potential back up move), giving exactly m grams of osmium.

Design an efficient Turing reduction of the search problem to the decision problem. The number of calls to CanGetExactAmount should be linear in the size of the input, and the rest of the reduction should take polynomial time. Describe the reduction in pseudo code. If a solution exists a string describing the robot's path through the matrix should be returned. If no solution exists an empty string should be returned. Even if there might be more than one possible solutions, the algorithm should only return one of them. Analyze the time complexity of your reduction and motivate its correctness.

 

DETAILED GRADING CRITERIA

Mastery test 2 is grader based on the grading criteria for the learning outcomes "compare problems with respect to complexity using reductions" and "analyse algorithms with respect to efficiency and correctness".

To make it extra clear how the three problems are graded and in order for the assistants taking the presentations keeping the requirements at the same level, there are detailed grading criteria, which the assistants assess both in writing and orally using a grading sheet.

The following table shows the requirements for the different problems.

 

Criterium	Requirements for problem 1	Requirements for problem 2	Requirements for problem 3
Completeness
Explains the principles of a completeness proof.	yes	no	-
Explains what a solution/counter example consists of	yes	yes	-
Shows included in NP/verifiability	yes	yes	-
Motivates that the verification algorithm (corresponding) is efficient	yes, polynomial	yes, finite	-
Reduction algorithm
Describes the overall reduction in words and possibly illustrates it.	moderate	moderate	high
Describes the reduction clearly	yes	yes	yes, with pseudo code
The reduction is correct	yes	yes	yes
Time complexity for the reduction
The reduction is sufficiently efficient	yes	yes	yes
Specifies time complexity in suitable variables	yes	yes	yes
Motivates time complexity	moderate	high	high
Correctness arguments
Accounts for what needs to be shown in general in a correctness proof of this type	yes	yes	yes
Gives basic idea for the correctness argument	no	yes, at least in one direction in the written submission	yes
Gives a complete correctness argument	no	yes, at least orally	yes

 

The requirements above should be fulfilled after the oral presentation. The requirements on the written solutions are somewhat lower.

BOOKING AN ORAL PRESENTATION

Book before 15:00 at December 3 an appointment for a 15 minute oral presentation December 7-11 in one of the booking sheets that will be posted here on December 1.

Link to the booking sheets Read the instructions below before booking!

The time listed on the booking page is the time of the first presentation of the presentation session in question. There is one time every 20 minutes. When you book a time you must therefore make a note of exactly which time you get. Do not sign yourself up for a presentation with an assistant that you know well or are related to, to avoid conflict of interest.

The booking lists are closed after deadline, so you cannot change your presentation time after December 3.

The presentations are done in Zoom. On the booking page you find the information about which Zoom room you should go to for the presentation. You need to use camera at the presentation so that your ID can be checked.

The presentation is 15 minutes, regardless if you are presenting one, two or three of the problems. It is important that you prepare for the oral presentation so that you can quickly respond to the assistant's
questions. In order for a task to be accepted you should be able to explain and motivate reductions and algorithms orally, and sort out any unclear parts.

EXAMPLE SOLUTIONS

Example solutions for Mastery Test 2 will be published in the Swedish version of this page when all oral presentations have been conducted. Until then, it is not allowed to discuss the problems with anyone else.