Mästarprov 2

Inlämningsdatum 7 dec 2023 av 19:00
Poäng 0
Lämnar in en filuppladdning
Filtyper pdf
Tillgänglig 23 nov 2023 kl 15:00–15 dec 2023 kl 17:00

Den här uppgiften låstes 15 dec 2023 kl 17:00.

Svenska
English

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. Vi tar mycket allvarligt på detta och följer KTH:s riktlinjer om att misstänkta fall av samarbete ska anmälas till rektor. Du får inte använda generativ AI för att lösa mästarprovsuppgifterna. Däremot får du gärna använda generativ AI för att typsätta med LaTeX. Inlämningarna plagiatgranskas.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; inskannade handskrivna lösningar går bra) senast torsdag 7 december 2023 klockan 19.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 11 och 15 december i Zoom eller på KTH för någon av lärarna eller assarna. Boka tid för en 10 minuters (om du har löst en uppgift) eller 20 minuters (om du har löst 2-3 uppgifter) muntlig redovisning i Canvas senast 7 december klockan 19:30. Bokningslistorna läggs upp den 6 december sist på denna sida. Vänta med att boka tid tills du har lämnat in dina lösningar.

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å ett felaktigt antagande. Fråga en lärare på kursen om något är oklart. Uppgiftslydelserna kommer också att gås igenom på föreläsningen 27 november (uppgift 1) och 29 november (uppgift 2 och 3).

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 (uppgift 3 examinerar kriterierna för A som inte inkluderar kriterierna för E eller C). 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 under rubriken Examination och slutförande i kurs-PM.

Den som blir godkänd på uppgift 3 men bara på 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 Skärmlagningsproblemet

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

Din mobilskärm (eller datorskärm, det är inte så noga) har skadats efter lång tids användning. Skadorna är antingen repor (raka streck) eller hack (punktformade). Du har tillgång till en uppsättning cirkulära lagningslappar som du vill använda för att laga alla skärmens skador. Skärmlagningsproblemet är att, givet en lista med alla skärmens skador och en lista med dom tillgängliga cirkulära lagningslapparna, laga alla skador med så få av dessa lappar som möjligt. Det finns tillräckligt med lagningslappar för att alla skador ska kunna lagas. En skada anses lagad om minst en lagningslapp placerats över hela skadan. En lång repa kan behöva flera lagningslappar.

Varje skada representeras i indata antingen med x- och y-koordinater (om det är ett punktformat hack) eller x- och y-koordinater för start- och ändpunkt (om det är en linjeformad repa). Varje lagningslapp representeras i indata med sin radie. Alla tal i indata kan antas vara rationella tal som går att räkna med (alla taloperationer kan antas gå i konstant tid i denna uppgift).

Formulera först skärmlagningsproblemet som ett beslutsproblem genom att införa ett mål K. Visa sedan att detta beslutsproblem ä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 Täckning med enhetsskivor och skärmlagningsproblemet.

Problemet täckning med enhetsskivor tar som indata

$n$ punkter i planet $LaTeX: p_1, p_2, \ldots, p_n$

$p_1, p_2, \ldots, p_n$ (representerade med koordinater) och ett mål

$U$ . Frågan är om det går att täcka alla punkter genom att placera ut

$U$ enhetsskivor på planet, där en enhetsskiva är en skiva vars rand är en cirkel med radien 1.

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 däremot inte.

Uppgift 2 Regionindelningsproblemet

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

Indata till regionindelningsproblemet är en tvådimensionell karta med $n$ stycken distrikt som innehåller $LaTeX: x_1, x_2, x_3, \ldots, x_n$ $x_1, x_2, x_3, \ldots, x_n$ personer, samt tre ickenegativa heltal $k$ , $LaTeX: s_{1}$ $s_{1}$ och $LaTeX: s_{2}$ $s_{2}$ , där $LaTeX: s_1\le s_2$ $s_1\le s_2$ .

