Teoriuppgifter till labb 1

Dessa teoriuppgifter hör till labb 1 och kan redovisas för en teoripoäng till tentan. Redovisningen görs skriftligt och muntligt på övningen den 3 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

1. Vilka är rollerna vid parprogrammering och vilka uppgifter har varje roll?
2. Indexinformationen för ett ord (det vill säga i vilka teckenpositioner ordet förekommer i den stora texten) kan bli mycket stor. Hur bör positionerna lagras för att det ska bli effektivast, som text eller binärt (data streams i Java)? Bör indexinformationen lagras tillsammans med själva ordet eller på ett separat ställe?
3. I denna labb ska datastrukturen för konkordansen huvudsakligen ligga på fil, vilket betyder att sökningar görs i filen istället för som vanligt i internminnet. Det påverkar till exempel hur man representerar pekare (lämpligen som bytenummer i filen). Diskutera för- och nackdelar med olika implementationer av konkordansen med avseende på följande egenskaper:

   • snabbhet (antal filläsningar och filpositioneringar per sökning),

   • minneskomplexitet för fillagringen (bara konstant mycket internminne ska användas)

   • enkelhet att konstruera och lagra på fil.

   Ta åtminstone upp följande datastrukturer:

   • binärt sökträd,

   • sorterad array,

   • hashtabell,

   • trie (träd där varje nivå motsvarar en bokstav i ordet),

   • latmanshashning

   Redovisa för- och nackdelarna i en tabell. 
4. Ge exempel på minst 7 indata (dvs ord) som är lämpliga testfall i labb 1 och motivera varför.