Uppgift 4 våren 2008

Uppgiften ska lämnas till din övningsledare på övningen den 13,14/2. Glöm inte försättsbladet (pdf) och att alla papper ska häftas samman eller lämnas in i en plastficka.

För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med någon uppgift så finns det som vanligt hjälp att få på labbarna.

Hemuppgift

Läs om träd i avsnitt 2.3 och om hashing i avsnitt 2.5 i algoritmboken.

Skriftlig uppgift

Lös uppgift R-2.2, R-2.3 samt C-2.10.

Beräkna tidskomplexiteten i medelfall för sökning, insättning och borttagning i en

• osorterad vektor,
• sorterad vektor,
• osorterad enkellänkad lista,
• sorterad enkellänkad lista,
• hashtabell (du kan anta att antalet element är lika med hashtabellens storlek).

Presentera lösningen i en tabell med tre rader och fem kolumner. Som vanligt ska du också motivera dina svar.

Implementera följande gränssnitt med hjälp av en hashtabell med "seperate chaining" så som det beskrivs i avsnitt 2.5.5 i algoritmboken.

/**
 * An interface describing the ADT (abstract data type)
 * dictionary. The dictionary cannot contain duplicate
 * strings.
 * 
 * @author Stefan Nilsson
 * @version 2005-01-24
 */
public interface StringDictionary
{ 
    /**
     * Adds the given string to this dictionary.
     * Returns <code>true</code> if the dictionary
     * did not already contain the given string.
     */
    public boolean add(String s);

    /**
     * Removes the given string from this dictionary
     * if it is present. Returns <code>true</code> if
     * the dictionay contained the specified element.
     */
    public boolean remove(String s);

    /**
     * Returns <code>true</code> if the string is
     * in this dictionary.
     */
    public boolean contains(String s);
 }

Hashtabellens storlek (antalet element i vektorn) ska anges när man skapar en ny tabell. Använd gärna din implementation av länkade listor från föregående uppgift och använd gärna metoden hashCode() som finns i alla Javaklasser (den deklareras i java.lang.Object) för att implementera din hashfunktion. Som vanligt ska du skriva och lämna in testkod.