En region är en delmängd av distrikten där alla ingående distrikt gränsar till varandra, dvs utgör en sammanhängande komponent. (Det räcker att två distrikt möts i en punkt för att dom ska anses gränsa till varandra. Varje distrikt är i sig sammanhängande, men liksom en region kan det bestå av delar som möts i en punkt.) Samma distrikt får inte ingå i flera regioner.

Frågan är: går det att hitta $k$ stycken olika regioner som alla innehåller mellan $LaTeX: s_{1}$ $s_{1}$ och $LaTeX: s_{2}$ $s_{2}$ personer (dvs minst $LaTeX: s_{1}$ $s_{1}$ och högst $LaTeX: s_{2}$ $s_{2}$ personer)?

Visa att regionindelningsproblemet är NP-fullständigt.

Du får själv välja hur kartan ska representeras i indata. (Representationen behöver bara fånga dom egenskaper som är relevanta för problemet, inte geometrin.) Anta att det finns en operation som i konstant tid avgör om två distrikt gränsar till varandra.

I reduktionen ska du som känt NP-fullständigt problem använda något av dom problem som listats som eller visats vara NP-fullständiga problem på föreläsning 25 (se föreläsningsbilderna), inget annat problem.

Använd Karpreduktion, inte Turingreduktion, när du visar att problemet är NP-svårt.

Uppgift 3 Konstruktion av regionindelning

Betygskriterium: utföra konstruktionsreduktioner.

Vi återvänder till regionindelningsproblemet som definierades i uppgift 2, men vi betraktar här det lite generellare optimeringsproblemet där det gäller att maximera antalet regioner som alla innehåller mellan $LaTeX: s_{1}$ $s_{1}$ och $LaTeX: s_{2}$ $s_{2}$ personer. Anta att det finns en algoritm ExistRegions som löser (det NP-fullständiga) beslutsproblemet som definierades i uppgift 2. Din uppgift är nu att ta fram en algoritm som med hjälp av anrop till ExistRegions löser konstruktionsproblemet, alltså problemet att bestämma vilka distrikt som ska ingå i var och en av det maximala antalet regioner. Även om det finns flera möjliga lösningar så ska bara en returneras.

Konstruera en effektiv Turingreduktion av konstruktionsproblemet till beslutsproblemet. Antalet anrop till ExistRegions ska vara högst kvadratiskt i $n$ (antalet distrikt), och i övrigt ska reduktionen ta polynomisk tid. Beskriv reduktionen med pseudokod. Om det inte finns någon lösning ska tomma mängden returneras. Analysera tidskomplexiteten för din reduktion och motivera att reduktionen ä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
NP-fullständighet/NP-tillhörighet
Förklarar principerna för fullständighetsbevis	ja	nej	-
Formulerar problemet som beslutsproblem	ja	-	-
Förklarar vad en lösning består av	ja	ja	-
Visar NP-tillhörighet	ja, pseudokod krävs inte	ja, pseudokod krävs inte	-
Motiverar att verifikationsalgoritmen (motsv.) är polynomisk	ja	ja	-
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, med invarianter

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

Om uppgift 2 redovisas för betyg E (dvs om uppgift 1 inte lösts/godkänts) används betygskriterierna för E (uppgift 1) vid bedömningen.

Bokning av muntlig redovisning

Tider för muntlig redovisning kommer att finnas mellan 11 och 15 december.

Lämna in din skriftliga lösning i Canvas innan du bokar tid för muntlig redovisning. Du kan boka tid fram till kl 19:30 den 7 december. Efter det är tiderna fixa och kan inte ändras.

Observera att det är olika bokningslistor för den som redovisar för betyg E och för den som redovisar för betyg A-D. Den som bara har gjort en uppgift, eller som har försökt på flera uppgifter men bara till kriterienivå E, ska boka tid på en lista märkt "för betyg E". Den som har löst flera uppgifter ska boka tid på en lista märkt "för betyg A-D".

