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 onsdag 7 december 2022 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 12 och 16 december i Zoom eller på KTH för någon av lärarna. 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 29 november (uppgift 1 och 2) och 1 december (uppgift 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 Artistproblemet

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

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 Grendosproblemet

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

I mästarprov 1 skulle ett elnät för notställsbelysning konstrueras. I denna uppgift gäller problemet också att sätta ihop ett elnät för notställsbelysning, men i detta fall är grendosorna givna, så problemet är att sätta ihop elnätet av givna komponenter.

Indata:

• oriktad graf $G=\langle V,E\rangle$
• källan $s\in V$ där vägguttaget (ett enda uttag) finns
• uppsättning med grendosor $g_1\ldots g_k$ där $g_i$ anger antalet uttag i grendosa i.
  Antalet uttag i en grendosa är ett heltal mellan 1 och |V|.

Fråga: Går det att förse alla hörn i grafen (utom källan) med el med hjälp av en delmängd av grendosorna? Grendosorna får bara ligga i grafens hörn (utom i källan), en dosa per hörn, och sladdarna bara gå längs grafens kanter. Alla kanter är lika långa, och en grendosas sladd räcker precis en kant. Ett hörn är försett med el om det finns minst ett ledigt uttag i grendosan som ligger i hörnet.

Visa att grendosproblemet är NP-fullständigt.

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 artistbokning

Betygskriterium: utföra konstruktionsreduktioner.

Vi återvänder till artistproblemet (se definitionen av problemet i uppgift 1). Anta att det finns en algoritm CanBookArtists som löser (det NP-fullständiga) beslutsproblemet som du definierade i uppgift 1 (om du inte löste uppgift 1 får du definiera det i uppgift 3 istället). Din uppgift är nu att ta fram en algoritm som med hjälp av anrop till CanBookArtists löser konstruktionsproblemet, alltså problemet att bestämma vilka artister som ska bo på vilket hotell för att så många artister som möjligt ska kunna bokas. Ä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 CanBookArtists ska vara högst kvadratiskt i indatas storlek, 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.

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 12 och 16 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örslag till mästarprov 2. Download Lösningsförslag till mästarprov 2.

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. 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, 2022, 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 12 and 16 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 29 (problems 1 and 2) and December 1 (problem 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 artist problem

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

Your company has been tasked with organizing a music festival. The goal is to book as many artists as possible, but the number of hotel places is limited. For each hotel, there is a limit to how many artists can be accommodated in that particular hotel. In addition, there are artists who cannot stay in the same hotel. These requirements are described by a list of pairs of artists who do not want to stay in the same hotel. Each artist is featured in at least one pair on the list.
The artist problem is to, given the number of seats in each hotel and a list of pairs of artists who do not want to stay in the same hotel, book as many artists as possible. You suspect that the problem is so difficult that it cannot be solved optimally in a reasonable time.
First formulate the artist problem as a decision problem by introducing a goal K. Then show that this decision problem is NP-complete by showing that it is included in NP and by designing a polynomial Karp reduction between the NP-complete problem Independent set and the artist problem.
In assignment 1, it is important that you show that you know the principles of NP-completeness and reductions. However, a complete proof of the correctness of the reduction is not required.

Assignment 2 The branch socket problem

Grading criterion: show NP-completeness or undecidability.

In mastery test 1, an electrical network for music stand lighting was to be constructed. In this assigment, the problem also applies to assembling an electrical network for music stand lighting, but in this case the branch sockets (junction boxes) are given, so the problem is to assemble the electrical network from given components.

Input:

• undirected graph $G=\langle V,E\rangle$
• the source $s\in V$ where the wall outlet (one single outlet) is
• set of branch sockets $g_1\ldots g_k$ where $g_i$ is the number of outlets in the branch socket i.
  The number of outlets in a branch socket is an integer between 1 and |V|.

Question: Is it possible to supply all vertices in the graph (except the source) with electricity using a subset of the branch sockets? The branch sockets may only be located in the vertices of the graph (except in the source), one socket per vertex, and the wires may only run along the edges of the graph. All edges are the same length, and a branch sockets's cord is just as long as one edge. A vertex is equipped with electricity if there is at least one free outlet in the branch socket located in the vertex.

Show that the branch socket problem is NP-complete.

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

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

Assignment 3 Construction of artist booking

Grading criterion: design constructive reductions.

We return to the artist problem (see the definition of the problem in assignment 1). Suppose there is an algorithm CanBookArtists that solves the (NP-complete) decision problem you defined in assignment 1 (if you didn't solve assignment 1, you need to define it in assignment 3 instead). Your task is now to develop an algorithm that, with the help of calls to CanBookArtists, solves the search problem (construction problem), i.e. the problem of deciding which artists should stay in which hotel so that as many artists as possible can be booked. Even if there might be more than one possible solution, the algorithm should only return one of them. 

Design an efficient Turing reduction of the search problem to the decision problem. The number of calls to CanBookArtists should be at most quadratic in the size of the input, and the rest of the reduction should take polynomial time. Describe the reduction in pseudo code. If no solution exists, an 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.

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

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.