Datastrukturer och algoritmer

Kursen är obligatorisk inom Sofware Engineering and Management, kandidatprogram (N1SOF) samt Datavetenskap, kandidatprogram (N1COS).

Kursen kan också ingå i följande program:

1. Applied Data Science masterprogram (N2ADS)
2. Matematiska vetenskaper, masterprogram (N2MAT)
3. Matematikprogrammet (N1MAT)

Kursen ges även som fristående kurs vid Göteborgs Universitet.

För att vara behörig till kursen ska studenten ha :

• Genomgångna kurser om minst 15 hp i programmering, varav minst 10 hp avklarade (t.ex. DIT009 Grundläggande programmering, 7,5 hp, och DIT044 Objektorienterad programmering, 7,5 hp, eller motsvarande).

• Avklarade kurser om minst 7,5 hp i diskret matematik eller algebra (t.ex. DIT008 Diskret matematik, eller motsvarande).

Följande kunskapsnivå i Engelska krävs: Engelska 6/Engelska nivå 2 eller motsvarande från ett erkänt internationellt test, t.ex. TOEFL, IELTS.

Datastrukturer och algoritmer utgör grundläggande byggstenar i nästan alla programvaror. Kunskaper och färdigheter i dataabstraktion, datastrukturer och algoritmer är nödvändiga vid konstruktion, användning och underhåll av förändringsbara, återanvändbara, korrekta och effektiva programkomponenter.

Kursen ger kunskaper och färdigheter i konstruktion och användning av algoritmer och datastrukturer, introduktion till algoritmanalys och dataabstraktion, samt insikter i fördelarna med dataabstraktion vid programutveckling.

Följande ämnen täcks av kursen:

• abstrakta datatyper
• datastrukturer och algoritmer, med fokus på imperativa och objektorienterade programmeringsspråk
• vanliga datastrukturer, såsom fält (arrayer), länkade listor, obalanserade och balanserade träd, heapar och hashtabeller
• hur dessa kan användas för att implementera abstrakta datatyper, såsom stackar, köer, prioritetsköer, avbildningar, mängder och grafer
• standardalgoritmer för dessa datastrukturer, inklusive deras resurskrav
• söknings- och sorteringsalgoritmer
• att använda olika bibliotek för datastrukturer och algoritmer
• grundläggande komplexitetsanalys av datastrukturer och algoritmer

Efter godkänd kurs ska studenten kunna:

Kunskap och förståelse

• redogöra för grundläggande abstrakta datatyper och datastrukturer, bland annat listor, köer, hashtabeller, träd och grafer
• redogöra för några av de algoritmer som används för att effektivt hantera dessa datastrukturer, och förklara varför de är korrekta

Färdigheter och förmåga

• tillämpa grundläggande abstrakta datatyper och datastrukturer, samt algoritmer relaterade till dessa
• implementera och använda abstrakta datatyper som gränssnitt, och datastrukturer som klasser, i ett objektorienterat programmeringsspråk
• läsa, specificera och beskriva algoritmer, på en högre abstraktionsnivå än programkod

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

• analysera effektivitet hos grundläggande algoritmer och datastrukturer
• göra välgrundade val mellan olika datastrukturer och algoritmer för olika tillämpningar

Undervisningen består av föreläsningar, övningar och grupparbete med handledning.

Undervisningsspråk: engelska

Kursen examineras genom en skritlig salstentamen (4,5 hp), och inlämningsuppgifter som genomförs i grupp (3.0 hp).

Om student som underkänts två gånger på samma examinerande moment önskar byte av examinator inför nästa examinationstillfälle, bör sådan begäran inlämnas skriftligt till institutionen och ska bifallas om det inte finns särskilda skäl däremot (HF 6 kap 22§).

Om student fått rekommendation från Göteborgs universitet om särskilt pedagogiskt stöd kan examinator, i det fall det är förenligt med kursens mål och förutsatt att inte orimliga resurser krävs, besluta att ge studenten en anpassad examination eller alternativ examinationsform.

I det fall en kurs har upphört eller genomgått större förändringar ska student garanteras minst tre examinationstillfällen (inklusive ordinarie examinationstillfälle) under en tid av minst ett år, dock som längst två år efter det att kursen upphört/förändrats. Vad avser praktik och verksamhetsförlagd utbildning gäller motsvarande, men med begränsning till endast ett ytterligare examinationstillfälle.

Delkurser

1. Skriftlig salstentamen, 4,5 hp
   Betygsskala: Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3) och Underkänd (U)
2. Inlämningsuppgifter, 3 hp
   Betygsskala: Godkänd (G) och Underkänd (U)

På kursen ges något av betygen Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3) och Underkänd (U). Det slutliga betyget bestäms utifrån betyget på den skrifltiga tentamen.

Kursen utvärderas genom möten, både under och efter kursen, mellan lärare och studentrepresentanter. Ett anonymt skriftligt frågeformulär skickas även ut till studenterna efter kursens slut. Resultaten av utvärderingarna används för att förbättra kursinnehållet och som indikation till vilka delar som skulle kunna läggas till, tas bort, förbättras eller ändras.

Kursen kan samläsas med Chalmers.

Kursen ersätter kursen DIT182, 7,5 hp. Den här kursen kan inte ingå i en examen som innehåller DIT182. Den kan inte heller ingå i en examen som bygger på en annan examen där DIT182 ingår.