Datastrukturer och algoritmer (C), 7,5 hp

Innehåll

Kursen behandlar grundläggande abstrakta datatyper, grundläggande algoritmer, komplexitetsanalys, tillämpningsexempel och olika problemlösningsansatser. Under kursen används programspråket C. Studenter som saknar tidigare erfarenhet av C ansvarar själva för att tillägna sig de grundläggande kunskaper i språket som krävs för att kunna följa kursen.

Grundläggande abstrakta datatyper som behandlas är bland andra lista, stack, kö, träd, mängd, graf och tabell. Datatypernas informella och formella specifikationer, generella egenskaper och användningsområden liksom olika implementationsmöjligheter och deras specifika egenskaper behandlas. Vidare behandlas grundläggande algoritmer förknippade med olika abstrakta datatyper, deras komplexitet och karakteristiska egenskaper för typiska problem (till exempel sökning, sortering och traversering). Komplexitetsanalys av algoritmer introduceras och studenten lär sig beskriva resultatet av en sådan analys med hjälp av asymptotisk notation. Grundläggande problemlösningsstrategier behandlas, till exempel divide and conquer, brute force, greedy och dynamisk programmering.

Teoridelarna i kursen tillämpas genom problemlösning (att konstruera algoritmer) och programmering (att överföra algoritmer till källkod i ett programspråk). Färdigheter som testning, felsökning och dokumentation övas. Komplexitet hos enkla algoritmer undersöks.

Kursen är uppdelad i två moduler.

Modul 1: Teori, 4,5 hp

Modul 2: Problemlösning, 3,0 hp

Förväntade studieresultat

Kunskap och förståelse
Efter avklarad kurs ska studenten kunna:

• (FSR 1) förklara grundläggande begrepp relaterade till datastrukturer och algoritmer,
• (FSR 2) beskriva vanliga abstrakta datatyper och algoritmer,

Färdighet och förmåga
Efter avslutad kurs ska studenten kunna:

• (FSR 3) formulera lösningar till enkla problem i form av algoritmer inklusive att identifiera och använda lämpliga datatyper och problemlösningsstrategier,
• (FSR 4) implementera lösningen i form av ett program i programspråket C,
• (FSR 5) experimentellt och teoretiskt undersöka en mjukvaras tids- och minneskomplexitet, samt redogöra för och dokumentera utfallet enligt givna riktlinjer,
• (FSR 6) konstruera och genomföra tester för att öka tilltron till att en komponent i ett program fungerar korrekt,

Värderingsförmåga och förhållningssätt
Efter avslutad kurs ska studenten kunna:

• (FSR 7) visa förståelse för hur struktur-, tids- och minnesaspekter påverkar kvalitet hos program.

Behörighetskrav

Minst 7,5 hp programmering.

Undervisningens upplägg

Undervisningen bedrivs i form av föreläsningar, arbete i datorlabb och övningar i mindre grupper. Utöver schemalagda aktiviteter krävs även individuellt arbete med materialet.

Examination

Modul 1, Teori, examineras genom en skriftlig salstentamen. På modulen sätts något av betygen Med beröm godkänd (5), Icke utan beröm godkänd (4), Godkänd (3), Underkänd (U).

Modul 2, Problemlösning, examineras genom skriftliga inlämningsuppgifter. På modulen sätts något av betygen Underkänd (U), Godkänd (G).

På kursen som helhet sätts något av betygen Med beröm godkänd (5), Icke utan beröm godkänd (4), Godkänd (3), Underkänd (U). När båda modulerna är godkända sätts betyget på kursen som helhet till samma som betyget på Modul 1, Teori.

Anpassad examination

För student som har beslut om rekommenderat stöd på grund av funktionsnedsättning kan Examinator besluta om avsteg från kursplanens examinationsform. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov och kursens förväntade studieresultat. För mer information se Handläggningsordning för stöd till studenter med funktionsnedsättning samt Regel för betyg och examination.

Övergångsbestämmelser

Om kursplanen har upphört att gälla eller kursen slutat erbjudas garanteras en student som någon gång registrerats på kursen minst tre provtillfällen (inklusive ordinarie provtillfälle) enligt denna kursplan under en tid av maximalt två år från det att kursplanen upphört att gälla eller kursen slutat erbjudas.