Mästarprov 1

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. Inlämningarna plagiatgranskas.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; inskannade handskrivna lösningar går bra) senast onsdag 9 oktober 2019 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 kontrollera att du är inloggad i Canvas. Klicka i så fall på inloggningsikonen i den blå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 14–18 oktober för någon av lärarna. Boka tid för en femton minuters muntlig redovisning i Canvas senast 9 oktober klockan 19. Bokningslistorna läggs upp senast 4 oktober, se 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 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. Formatet/datastruktur för indata och utdata ska du välja själv om det inte står specificerat i uppgiften.

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å en av uppgifterna. Helt rätt på två av uppgifterna 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.

För att se exempel på hur utförliga lösningarna bör vara kan du titta på lösningar till tidigare mästarprov på kurswebben. Där finns också tips om hur man skriver pseudokod, som du bör läsa innan du formulerar dina algoritmer. 

Uppgift 1 Nattparkering av långt godståg

Betygskriterium: utveckla algoritmer med datastrukturer för enkla problem givet en konstruktionsmetod.

Godståg kan vara mycket långa och ha vagnar av olika längd. SJ har en bangård med d parallella parkeringsspår där ett godståg ska nattparkeras. Alla parkeringsspår har längden m. Eftersom tåget är så långt behöver det delas upp i d delar genom att man lösgör d-1 vagnskopplingar. Varje del rullas sedan in på ett eget parkeringsspår. SJ vill att alla d spåren ska utnyttjas. Din uppgift är att konstruera en effektiv algoritm som givet d, m och ett godståg med vagnslängderna v₁, v₂, v₃, ..., v_n ska tala om ifall det är möjligt att få plats att nattparkera tåget på bangårdens d spår av längd m så att alla d spår används. Du kan anta att d<n.

Din algoritm ska vara en girig algoritm och uttryckt i pseudokod. Analysera algoritmens tidskomplexitet (med enhetskostnad). Komplexiteten måste vara polynomisk i n, det vill säga O(n^k) för någon konstant k.  Som alltid för giriga algoritmer måste du motivera att det giriga angreppssättet leder fram till en riktig lösning. Något korrekthetsbevis för din pseudokod behövs inte i denna uppgift, men du ska redogöra för vad som skulle behöva visas i ett korrekthetsbevis.

Om inmatningen exempelvis är d=3, m=13, v[1..8]=[3,4,4,2,10,6,3,4] så är svaret ja, eftersom det går att dela upp tåget i d=3 delar [3,4,4], [2,10], [6,3,4] som alla ryms på parkeringsspår av längd m=13, och alla 3 parkeringsspår används.

Uppgift 2 Förvirrad skalbagge

Betygskriterium: utveckla algoritmer med datastrukturer för icketriviala problem.

En skalbagge sitter på ett rektangulärt rutnät av storlek x gånger y. I vissa rutor finns det hinder. Skalbaggen är korkad och kryper vid varje tidsenhet slumpmässigt med samma sannolikhet en ruta åt norr, söder, väster eller öster. Den kan inte krypa i rutor där det finns ett hinder. Om det inte finns något hinder intill skalbaggen är sannolikheten 1/4 att den kryper åt ett visst håll. Om det finns ett hinder öster om skalbaggens ruta så är sannolikheten 1/3 att den kryper åt norr, 1/3 åt söder och 1/3 åt väster. Den slutar krypa om den ramlar av kanten på rutnätet. Vid tiden 0 befinner sig skalbaggen längst i nordväst (ruta (1,1) där det inte får finnas något hinder).

Konstruera en algoritm som, givet n, x, y och vilka rutor som har hinder på sig, beräknar sannolikheten P(n) för att skalbaggen efter n tidssteg fortfarande är kvar på rutnätet (det vill säga inte har ramlat av kanten).

Beskriv algoritmen med pseudokod och analysera dess tidskomplexitet. Den måste vara polynomisk i x, y och n. Motivera också att algoritmen är korrekt.

                                            norr

väster öster

                                          söder

I exemplet ovan kommer skalbaggen att röra sig med sannolikhet 1/3 en ruta åt norr, med sannolikhet 1/3 en ruta åt väster och med sannolikhet 1/3 ramla av rutnätet åt öster.

Uppgift 3 Optimal nattparkering av godståg

Betygskriterium: utveckla algoritmer med datastrukturer för svårare problem med den metod som passar bäst.

Denna uppgift bygger vidare på uppgift 1 ovan. SJ vill optimera nattparkeringen så att så kort del av parkeringsspåren som möjligt används. Mer specifikt ska tåget parkeras så att den längsta av tågets d delar är så kort som möjligt.

Konstruera en algoritm som givet d och vagnslängderna v₁, v₂, v₃, ..., v_n hittar och returnerar det minsta L så att tåget kan parkeras på d parkeringsspår av längd L (så att alla d spår används). Du kan anta att vagnslängderna är heltal mindre än n² och att d<n.

Algoritmen ska vara så effektiv som möjligt. Analysera tidskomplexiteten med bitkostnad (uttryckt i n) för en så effektiv algoritm som möjligt som löser problemet. Visa också med en undre gräns att din algoritm är optimal eller högst en logaritmisk faktor ifrån optimal.
Du ska också tydligt tala om vad som krävs (allmänt sett) för att bevisa korrektheten för den typ av algoritm som du skrivit och sedan bevisa korrektheten för algoritmen.

Detaljerade bedömningskriterier