Hemtal 3
A) Problemträd
Läs om
breddenförstsökning (Breadth First Search) och
djupetförstsökning (Depth First Search) i kursboken.
Titta sedan på bilspelet:
rush hour
(det är samma spel i flera implementationer - välj vilken du vill).
- Rita av startpositionen för bilarna och numrera dom.
- Hur många olika sätt finns det att flytta någon bil i startläget? Skriv upp alla möjligheter (t ex "Flytta bil 1 en ruta uppåt")
- När du själv spelar bilspelet - är det breddenförstsökning eller djupetförstsökning du använder? Motivera ditt svar!
- Vad har breddenförstsökning för komplexitet?
- Vad har djupetförstsökning för komplexitet?
B) Hashning
Läs om
hashning (Hashing) i kursboken.
- Anta att vi har en hashtabell med 1000 platser.
Vilken av följande hashfunktioner är bäst? Motivera ditt svar!
- h(x) = x % 999
- h(x) = x % 1000
- h(x) = x % 1001
- Om vi stoppar in 500 värden i hashtabellen ovan, vad blir då fyllnadsgraden (load factor) λ?
- Vad är en krock (collision)?
- Vad är en perfekt hashfunktion?
- Beskriv tre olika sätt att hantera krockar.
Hemtalet tas med till övning 3 (13 september) och rättas där!
Den som gjort uppgiften ska skriva sitt namn
och personnummer överst till höger på alla blad.
Den som rättar ska skriva sitt namn och personnummer
längst ner till vänster på första bladet.
