Datastrukturer och algoritmer

Kurskod: DA252A

Institution:

Datavetenskap

Version:

1

För studenter antagna höst 2014   höst 2013   höst 2012  

Fastställande

Kursen är inrättad 28 februari 2012.
Denna kursplan (version 1) är fastställd 28 februari 2012 av Utbildningsnämnden/kursnämnden för beredning och beslut av kursplaner på Teknik och samhälle.
Kursplanen gäller från 03 september 2012.

Utbildningsnivå

Grundnivå

Kursbeskrivning

Kursen syftar till att studenten utvecklar en fördjupad programmeringserfarenhet. I kursen studerar studenten analys, design och implementation av praktiska och effektiva algoritmer och datastrukturer, vilket syftar till att utveckla en förmåga att lösa problem som ofta uppkommer i en programmerares vardag.

Fördjupning i förhållande till examensfordringarna

Kursen ingår i kandidatexamen i Datavetenskap med inriktning mot systemutveckling på 31-60 poängsnivån.

Förkunskapskrav

Kurser om minst 30 hp i datavetenskap varav minst 7.5 hp i programmering.

Lärandemål

Kunskap och förståelse
Efter genomförd kurs ska studenten:

• visa fördjupad förståelse för egenskaper hos strukturerade och objektorienterade datorprogram
• ha förmåga att beskriva samt uppvisa en fördjupad förståelse av grundläggande och avancerade praktiska algoritmer inom områden såsom grafteori, geometri, strängmatchning och talteori
• ha förmåga att beskriva samt uppvisa en fördjupad förståelse av grundläggande och avancerade datastrukturer

Färdighet och förmåga
Efter genomförd kurs ska studenten:

• kunna använda och självständigt anpassa grundläggande och avancerade praktiska algoritmer och datastrukturer för att lösa samt implementera givna problem korrekt och effektivt
• arbeta effektivt i grupp och självständigt för att lösa givna problem korrekt och effektivt inom givna tidsramar

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

• utifrån en given problemställning självständigt och i grupp kunna analyser problemet samt kritiskt välja lämpligt angreppssätt, algoritm och/eller datastruktur
• kunna utföra en korrekt implementation och kunna resonera kring och kritiskt värdera design- och implementationsval ur olika aspekter såsom prestanda

Formerna för att bedöma studenternas prestationer

Kursen examineras genom en skriftlig tentamen, ett antal obligatoriska inlämningsuppgifter samt ett projektarbete.

Krav för godkänd: Godkänd skriftlig tentamen, godkända inlämningsuppgifter samt godkänd projektuppgift.
Krav för väl godkänd: Väl godkänd på minst 60% av examinationsmomenten som viktas efter hp på momenten.


Innehåll eller kursinnehåll

Kursen innefattar följande:


• algoritmanalys och algoritmkonstruktion: amorterad analys, giriga algoritmer, dynamisk programmering och heuristiska metoder
• rimlighetsbedömningar
• algoritmer: grafalgoritmer, sorteringsalgoritmer, beräkningsgeometri och strängmatchning
• grundläggande och avancerade datastrukturer såsom binära sökträd, hash-tabeller, prioritetsköer och suffixträd

Arbetsformer

Föreläsningar ca 35 timmar, laborationer och seminarium ca 30 timmar, projekthandledning ca 5 timmar, samt självstudietid ca 130 timmar.


Betygsgrader

Underkänd, Godkänd eller Väl godkänd.


Kurslitteratur och övriga läromedel

• Cormen; Leiserson; Rivest & Stein, Introduction to Algorithms, 3rd Edition, MIT Press, 2009, ISBN: 978-0-262-03384-8

Kursvärdering

Alla studenter ges vid slutet av kursen möjlighet att kommentera kursen skriftligt. En sammanställning av resultatet med bemötande av kursansvarig diskuteras med studenter/kursrepresentanter under ett kursvärderingsmöte/programråd. Sammanställningen finns tillgänglig på områdets datornät.