Teoriuppgifter till labb 2

Inlämningsdatum 23 sep 2021 av 13.15
Poäng 1

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 23 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 ha med en lösning. Om det är flera som samarbetat om lösningen ska du se till att det framgår klart (se hederskodexLänkar till en externa sida.). Ö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 ladda upp en PDF med lösningen.

Läsanvisningar för teoriuppgifterna:

labblydelsen och den givna programkoden
videorna och förberedelseuppgifterna till föreläsning 9 (dynamisk programmering del 1)
sida 251-260 i KT (Kleinberg-Tardos)

Teoriuppgifter

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

Formulera rekursionen (partDist i programmet) så kompakt som möjligt med matematisk notation.
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?
Vad är det alltså metoden partDist(w1, w2, x, y) beräknar?
Visa att tidskomplexiteten för Distance(w1, w2) är exponentiell i ordlängden. Du kan anta att w1 och w2 har samma längd.
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.
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?
Analysera tidskomplexiteten för att bestämma editeringsavståndet mellan ett n-bokstavsord och ett m-bokstavsord med dynamisk programmering.
Beräkna dynprogmatrisen för editeringsavståndet mellan "labs" och "blad".
Vilken del av matriserna för "labd"-"blad" och "labs"-"blad" skiljer?
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?