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 tisdag 12 oktober 2021 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 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 individuella muntliga redovisningen som kommer att ske 18–26 oktober 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 senast 12 oktober klockan 18. Bokningslistorna läggs upp 11 oktober (nytt datum), se sist på denna sida. Vänta med att boka tid tills du har lämnat in uppgiften.

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 under rubriken Examination och slutförande i kurs-PM.

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 skriver pseudokod, som du bör läsa innan du formulerar dina algoritmer. 

Uppgift 1 Färgsortering med minimalt antal hällningar

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

Det finns ett populärt färgsorteringsspel som du ska skriva en algoritm för att hitta lösningen till. Lösningen är det minsta antalet hällningar som krävs för att färgerna ska bli helt sorterade. Indata är 14 stycken rör som rymmer n liter var, och ett startläge med färger (alltid heltalsmängder av varje färg) i varje rör. Man får bara hälla från ett rör till ett annat om det är samma färg överst i båda rören eller det andra röret är tomt, och bara om hela mängden av den färg som är överst i första röret får plats i andra röret. I en hällningsoperation för man alltså över den färg som är överst i ett rör till ett annat rör, som antingen redan har samma färg överst eller som är tomt. Färgerna blandar sig aldrig med varandra. Titta på denna video Links to an external site. för att se hur en färgsortering med n=4 kan fungera.

Det finns 12 olika färger, representerade av alfabetets 12 första bokstäver A-L. Rörens ursprungliga innehåll beskrivs i indata som en array av n bokstäver för varje provrör, där varje bokstav motsvarar en liter färg, och där mellanslag motsvarar en liters tomrum i röret. Det finns totalt n liter av varje färg. Varje rörs innehåll anges uppifrån och ner, se följande exempel på hur ett rör kan representeras med en array av bokstäver (n=5):

Du ska skriva en algoritm som med hjälp av breddenförstsökning från startpositionen (det ursprungliga innehållet i dom 14 rören) beräknar det minsta antalet hällningar som krävs för att färgerna ska bli helt sorterade, dvs att varje rör antingen är helt fyllt av samma färg eller är helt tomt. Algoritmen ska skriva ut en följd av hällningar som ger en optimal lösning (t ex Häll rör 9 till rör 7. Häll rör 3 till rör 7. Häll rör 2 till rör 4. etc.). Om det inte finns någon lösning ska algoritmen skriva ut det. Exakt format för indata och utskrift väljer du själv.

Algoritmen ska hålla reda på vilka positioner som hittills har uppstått genom hällningar så att den inte behöver gå igenom samma position flera gånger. Beskriv algoritmen med pseudokod, visa dels att tidskomplexiteten är exponentiell i n (dvs O(cⁿ) för en konstant c) och dels att utskriftens längd är linjär i n.

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.

Uppgift 2 Antal sätt att producera ett prov

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

N stycken lärare ska producera x stycken uppgifter till ett prov. Lärare nummer i kan göra mellan 0 och u[i] uppgifter, där u[i] är högst 10. På hur många olika sätt kan man fördela jobbet?

Exempel: Två lärare (N=2) som var för sig kan göra max 2 uppgifter (u[1]=u[2]=2) kan producera ett mästarprov med 3 stycken uppgifter (x=3) på två olika sätt: 1+2 eller 2+1.

Deluppgift 2.1

Konstruera en algoritm som givet N, x och u[1..N] beräknar antalet sätt som jobbet kan fördelas på. Om det inte finns något sätt ska 0 returneras.

Beskriv algoritmen med pseudokod och analysera dess tidskomplexitet. Tidskomplexiteten måste vara polynomisk i N, dvs O(N^c) för en konstant c. Motivera också att algoritmen är korrekt.

Deluppgift 2.2

Skriv en funktion print_all_ways som skriver ut alla sätt som jobbet kan fördelas på. I exemplet ovan ska funktionen alltså skriva ut:

1+2
2+1

Det finns inget krav på i vilken ordning delresultaten ska skrivas ut.

Även denna algoritm ska beskrivas med pseudokod. Utöver tydlig och väldokumenterad pseudokod behöver du däremot inte motivera korrekthet och du behöver inte heller analysera tidskomplexiteten.

Uppgift 3 Optimal anagramanalys

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

Ett anagram är två ord som innehåller samma bokstäver fast i olika ordning, t ex stativ och tvista eller enradig och idegran. Du kan i denna uppgift inte anta att det finns någon specifik begränsning på antalet bokstäver i alfabetet (kinesiska "alfabetet" är till exempel väldigt stort).
Konstruera och analysera tidskomplexiteten för en algoritm som avgör ifall två ord är anagram, och om dom är det returnerar en permutation av det andra ordet som ger det första.

Exempel: Om indata är stativ, tvista ska algoritmen returnera 1, 5, 4, 0, 3, 2 (eller 3, 5, 4, 0, 1, 2). Om indata är enradig, idegran ska 5, 4, 0, 6, 2, 3, 1 returneras.

Algoritmen ska vara så effektiv som möjligt, med tidskomplexiteten uttryckt med en ordoklass i n, längden på indata. I denna uppgift får du anta att vanliga taloperationer på två heltal som är högst n kan göras i konstant tid (alltså en något begränsad version av enhetskostnad). Du får också anta att insättning och sökning i en hashtabell tar konstant tid.

Du ska visa att din algoritm är optimal (med avseende på ordoklass). 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 din algoritm. Formulera invarianter för slingor och ingångs- och utgångsvillkor för hjälpfunktioner.

Detaljerade bedömningskriterier