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

Syfte

Syftet med denna obligatoriska upgift är att du skall:

• få prova på att testa och utvärdera implementationer av okända algoritmer.
• öva dig på att analytiskt utvärdera algoritmer.

Notera

Låt dig inte luras av att denna uppgift är teoretisk och saknar implementationsdel. Den här uppgiften beräknas ta lika lång eller kanske längre tid än programmeringsuppgiften OU2. Börja med den så snart du kan (direkt efter första föreläsningen om komplexitetsanalys). Speciellt viktigt är att läsa igenom del 2 av uppgiften innan gruppövning 2 och börja med att försöka lösa den innan dess.

Problemspecifikation

Den obligatoriska upgiften består av två delar. I den första delen skall tre implementationer av olika algoritmer (det är INTE sorteringsalgoritmer!) utvärderas. Det som gör det hela lite spännande är att endast den exekverbara binären kommer att vara tillgänglig (du kan alltså inte lista ut vilka algoritmer det rör sig om genom att kolla på källkoden). Den information du får ut från programmet är hur lång tid algoritmen tog på sig för ett givet antal element n.

Den andra delen består i att på ett analytiskt sätt komma fram till tidskomplexiteter för ett antal sorteringsalgoritmer. Du kommer att få arbeta med denna del på gruppövning 2 (men det krävs en hel del eget arbete också!). Observera att närvaro på gruppövningen underlättar ert arbete avsevärt!

Del 1- Experimentell komplexitetsanalys

Den exekverbara binären finns att ladda ner i versioner för SunOS, Linux, MacOS och Windows.

• SunOS (körs på peppar och de flesta av institutionens övriga icke-windows datorer).
• Linux (körs bl a på datorerna i MA426).
• MacOS X
• Windows

Spara den binär du vill använda på ett lämpligt ställe (t ex edu/5DV043/ou4/) och starta den genom att i ett terminalfönster skriva algorithms_solaris/algorithms_linux/algorithms_osx/algorithms_win (beroende på vilken du laddat ner). Progammet tar tre kommandoradsparametrar och har en syntax som följer:

algorithms -{1,2,3} num_elements [num_loops=1]

Om du kör på SunOS, Linux eller MacOS X så måste kommandot föregås av ./, dvs kommandosyntaxen ser ut så här:

./algorithms -{1,2,3} num_elements [num_loops=1]

Den första parametern är -1/-2/-3 och anger vilken algoritm som ska användas. Den andra ska vara ett heltal (> 0) som anger hur många element algoritmen ska testas för. Den sista är valfri och anger hur många gånger en algoritm av given storlek ska köras. Om ett tal större än ett anges kommer tiden som ges som utdata vara medeltiden det tog för en algoritm att köras.

Som exempel skulle algorithms -1 1000 10 kunna ge utdatat

1000    0.1684

Den första siffran är antalet element som ingår i testet och den andra är den tid (i sekunder) den givna algoritmen i genomsnitt (över 10 körningar) tog att köra.

Använd ett bra intervall (minsta storlek/största storlek) för respektive algoritm. Ett bra intervall väljer man med tanke på den dator man kör på. Den nedre gränsen bör innehålla så pass många tal att det tar längre tid att köra algoritmen än vad datorn klarar av att mäta (allt från en 1/1000s till 1/18s). Den övre gränsen för intervallet måste väljas så att det tar minst 30s för algoritmen. Det är inte säkert att 30 s räcker för att få en fullständig bild. Se till att inte dra slutsatser för fort.

Är man i nedre delen av testintervallet så att körningarna går väldigt fort bör man upprepa körningarna genom att sätta den sista parametern till sortprogrammet så att körningarna åtminstone tar några sekunder. Om programmet inte fungerar tillfredsställande på den plattform som du valt så räcker det inte med att skriva att det inte fungerade. Du måste isåfall testa att köra det på en annan platform. Kontakta handledarna om du får problem.

När du tror att du vet vilken komplexitet algoritmen har måste du motivera det. Motivera ditt val av komplexitet genom att visa att de mätvärden du har begränsas av ditt komplexitetsförslag, dvs beräkna c så att f(n) <= c*g(n) där f(n) är dina tider och g(n) är ditt förslag på komplexitet. I diagrammen du ska göra ska dels f(n) synas men också c*g(n) och gärna också en linje för en lägre komplexitet så att man ser att f(n) ligger mellan dessa två komplexiteter.

Del 2 - Asymptotisk komplexitetsanalys

Syftet med denna del av den obligatoriska uppgiften är att ni ska bestämma tidskomplexiteten för ett antal sorteringsalgoritmer. Detta ska göras genom att räkna antalet primitiva operationer som varje utförs i varje algoritm. Utifrån detta ska sedan definitionen av Ordo användas för att ge uttryck för varje algoritms tidskomplexitet. Konstanterna c och n0 skall bestämmas.

OBS! Visserligen får ni samarbeta under gruppövning 2 med denna del men arbetet ska renskrivas och sammanfogas med del ett samt lämnas in enskilt.

Uppgiften

Del2

Redovisning

Den obligatoriska upgiften ska redovisas i en koncis rapport.

• För den första delen av uppgiften ska rapporten innehålla diagram som visar hur lång tid de tre algoritmerna tar på sig för olika stora listor och en analys av dessa diagram (vilken tidskomplexitet kan algoritmerna tänkas ha och varför? Motivering är viktigt!. Det räcker inte att säga att det "syns i grafen". Glöm ej tala om hur många tester du gjorde för varje storlek på listan.
• För den andra delen ska rapporten innehålla en utförlig analys av de algoritmer som finns i del 2 och som du arbetade med delvis på gruppövningen, med fullständigt redovisade räkningar. Du måste också ange vad du ansett vara en primitiv operation och i detalj beskriva hur exempelvis en for-loop analyseras.
• Det ska finnas ett avsnitt med rubriken "Reflektioner": Berätta om ditt arbete med den obligatoriska uppgiften. 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?
• Ange alltid referenser till material du använt för att lösa den obligatoriska uppgiften 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 ska vara fristående från uppgiftens specifikation och en student som har samma förkunskaper som du men som inte läser denna kurs ska kunna förstå innehållet i din rapport, vad du gjort och varför.
• Definitionen av ordobegreppet bör finnas med i rapporten och det ska tydligt framgå vilka beräkningar som gjorts.

Den obligatoriska uppgiften ska lösas individuellt och du ska kunna redogöra i detalj för varje del i din lösning.

Rapporten lämnas i facket avsedd för denna kurs senast 7 maj, 12.00.