Oppgavesett 9 - Hashing / Dronninger

Oppgavene blir tema på øvingen fredag 30. mars. Innleveringen skal bestå av en pdf-fil med korte kommentarer og dokumentasjon (utskrifter etc.). Legg også ved godt dokumenterte java filer. Alt pakkes i en zipfil, med navn assignment09-*.zip der * er etternavnene til gruppemedlemmene. Javafilene skal tilhøre en pakke med navn package assignment09.

Fristen for innlevering er tirsdag 27.mars 09:00.

Oppgave 1

Anta at vi har en hashtabell på 8 elementer. Vi bruker enkel, lineær prøving ved kollisjoner. Elementene som skal settes inn har en tekststreng som nøkkel. Hashfunksjonen som skal brukes er A(s) % n, der A(s) er summen av ascii-verdiene til de enkelte tegnene i strengen s, og n er 8.

Sett inn følgende nøkler: 1) ANNE, 2) PER, 3) NINA, 4) ANNI, 5) ALI, 6) KAREN, 7) OLA, og 8) SIV. Tegn opp tabellen etter hver innsetting.

Oppgave 2: N-Queens

Her skal du ta utgangspunkt i Queens.java fra forelesningen.

A

Implementer metoden boolean print(int[] perm), som skriver ut et sjakkbrett til System.out med plassering av dronningene representert ved perm. Dokumenter at den virker.

B

Implementer metoden boolean legal(int[] perm), som sjekker om dette er lovlig plassering av dronningene (dvs. at ingen av dronningene står på samme diagonal. Beskriv metoden, og dokumenter at den virker.

C

Implementer ferdig koden slik at den finner alle lovlig plasseringer for en gitt størrelse på brettet. Dokumenter at den virker.

D

Bruk koden til å lage et plott som viser antallet lovlige løsninger for økende brettstørrelser.

*E

Man kan effektivisere koden ved å ikke generere alle mulige permutasjoner. Dette gjøres ved å avskjære genereringen av en permutasjon hvis den på et punkt gir en ulovlig løsning. Beskriv denne teknikken nærmere, og implementer den. Bruk den til å lage et plott der y-aksen viser antall rekursive kall, og der x-aksen viser størrelsene på brettene.