Datastrukturer för D2 DAT036 - lp 2 2009 Rättelse Ett fel hade smugit sig in i svaret på uppgift 1 (b) i tentamen från december 2008 (länk finns under tentamen). Splayträdet uppfyllde inte egenskapen att vara ett binärt sökträd. Felet har korrigerats. Kursens syfte Kursen handlar om hur man utnyttjar datorns resurser på ett effektivt sätt. Man får lära sig olika metoder att lagra data så att man snabbt kan bearbeta dem. Man får också lära sig att analysera hur pass tidseffektiva program är. Ytterligare ett tema är abstraktion: man lär sig att arbeta med abstrakta datatyper som ger tillgång till metoder/funktioner med ett visst beteende utan att specificera implementeringsdetaljer. Kursen handlar också om hur man implementerar vanligt förekommande abstrakta datatyper, datastrukturer och algoritmer i ett i objektorienterat språk (Java) och i ett funktionellt språk (Haskell). Efter genomgången kurs ska man kunna implementera abstrakta datatyper som Java-gränssnitt och datastrukturer som Java-klasser; implementera abstrakta datatyper som Haskell-moduler och datastrukturer som Haskell-typer; känna till hur de algoritmer som är kopplade till datastrukturerna kan implementeras effektivt; uppskatta resurskrav för olika datastrukturer och algoritmer och därmed göra motiverade val mellan tillgängliga alternativ.

Kurslitteratur

Schema

Föreläsningar: tisdagar 13.15 - 15.00 i HC1 och torsdagar 13.15 - 15.00 i HC2. Första tillfälle 27 oktober.

Övningar: tisdagar 15.15 - 17.00 och fredagar 13.15 - 15.00 i EC (efternamn A-J, AB), ED (efternamn K-, SB). Första tillfälle 3 november. Fr o m fredag den 20 november kommer de båda övningsgrupper att slås samman till en grupp, som träffas i EC. Arnar Birgisson leder tisdagsövningarna och Staffan Björensjö leder fredagsövningarna under resten av läsperioden.

Labhandledning: måndagar (AB), torsdagar (AL) och fredagar (SB) 15.15 - 17.00 i sal 3507a,b. Första tillfälle 2 november. Under vecka 6 och 7 kommer det dessutom att vara labhandledning tisdagar 10-12 i 5352 (AL) och fredagar 10-12 i 6225a,b (vecka 6 SB, vecka 7 AB).

Det är ingen föreläsning och övning tisdagen den 10 november (internationella dagen).

Preliminär plan för föreläsningar och övningar

Om du klickar på ett visst datum kan du titta på bilderna från föreläsningen den dagen.
Lösningsförslag finns till vissa uppgifter i boken. Förslagen distribueras av författarna och är av varierande kvalitet.

Laborationer

Laboration	Genomgång på övning	Sista inlämningsdag	Sista godkännandedag
1. Binärsökning	3 nov	13 nov	20 nov
2. Aktiehandel	12 nov	24 nov	4 dec
3. Reseplanering	24 nov	8 dec	15 dec

Anvisningar för labrapportering (på engelska). Följ dessa!

Laborationerna utgör ett obligatoriskt moment. För att godkännas på detta moment måste varje laboration rapporteras före ovan angivna sista inlämningsdag och godkännas före ovan angivna sista godkännandedag! De som ej är klara med laborationerna i tid kommer att hänvisas till nästa kurstillfälle hösten 2010.

Kod ska struktureras, indenteras, kommenteras och testas väl. Laboration som inte uppfyller dessa kriterier returneras utan att rättas. Använd gärna JavaDoc! Grupp som får retur förväntas göra en rejäl revision av sin lab innan den lämnas in igen. Tänk på att antalet returmöjligheter innan sista godkännandedag är begränsat!

Varje grupp ska lösa sin uppgift själv - skilj på samarbete och fusk! Skydda er kod! Om någon kopierar den, blir både kopierande och kopierad grupp underkända. Allvarliga fall anmäls till disciplinnämnden.

Animeringar

• Hashtabeller
• Sökträd, skipplistor och heapar
• DFS- och BFS-sökning
• Kortaste vägen
• Minsta uppspännande träd
• Transitiva höljet
• Sortering