Datastrukturer och algoritmer

Kursen är obligatorisk inom N1SOF Sofware Engineering and Management kandidatprogram.

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

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

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

• 15 hp programmering (t.ex. DIT009 Fundamentals of programming, 7,5 hp, och DIT044 Object-oriented programming, 7,5 hp, eller motsvarande)
• 7,5 hp diskret matematik (t.ex. DIT008 Discrete mathematics, DIT984 Discrete mathematics for computer scientists, delkursen Introductory algebra i MMG200 Mathematics 1, eller motsvarande).

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 (Written hall examination), 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 (Assignments), 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.

Resultatet och eventuella förändringar i kursens upplägg ska förmedlas både till de studenter som genomförde värderingen och till de studenter som ska påbörja kursen.

Kursen kan samläsas med Chalmers.

Kurslitteratur kommer att publiceras senast 8 veckor innan kursstart.

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.