Hemtal 2

Hemtal 2

          Hashning

          Läs avsnittet Hashing i kapitlet Sorting and Searching i kursboken

          Besvara sedan följande frågor:

1. I Spotify finns ca femton miljoner låtar. Hur stor ska hashtabellen vara? (betyg E)
2. Föreslå en hashfunktion för ett låtnamn, t ex "The Axoltl song". (betyg E)
3. Rita och beskriv hur krockhantering med krocklistor fungerar. (betyg E)
4. Skulle man kunna använda ett bloomfilter för Spotifys låtar? Motivera ditt svar! (betyg C)
5. Hur skulle man kunna lägga upp hashningen om man vill kunna söka på både låtnamn och artist? Beskriv din plan tydligt, och redogör för eventuella problem/nackdelar med ditt tillvägagångssätt. (betyg A)
   
   
   

   Problemträd

   Läs om Breadth First Search och Depth First Search i kursboken
   
   

   Besvara sedan följande frågor:

6. Använder man en stack eller en kö i djupetförstsökning? Förklara varför. (betyg E)
7. Vilken komplexitet har breddenförstsökning? Definiera ingående variabler. (betyg E)
8. Är djupetförstsökning eller breddenförstsökning bättre om problemträdet har oändligt djup? Eller spelar det ingen roll? Motivera. (betyg C)

9. 8	1	6
   3	5	7
   4	9	2

   En magisk kvadrat är en kvadrat med sidan n som innehåller alla tal \(1, 2, ... n^{2}\) placerade så att summan av talen i varje rad, kolumn och diagonal blir densamma, se exemplet ovan. Anta att vi vill skriva ett program som för ett givet n hittar alla magiska kvadrater. Gör en steg-för-steg-beskrivning av hur man ska gå tillväga för att lösa detta problem. Beskrivningen ska ha god struktur och vara illustrerad med skisser av problemträdet och datastrukturer. (betyg A)

Hemtalet lämnas in på kurswebbsidan (under Inlämningsuppgifter).