Datastrukturer och algoritmer 7,5 hp (5DV043), våren 2009

Syfte

Syftet med denna obligatoriska uppgift är att du ska

• börja få en förståelse varför man använder sig av abstrakta datatyper,
• analysera för- och nackdelar med olika implementationer av den abstrakta datatypen Tabell,
• öva dig i att hantera dynamiska strukturer,
• öva dig i skriftlig presentation.

Uppgift

Du ska implementera den abstrakta datatypen tabell på tre olika sätt. Du ska även analysera dina implementationers för- och nackdelar och redovisa både implemenation och analys i en skriven rapport.

OBS!

• Uppgiften ska utföras enskilt.
  
  
• Vi vill att all kod för de olika implementationerna av tabellerna skall vara skrivna av er, så inlämnade uppgifter som bygger på att det finns en ArrayList/LinkedList/Vector/annan klass i Javas API i bakgrunden är inte godkända.

  Javas API kan dock vara till hjälp en hel del under utvecklingen av er lösning: det kan ju vara bra, om man inte är helt säker på att den egna implementationen av en länkad lista (exempelvis) är helt korrekt, att provköra med de som finns i Java. Men, när du lämnar in koden måste du alltså ha tagit bort alla spår av klasserna som finns i Javas API.

• Tänk på effektiviteten när du implementerar! Ett exempel på detta: Att kolla om en tabell är tom ska ske på konstant tid. Med andra ord ska du inte loopa igenom tabellen för att se om den är tom eftersom tiden då beror på tabellens storlek.

Implementation

Gränsytan på den tabell du ska implementera finns i sin helhet i filen Table.java. Dina tabeller ska alltså implementera interfacet Table!

I fallen med dynamiska listor nedan ska ni först implementera den abstrakta datypen Lista och sedan implementera tabellen med hjälp av denna lista. Gränsytan till ADT Lista finns i filen List.java och Gränsytan till positionen finns i Pos.java.

Tabell konstruerad med hjälp av en statisk Lista

Utnyttja den inbyggda array-konstruktionen i språket ("hakparenteserna" [ ] med andra ord...). Bygg sedan tabellen utifrån det så att storleken är statisk och rymmer max tusen element. Se dock till att koden är skriven på ett snyggt sätt så att man bara behöver ändra på ett ställe i koden för att kunna kompilera en tabell med större storlek. Kalla den nya abstrakta datatypen för ArrayTable.

Tabell konstruerad med hjälp en dynamisk lista

I denna variant ska du konstruera en tabell med hjälp av en dynamisk lista. Du får själv bestämma om listan ska vara enkel- eller dubbellänkad. Kalla den nya abstrakta datatypen för ListTable. Listan ska implementeras som en separat abstrakt datatyp.

Tabell konstruerad som Move To Front-lista

Även i denna variant ska du konstruera en tabell med hjälp av en dynamisk struktur, med det tillägget att när du läser av ett element i tabellen (LookUp) ska du flytta detta element först i listan. Det gör listan till en Move To Front-lista. Kalla den nya abstrakta datatypen för MTFTable. Listan ska implementeras som en separat abstrakt datatyp.

Frivillig extra uppgift

Implementera tabellen som en hash-tabell eller som ett sorterat träd istället för MTF-lista. Notera att denna extra uppgift kan innehålla teori som vi inte hunnit gå igenom på kursen ännu. Det ingår i uppgiften att själv ta fram den information som behövs för att genomföra den.

Analys

I dokumenationen av din obligatoriska uppgift ska du diskutera de olika implementationerna av tabell som du gjort. Analysen ska ske i löpande text och inte i fråga-svar form. Minimikravet för analysen är att den ska besvara följande frågor:

