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.

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 man lär sig beskriva resultatet av en sådan analys med hjälp av Ordo-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 avslutad 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,
• (FSR 4) implementera lösningen i form av ett program i programspråket C,
• (FSR 5) tillämpa filhantering och dynamisk minnesallokering,
• (FSR 6) använda sig av grundläggande problemlösningsstrategier,
• (FSR 7) experimentellt och teoretiskt undersöka en mjukvaras tids- och minneskomplexitet, samt redogöra för och dokumentera utfallet enligt givna riktlinjer,
• (FSR 8) visa att en komponent i ett program fungerar korrekt med hjälp av testning,
• (FSR 9) använda sig av en debugger för att hitta fel i program,
• (FSR 10) visa förståelse för hur struktur-, tids- och minnesaspekter påverkar kvalitet hos program.

Behörighetskrav

För behörighet krävs en kurs (ca 7,5 hp) i programmering i programspråket C.

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
Examinator kan besluta om avsteg från kursplanens examinationsform. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov. Examinationsformen anpassas inom ramen för kursplanens förväntade studieresultat. Student som har behov av en anpassad examination ska senast 10 dagar innan examinationen begära anpassning hos Institutionen för datavetenskap. Examinator beslutar om anpassad examination som sedan meddelas studenten.

Övriga föreskrifter

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.