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 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. Ta med lösningen på papper till övningen. Det går bra att lämna in en 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 labb 1 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). Fundera hur det går att implementera konkordansen på fil med användning av olika datastrukturer med avseende på följande egenskaper:

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

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

   • 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 snabbhet, minneskomplexitet och konstruktionsenkelhet för dessa datastrukturer i en tabell. Reflektera över varför ni ska använda just latmanshashning i labb 1.
4. Ge exempel på minst 7 indata (dvs ord) som är lämpliga testfall i labb 1 och motivera varför.
5. Konstruera en hashfunktion för latmanshashning och motivera varför den fungerar. Hashfunktionen ska ta ett ord som indata och returnera ett unikt hashvärde (heltal) baserat på ordets tre första bokstäver.