• När du testkörde ditt program, vilken tabelltyp var snabbast?
• Vilka fördelar kan du se med de olika tabelltyperna? Nackdelar?
• Välj ut en av fördelarna och fundera över varför denna fördel inte finns hos de övriga typerna.
• Finns det några förändringar du skulle vilja göra i den gränsyta du implementerat?
• Vilka skillnader kan du se mellan en statisk och en dynamisk implementation?
• Hur hanterar dina implementationer fallet när man försöker ta bort något i tabellen som inte finns där?
• Hur hanteras dubbletter bland nycklarna i tabellen?

Berätta om ditt arbete med laborationen. Vad var lätt, vad var svårt, hur löste du de problem som dök upp? Har du synpunkter på själva uppgiften?

Testprogrammet

Syftet med denna obligatoriska uppgift är inte att du ska spendera tid på att skriva ett testprogram, därför får du använda dig av ett färdigt testprogram (se nedan för länkar). För att testprogrammet ska fungera måste du följa den givna gränsytan för tabell. Om din implementation klarar alla tester kommer testprogrammet skriva ut fyra olika mätvärden för hur lång tid det tog att göra insättningar, uppslagningar och raderingar i tabellen. Märk att testprogrammet innehåller numeriska konstanter som du kan (och antagligen bör) ändra för att få användbara mätvärden. Resultaten från testprogrammet kommer att behövas för att kunna utföra analysen.

För att använda testprogrammet så kompilerar du TableTest.java som finns här tillsammans med de hjälpklasser som den behöver. Du kör testprogrammet antingen genom att skriva java TableTest klassnamn på kommandoraden (där klassnamn är namnet på den tabellklass du vill testa. Utelämnas klassnamnet testas alla tre tabellimplementationer), eller så kan du köra det via den IDE du använder.

OBS!

För att undvika onödiga "O:n", observera att din lösning inte automatiskt är godkänd för att den klarar av det testprogram som finns på den här sidan. Tänk över om det finns ytterligare fall som borde testas och koden ska också uppfylla kraven på god programmeringsmetodik (indentering, kommentering, lämpliga variabelnam, bra modularisering etc).

Redovisning

Lämna in en rapport som innehåller följande:

• Ett försättsblad med ditt namn, användarnamn, kursens namn, handledarnas namn och laborationens nummer.
• En bra beskrivning av hur alla intressanta delar av dina tabeller fungerar. Ett exempel kan vara att beskriva hur du genomförde move-to-front eller vilken typ av lista du valt och varför.
• Analysen enligt det som beskrivs ovan. Denna del är det viktigaste i hela rapporten och bör därför vara utförlig. Svaren på frågorna ska ske i löpande text och själva frågorna ska inte upprepas i rapporten.
• Välstrukturerad och kommenterad kod (skriven i ett icke-proportionellt typsnitt, t.ex. courier)
• Det är mycket viktigt att koden finns tillgänglig under ditt_användarnamn/edu/5DV043/ou2/ och inte i någon annan katalog. Observera att t.ex. DoA är skillt från doa på det filsystem där du sparar era filer..

Den obligatoriska uppgiften ska lösas individuellt och du ska kunna redogöra i detalj för varje del i din lösning. Ange referenser till de material du använt för att lösa laborationen i din rapport. För exempel på hur man skriver referenser se http://www.ub.umu.se/global/biblref.htm eller http://www.cs.umu.se/education/examina/InternetCite/citera.htm

Rapporten lämnas i kursens lablåda som finns ett par meter från Coca-cola automaten på plan 4 i MIT-huset och är märkt med kursens namn och kurskod (5DV043) senast 20 April, 12.00. Kom ihåg reglerna för obligatoriska uppgifter!

Tips

• Vet du inte vad interface i java är eller hur man implementerar ett sådant, gå tillbaka till kursbok, föreläsningar och läsanvisningar från förkunskapskursen (5DV081/5DV090) och repetera!

• Allmänt för alla tabeller gäller att de ska ha en konstruktor som inte tar några parametrar.
  
  
• Får ni en någon enstakavarning om "Unchecked or unsafe operations" så kan ni ignorera den. Mer information om Generics finns på denna sida och kommer även att diskuteras på kursen Applikationsprogrammering i Java.