Teoriuppgifter till labb 2

Dessa teoriuppgifter hör till labb 2 och kan redovisas för en teoripoäng till tentan. Redovisningen görs skriftligt och muntligt på övningen den 17 september (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom. Arbeta gärna i grupp med labbteoriuppgifterna, men var och en ska vid redovisningen ladda upp lösningen som PDF-dokument. Om det är flera som samarbetat om lösningen ska det framgå klart (se hederskodex).  Det går bra att lämna in en inskannad handskriven lösning.

Teoriuppgifter

Sätt dig in i hur det givna programmet fungerar och svara sedan på följande frågor.

1. Formulera rekursionen (partDist i programmet) så kompakt som möjligt med matematisk notation.

2. Beräkna partDist("labd", "blad", x, y) för alla x och y mellan 0 och 4 och för in värdena i en matris M. Vad blir M?

3. Vad är det alltså metoden partDist(w1, w2, x, y) beräknar?

4. Visa att tidskomplexiteten för Distance(w1, w2) är exponentiell i ordlängden. Du kan anta att w1 och w2 har samma längd.

5. Visa hur man kan spåra vilka editeringsoperationer som görs i den kortaste editeringsföljden från "labd" till "blad" genom att titta på matrisen M.

6. Visa med pseudokod hur rekursionen kan beräknas med dynamisk programmering, dvs hur en dynprogmatris M kan skapas. Vilken beräkningsordning är lämplig vid beräkning av M?

7. Analysera tidskomplexiteten för att bestämma editeringsavståndet mellan ett n-bokstavsord och ett m-bokstavsord med dynamisk programmering.

8. Beräkna dynprogmatrisen för editeringsavståndet mellan "labs" och "blad".

9. Vilken del av matriserna för "labd"-"blad" och "labs"-"blad" skiljer?

10. Allmänt sett, vilken del av matriserna för Y-X och Z-X skiljer när orden Y och Z har samma första p bokstäver?