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) senast onsdag 10 oktober 2018 klockan 13: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 personnummer överst på framsidan av lösningarna. Läs på dina lösningar inför den muntliga redovisningen som kommer att ske 15–19 oktober för någon av lärarna. Boka tid för en femton minuters muntlig redovisning i Canvas senast 10 oktober klockan 13. Bokningslistorna läggs upp senast 5 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.

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 Täckning av en kvadrat med L

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

Ett vanligt tidsfördriv är att försöka täcka en given yta med många likadana bitar. I denna uppgift ska du konstruera en algoritm som (nästan) täcker en kvadrat med sidan m=2ⁿ med bitar som ser ut som små L. Varje L-bit har ytan 3 och kan vridas och läggas på 4 sätt. Det går inte att täcka precis hela kvadraten, så innan vi börjar klipper vi bort en 1×1-ruta i övre högra hörnet på kvadraten. I vänstra figuren nedan visas hur en täckning av en 4×4-kvadrat med utklippt hörn kan göras.
Din algoritm ska ta m som indata (som måste vara en jämn tvåpotens) och returnera en m×m-matris som beskriver hur täckningen kan göras. Ge varje L ett eget nummer och märk dom tre platserna i matrisen som den täcker med detta nummer, se exemplet nedan till höger.
Din algoritm ska använda dekomposition för att konstruera täckningen. Lägg första L-biten precis mitt i kvadraten och dela sedan upp problemet i fyra delar.
Beskriv algoritmen med pseudokod. Analysera algoritmens tidskomplexitet (med enhetskostnad). Komplexiteten måste vara polynomisk i m, det vill säga O(m^k) för någon konstant k. (En sådan algoritm som är polynomisk i indatatalens storlek kallas pseudopolynomisk, vilket vi kommer att tala mer om i slutet av kursen.)

 $\left(\begin{array}{cccc} 5 & 5 & 2 & 0 \\ 5 & 1 & 2 & 2 \\ 4 & 1 & 1 & 3 \\ 4 & 4 & 3 & 3 \end{array} \right)$

Uppgift 2 Chokladoptimering

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

En oboist har fått ett genomskinligt rör med chokladbitar som tack för sina insatser på en fyrverkerikonsert. Oboisten äter en chokladbit varje dag, antingen från den vänstra eller högra änden av röret. (Vid varje läge är bara yttersta bitarna tillgängliga att plocka, för dom spärrar dom inre bitarna.)

Chokladbitarna är försedda med positiva heltal som berättar hur gott de smakar. Eftersom smak är subjektivt så finns det också en förväntanseffekt. En chokladbit blir lite godare för varje dag man väntar med att äta upp den. Om biten smakar m (som i mums) den första dagen så smakar den mk den k-te dagen.

Designa en effektiv algoritm som beräknar ett sätt att äta upp chokladen som optimerar oboistens lycka.

Din algoritm ska, givet chokladbitarnas initiala smakvärden, mata ut en följd med instruktioner (vänster eller höger) för hur chokladen ska ätas, till exempel höger höger vänster höger vänster vänster 

Beskriv algoritmen med pseudokod och analysera dess tidskomplexitet. Motivera också att algoritmen är korrekt.

Uppgift 3 Sjukhuskorridorsträning

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

Elvis Mammson som är chef för ett nybyggt sjukhus har kommit på att patienter som behöver motionera bör göra det genom att gå från sjukhusentrén upp till översta våningen och sen tillbaka. På uppvägen ska patienterna bara gå uppför trappor och på nedvägen bara gå nerför trappor. Så länge en patient befinner sig på samma våning så går den i samma riktning - den får alltså inte byta riktning mitt i korridoren. Det finns många trappor att välja på från en våning till nästa, men Elvis vill att patienterna ska använda den jobbigaste vägen. Hjälp honom att räkna ut denna väg!
Sjukhuset kan beskrivas som en rektangel bestående av n stycken våningar numrerade från 1 till n. Varje våning består av en enda m meter lång korridor. Var trapporna ligger i huset beskrivs av heltalsmatrisen S[1..n, 0..m]. Om S[i, j] > 0 så finns det en trappa från våning i till våning i+1, och den trappan startar j meter in i korridoren på våning i och kommer fram j meter in i korridoren på våning i+1. Det finns alltså som mest m+1 trappor upp från våning i till våning i+1, en per meter. Värdet S[i, j] anger hur jobbigt det är för en patient att ta den trappan uppåt eller nedåt (uttryckt i arbetsenheter). Dessutom kostar det 1 arbetsenhet per meter för patienten att gå i en korridor. 
Du ska konstruera en så effektiv algoritm som möjligt som givet S räknar ut vilken som är den jobbigaste vägen från sjukhusentrén i början på korridoren på bottenplanet (dvs vid meter 0 på våning 1) upp till Elvis kontor längst bort på översta våningen (dvs vid meter m på våning n) och sedan tillbaka igen till sjukhusentrén. Anta att det finns minst en trappa upp från varje våning till nästa, så att problemet säkert är lösbart. 
Analysera tidskomplexiteten (uttryckt i n och m) för en så effektiv algoritm som möjligt som löser problemet och returnerar det maximala jobbet och en väg som ger upphov till det jobbet. Visa också med en undre gräns att din algoritm är 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.

Förtydliganden av uppgiftslydelserna som gjorts efter den ursprungliga publiceringen

I uppgift 2 har "efter k dagars väntan" förtydligats till "den k-te dagen". Att indata är chokladbitarnas initiala smakvärden har också förtydligats.

I uppgift 3 har "alltså som mest m trappor" korrigerats till "alltså som mest m+1 trappor". Vad som ska returneras av algoritmen har förtydligats till "det maximala jobbet och en väg som ger upphov till det jobbet".

Formatet/datastruktur för indata och utdata ska du välja själv om det inte står specificerat i uppgiften.

Detaljerade bedömningskriterier