Ommästarprov 1

  • Inlämningsdatum 4 jan 2023 av 19:00
  • Poäng 0
  • Lämnar in en filuppladdning
  • Filtyper pdf
  • Tillgänglig 19 dec 2022 kl 12:00–4 jan 2023 kl 19.30
Den här uppgiften låstes 4 jan 2023 kl 19.30.

Detta ommästarprov ger möjlighet att bli godkänd (betyg E) på mästarprov 1 (momentet MAS1).

Ommä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å. Inlämningarna plagiatgranskas. Misstänkt otillåtet samarbete och plagiat måste enligt KTH:s regler anmälas till rektor. Vid ordinarie mästarproven var vi tvungna att anmäla ett fall av misstänkt otillåtet samarbete.

Skriftliga lösningar ska lämnas in senast onsdag 4 januari 2023 klockan 19.00 i Canvas som PDF-dokument. Det är tillåtet att skriva för hand och skanna in dokumentet.

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på din inlämning inför den muntliga redovisningen som kommer att ske i Zoom under perioden 9-12 januari 2023. Boka tid för muntlig redovisning senast 4 januari klockan 19. Bokningslistorna läggs upp 3 januari sist på denna sida. 

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 uppgiften 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 i uppgiftslydelsen är oklart. Du kan skriva frågan i Canvas eller mejla den till viggo@kth.se

För godkänt (betyg E) på mästarprov 1 krävs helt rätt på uppgiften. 

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.

Mästarprov 1, E-uppgift

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

En springare i schack flyttar antingen två steg uppåt eller nedåt på schackbrädet, och sedan ett steg höger eller vänster, eller först två steg åt höger eller vänster och sedan ett steg uppåt eller nedåt.
Schackbräde med en springare och dom rutor som den kan hoppa till.
När man flyttar en springare så kommer man alltid till en ruta av annan färg: om springaren står på en vit ruta så hamnar den på en svart och tvärtom.
I den här uppgiften ska vi experimentera med en annan typ av pjäs: en k-l-springare. En k-l-springare flyttar antingen k steg uppåt eller nedåt på schackbrädet, och sedan l steg höger eller vänster, eller först k steg åt höger eller vänster och sedan l steg uppåt eller nedåt. Talen k och l är positiva heltal.
Din uppgift är att skriva en algoritm som tar indata n, k, l och färglägger ett nxn-bräde med två färger, svart och vitt, så att en k-l-springare alltid går till en ruta av den andra färgen. Om det inte är möjligt att skapa ett sånt bräde så ska din algoritm meddela detta. Om det finns flera möjliga lösningar så räcker det om algoritmen hittar en av dem. Du kan förutsätta att indata är positiva heltal och att k<n och l<n.
Beskriv algoritmen med pseudokod. Använd gärna en hjälpfunktion (beskriven med pseudokod) som returnerar en lista av alla möjliga drag – det gör koden mera lättläst.
Analysera tidskomplexiteten för algoritmen uttryckt i n. Komplexiteten måste vara polynomisk i n.
Algoritmen ska använda en djupetförst- eller breddenförstgenomgång som startas från varje plats på brädet.

Detaljerade bedömningskriterier

För att det ska bli extra tydligt hur uppgiften 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 på ett bedömningsprotokoll.

E-nivå för mästarprov 1

Mästarprov 1 betygsätts efter betygskriterierna för målen utveckla algoritmer med datastrukturer samt analysera algoritmer med avseende på effektivitet och korrekthet. Dessutom kommer målet jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet naturligt att övas vid algoritmkonstruktionen.

Bedömningsgrund Krav för
uppgift 1
Algoritmbeskrivning
Modellerar problemet på ett rimligt sätt nej
Beskriver algoritmen övertygande i ord och ev. i bild måttliga
Beskriver algoritmen i pseudokod ja
Bra urval av detaljer i pseduokoden måttliga
Algoritmen är tillräckligt effektiv polynomisk i n
Algoritmen löser rätt problem ja
Tidskomplexitet
Anger tidskomplexitet i lämpliga variabler ja
Motiverar tidskomplexitet måttliga
Korrekthetsresonemang
Redogör för vad som i allmänhet behöver visas i ett korrekthetsbevis av denna typ endast principerna
Framställer grundläggande idé för 
korrekthetsresonemanget		 nej
Genomför ett fullständigt korrekthetsresonemang 
som omfattar alla delar		 nej

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

Bokning av muntlig redovisning

Boka senast 4 januari 2023 klockan 19 en tid för en tiominuters muntlig redovisning av ommästarprov 1. Det är olika tider för redovisning av ommästarprov 1 och ommästarprov 2.

Här kommer länk till bokningslistor att läggas upp 3 januari.

Läs instruktionerna nedan innan du bokar!

Redovisningen är 10 minuter och sker i Zoom. Du ska ha kameran på och vara beredd att visa ID vid redovisningen.

Den tid som står på bokningslistesidan är tiden för den första redovisningen det aktuella redovisningspasset. När du bokar en tid ska du därför notera vilken tid du får. 

Bokningslistorna stängs för ändring efter deadline, så du kan inte byta redovisningstid efter 4 januari.

Det är 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 reduktioner och algoritmer muntligt och reda ut eventuella oklarheter.

1672855200 01/04/2023 07:00pm