Övningsmästarprov 1

Det riktiga mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Detta övningsmästarprov,  som redovisas skriftligt och muntligt under övningstillfället 28 september, får däremot mycket gärna lösas i tvåpersonsgrupp. Det är dessutom tillåtet att diskutera det i ännu större grupper. Var och en ska vid redovisningen ha med en lösning. Om det är flera som samarbetat om lösningen ska du se till att det framgår klart (se hederskodex). Överarbeta inte lösningen - den behöver inte se snygg ut. Det går bra att lämna in en (inskannad) handskriven lösning. Om du redovisar i övningssal ska du ta med en utskrift av lösningen; om du redovisar i Zoom ska du under övningen ladda upp en PDF med lösningen.

Vid övningen kommer lösningarna att kamraträttas enligt samma kriterier som används vid det ordinarie mästarprovet. Den som vid övningstillfället redovisar ett gott försök till lösning (den behöver inte vara korrekt i alla delar) får en teoripoäng.

Övningsmästarprovet är frivilligt, till skillnad från det ordinarie mästarprovet som är ett obligatoriskt moment i kursen. Det ordinarie mästarprovet består av tre uppgifter som motsvarar betygskriterierna för E, C respektive A. Övningsmästarprovet har bara en uppgift, och den motsvarar betygskriterierna för E. För att se exempel på hur utförliga lösningarna bör vara kan du titta på lösningar till tidigare mästarprov.  Där finns också tips om hur man skriver pseudokod.

Kortaste texten

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

En text består av n stycken ord. Ordens längd i tecken betecknas w₁, ..., w_n (i samma ordning som orden förekommer i texten). För enkelhets skull ingår skiljetecken (som punkt och komma) i det ord dom följer, så vi slipper skilja på bokstäver och skiljetecken. När vi skriver ner texten ska det som vanligt stå ett mellanslag mellan två ord som följer på varandra på samma rad. Målet är att formatera texten (utan avstavningar) så att den ryms på så få rader av längd len som möjligt. Ordens inbördes ordning ska bibehållas.

Konstruera och beskriv pseudokoden för en effektiv girig algoritm som givet n, len och w₁, ..., w_n beräknar och returnerar det minimala antalet rader av längd högst len som texten kan skrivas ner på. Du kan anta att inget enskilt ord i texten är längre än len tecken.

Som vanligt för giriga algoritmer ingår det att motivera att algoritmen returnerar det optimala värdet. Det brukar vara en större utmaning än att utveckla själva algorimen, som ibland kan vara närmast trivial. Analysera också tidskomplexiteten för algoritmen (med enhetskostnad).

Exempel på en text och motsvarande indata till problemet:

"Tidskomplexiteten O(1) betyder att komplexiteten är oberoende av indatas längd."

n=10, len=25, w₁=17, w₂=4, w₃=7, w₄=3, w₅=13, w₆=2, w₇=9, w₈=2, w₉=7, w₁₀=6.

Den optimala lösningen är 4 rader.

Bedömningskriterier

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.

Ovanstående krav ska vid det ordinarie mästarprovet vara uppfyllda efter den muntliga redovisningen, där oklarheter och små ofullkomligheter och fel kan redas ut. Kraven på den skriftliga lösningen är något lägre.

Lösningsförslag och övningsbedömning

På övningsmästarprovsövningen kommer en lösning till uppgiften att gås igenom och en kamratbedömning av övningsmästarprovet att göras med hjälp av ett rättningsprotokoll Download rättningsprotokoll. Vid det riktiga mästarprovet kommer ett sådant rättningsprotokoll att användas vid bedömningen.