Visa version
Version skapad av Linda Kann 2013-09-20 21:00
Visa
< föregående
Jämför
< föregående
Hemtal 2
Hemtal 2
Hashning
Läs avsnittet Hashing i kapitlet Sorting and Searching i kursboken
Besvara sedan följande frågor:
- I Spotify finns ca femton miljoner låtar. Hur stor ska hashtabellen vara? (betyg E)
- Föreslå en hashfunktion för ett låtnamn, t ex "The Axoltl song". (betyg E)
- Rita och beskriv hur krockhantering med krocklistor fungerar. (betyg E)
- Skulle man kunna använda ett bloomfilter för Spotifys låtar? Motivera ditt svar! (betyg C)
- 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:
- Använder man en stack eller en kö i djupetförstsökning? Förklara varför. (betyg E)
- Vilken komplexitet har breddenförstsökning? Definiera ingående variabler. (betyg E)
- Ä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)
-
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)
8 1 6 3 5 7 4 9 2
Hemtalet lämnas in på kurswebbsidan (under Inlämningsuppgifter).