Länk till bokningslistorna kommer att publiceras här den 6 december.

På bokningslistan står om redovisningen sker i Zoom eller på KTH. Du ska i båda fallen kunna visa ID vid redovisningen.

Redovisningen är 10 minuter om du redovisar för betyg E och 20 minuter om du redovisar för betyg A-D. Det är i båda fallen 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 algoritmen muntligt och reda ut eventuella oklarheter.

Lösningsförslag

Lösningsförslag till mästarprov 2 kommer att publiceras här när alla muntliga redovisningar genomförts. Fram till dess är det inte tillåtet att diskutera uppgifterna med någon annan.

Lösningsförslaget Download Lösningsförslaget

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 president. You may not use generative AI to solve the mastery test preoblems. However, you are welcome to use generative AI for typesetting with LaTeX. The submissions are checked for plagiarism.

Written solutions must be handed in in Canvas (as PDF; scanned handwritten solutions are fine) by Wednesday December 7, 2023, at 19: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 or at KTH between December 11 and 15 with one of the assistants or teachers of the course. Book a time slot for a 10 minute oral presentation (if you have solved one assignment) or 20 minute oral presentation (if you have solved 2-3 assignments) no later than December 7, 19:30 (Stockholm time). The booking slots are published on December 6 at the bottom of this page. Do not book a slot until you have submitted your written solutions.

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 assignments 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 27 (problem 1) and November 29 (problems 2 and 3).

The mastery test is a mandatory part of the course. It consists of three assignments 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 in the course memo (in Swedish).

If you solve assignment 3 but only one of assignment 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 assignment.

Assignment 1 The Screen Repair Problem

Grading criterion: explain the principles, carry out simple reductions between given problems.

Your mobile screen (or computer screen, it does not matter) has been damaged by years of use. The damages are either scratches (straight line segments) or cuts (point-shaped). You have access to a set of circular mending patches that you want to use to repair the screen's damages. The Screen Repair Problem is, given a list of all the screen's damages, and a list of the available circular mending patches, to fix all damages with as few patches as possible. It is guaranteed that there are enough patches in order to repair all damages. A damage is considered repaired if every point of the damage has been covered with at least one mending patch. A long scratch might require several mending patches.

Every damage is represented in the input with either its x- and y-coordinates (if it is a point-shaped cut) or the x- and y-coordinates of its start point and end point (if it is a straight line scratch). Every mending patch is represented in the input by its radius. All numbers in the input can be assumed to be rational numbers that can be exactly operated on (all numeric operations are assumed to take constant time in this problem).

First, formulate the Screen Repair Problem as a decision problem by introducing a target K. Then show that this decision problem is NP-complete by both proving that it is in NP and designing a polynomial time Karp reduction between the known NP-complete Unit Disc Cover Problem and the Screen Repair Problem.

The Unit Disc Cover Problem takes as input

$n$ points in the plane $LaTeX: p_1, p_2, \ldots, p_n$

$p_1, p_2, \ldots, p_n$ (represented by their coordinates) and a target

$U$ . The question is whether all the given points can be covered by placing

$U$ unit discs in the plane, where a unit disc is the region covered by a circle with radius 1.

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

Assignment 2 The Region Division Problem

Grading criterion: show NP-completeness or undecidability.

The input for the Region Division Problem is a 2-dimensional map with $n$ districts, containing $LaTeX: x_1, x_2, x_3, \ldots, x_n$ $x_1, x_2, x_3, \ldots, x_n$ people (respectively), together with three non-negative integers $k$ , $LaTeX: s_{1}$ $s_{1}$ and $LaTeX: s_{2}$ $s_{2}$ , where $LaTeX: s_1\le s_2$ $s_1\le s_2$ .

