Behörighetskrav

• 4 hp från kursen CD100A: Imperativ programmering (7,5 hp)
• Utöver de formella förkunskapskraven förutsätts att studenten har kunskaper från kurserna CD102A: Objektorienterad programmering (7,5 hp) och CM103A: Diskret matematik (7,5 hp)

Fördjupningsnivå i förhållande till examensfordringarna

Kursen ingår i examensfordringarna för civilingenjörsexamen i Datateknik.

Innehåll

• Asymptotiska mått för algoritmers tids- och utrymmeskomplexitet.
• Grundläggande datastrukturer såsom array, stack, länkad lista, kö och träd, och deras betydelse för datorprograms prestanda och resursutnyttjande.
• Sökdatastrukturer såsom hashtabeller, sökträd och prioritetsköer.
• Effektiva sorteringsalgoritmer, deras egenskaper och lämplighet beroende på sammanhang.
• Användning av problemlösningstekniker såsom rekursion, söndra och härska, giriga algoritmer och uttömmande sökning.
• Beräkningsbarhet och komplexitetsklasser såsom P och NP

Lärandemål

Kunskap och förståelse

Efter avslutad kurs skall studenten kunna:

1. beskriva arbetssätt och syfte för de algoritmer och datastrukturer som ingår i kursen samt ange deras resurskrav i fråga om tid och utrymme, 
2. redogöra för centrala komplexitetsklasser och beräkningsbarhet,
3. redogöra för komplexitetsbegreppet och dess konsekvenser för algoritmdesign.

Färdighet och förmåga

Efter avslutad kurs skall studenten kunna:

4. analysera och kritiskt utvärdera program och algoritmer med avseende på deras förväntade resursutnyttjande, effektivitet och prestanda,
5. utforma algoritmer och datastrukturer för utveckling av datorprogram med gott resursutnyttjande och god prestanda,
6. välja, applicera, implementera och vid behov modifiera algoritmer och datastrukturer för praktisk utveckling av effektiva datorprogram,
7. använda asymptotiska komplexitetsmått för jämförelse av algoritmer och datastrukturer.

Värderingsförmåga och förhållningssätt

Efter avslutad kurs ska studenten kunna:

8. bedöma vilken exekveringstid och övrigt resursutnyttjande som krävs av ett datorsystem för att lösa givna problem, och om problemen är ohanterliga för stora datamängder.

Arbetsformer

Föreläsningar, laborationer, självstudier och inlämningsuppgifter med handledning.

Bedömningsformer

För godkänt betyg krävs:

• godkänd skriftlig och muntlig redovisning av inlämningsuppgifter (UG, 3,5 hp) (Lärandemål 4-8).
• godkänd skriftlig tentamen (TH, 4 hp) (Lärandemål 1-3, 7, 8)

För samtliga bedömningar ska underlaget vara sådant att individuella prestationer kan särskiljas.

Slutbetyget motsvaras av betyget på den skriftliga tentamen.

Kurslitteratur

• Sedgewick, R. and Wayne, K. (2011) Algorithms (4th edition), Addison Wesley

Kursvärdering

Malmö universitet ger studenter som deltar i eller har avslutat en kurs en möjlighet att framföra sina erfarenheter av och synpunkter på kursen genom en kursvärdering som anordnas av lärosätet. Universitetet sammanställer kursvärderingarna samt informerar om resultaten och eventuella beslut om åtgärder som föranleds av kursvärderingarna. Resultaten ska hållas tillgängliga för studenterna. (HF 1:14).

Övergångsbestämmelser

Om en kurs har upphört att ges eller har genomgått större förändringar ska studenterna, under ett år efter det att förändringen har skett, erbjudas två tillfällen för omprov baserade på den kursplan som gällde vid registreringen.

Övrigt

Om en student har beslut om riktat pedagogiskt stöd, har examinator rätt att ge ett anpassat prov eller låta studenten genomföra prov på ett alternativt sätt.