A region is a subset of the districts where all included districts are adjacent to each other, i.e. is a connected component. (It is enough that two districts meet in a single point to be considered adjacent. Every district is connected, but just like a region it can consist of parts that meet in a single point.) The same district cannot be included in more than one region.

The problem is: does there exist $k$ different regions which each contain between $LaTeX: s_{1}$ $s_{1}$ and $LaTeX: s_{2}$ $s_{2}$ people (i.e., at least $LaTeX: s_{1}$ $s_{1}$ and at most $LaTeX: s_{2}$ $s_{2}$ people)?

Prove that the Region Division Problem is NP-complete.

You may choose how the map should be represented in the input. (The representation only needs to capture the properties that are relevant for the problem, not the geometry.) Assume that there is an operation that in constant time can tell whether two districts are adjacent to each other.

In the reduction, you must as your known NP-complete problem use one of the problems listed as or shown to be NP-complete in lecture 25 (see slides (in Swedish)), no other problem.

Use a Karp reduction, not a Turing reduction, when showing that the problem is NP-hard.

Assignment 3 Region Division Search

Grading criterion: design constructive reductions.

We return to the Region Division Problem as defined in assignment 2, but we now look at the slightly more general optimization problem where the objective is to maximize the number of regions that contain between $LaTeX: s_{1}$ $s_{1}$ and $LaTeX: s_{2}$ $s_{2}$ people. Assume that there is an algorithm ExistRegions which solves the (NP-complete) decision problem defined in assignment 2. Your task now is to design an algorithm which, using calls to ExistRegions, solves the search problem, in other words the problem of choosing which districts should be part of which region in a region division of maximum size. If there is more than one possible solution, only one solution should be returned.

Design an efficient Turing reduction from the search problem to the decision problem. The number of calls to ExistRegions should be at most quadratic in $n$ (the number of districts), and the rest of the reduction should take polynomial time. Describe the reduction with pseudo code. If there is no solution, the empty set should be returned. Analyze the time complexity of your reduction and motivate its correctness.

Detailed grading criteria

The grading of Mastery test 2 is 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". In addition, the learning outcome "define and translate central concepts as P, NP, NPcompleteness and undecidability" naturally be trained at the presentation.

To make it extra clear how the three assignments are graded and in order for the TAs taking the presentations to keep 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 assignments.

Criterium	Requirements for assignment 1	Requirements for assignment 2	Requirements for assignment 3
Completeness
Explains the principles of a completeness proof.	yes	no	-
Formulates the problem as a decision problem	yes	-	-
Explains what a solution/counter example consists of	yes	yes	-
Shows inclusion in NP	yes, pseudo code is not required	yes, pseudo code is not required	-
Motivates that the verification algorithm (or corresponding) is polynomial	yes	yes	-
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.

If assignment 2 is used for grade E (i.e. if assignment 1 is not solved/passed), the grading criteria for E (assignment 1) are used in the assessment.

Booking an oral presentation

Slots for oral presentations are available between December 11 and 15.

Submit your written solution in Canvas before booking an appointment for an oral presentation. You can book an appointment until 19:30 on December 7. After that, the times are fixed and cannot be changed.

Please note that there are different reservation lists for those who report for grades E and for those who report for grades A-D. Anyone who has only done one assignment, or who has attempted several assignments but only to criterion level E, must book an appointment on a list marked "för betyg E". Anyone who has solved several problems and reaches criterion level C on task 2 or 3 must book an appointment on a list marked "för betyg A-D".

Link to the reservation lists will be published here on December 6.

The reservation list states whether the presentation takes place in Zoom or at KTH. In both cases, you must be able to show ID when reporting.

The time slot for oral presentation is 10 minutes if you report for grade E and 20 minutes if you report for grades A-D. In both cases, it is important that you prepare for the oral presentation so that you can quickly answer the assistant's questions. In order for an assignment to be approved, you must be able to explain and justify the algorithm orally and clear up any ambiguities.

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 assignments with anyone else.