Kursöversikt

Hoppa fram till i dag

Kursen ges av institutionen för Data- och informationsteknik

Lärare och studentrepresentanter

Samtliga finns presenterade på kontaktsidan.

Kursansvariga

Lärarassistenter

Patrick Franz, Yazan Ghafir, Hannes Gustafsson, Marcus Karegren & Adam Olivegren.

Studentrepresentanter

TIDAL: Jonatan Boman Karinen, Johan Fridlund

TKIEK: Jonathan Hjärtström, Klara Pilhall, Ella Wallinder

Kursens syfte

Algoritmer och datastrukturer utgör fundamentala byggstenar i de flesta moderna programvaror. Kunskaper och färdigheter i tekniker för konstruktion och analys av algoritmer är viktiga verktyg vid produktion av korrekta och effektiva program. Förtrogenhet med begreppen dataabstraktion och datastruktur är nödvändig vid konstruktion, användning och underhåll av förändringsbara och återanvändbara programkomponenter.

Kursen skall ge kunskaper och färdigheter i konstruktion och användning av algoritmer och datastrukturer, introduktion till olika tekniker för analys av algoritmer, samt insikter i fördelarna med dataabstraktion vid programutveckling.

Lärandemål (efter fullgjord kurs ska studenten kunna)

  • Använda olika algoritmtekniker som problemlösningsverktyg vid programkonstruktion.
  • Göra enkla analyser av algoritmers och datastrukturers resurskrav.
  • Använda olika datastrukturer och känna till viktiga tillämpningar.
  • Använda standardbibliotek för datastrukturer och algoritmer.
  • Implementera egna datastrukturer i ett objektorienterat språk.

Innehåll

I kursen används Java som programmeringsspråk.

  • Algoritmtekniker: Iterativa och rekursiva algoritmer, induktionsbevis, divide and conquer, backtracking, dynamisk programmering.
  • Analys av algoritmers och datastrukturers resurskrav med avseende på beräkningstid och minnesbehov. Asymptotisk komplexitet, genomsnittlig komplexitet och värsta-fall-komplexitet.
  • Linjär- och binärsökning.
  • Olika sorteringsalgoritmer och deras egenskaper.
  • Begreppen abstrakt datatyp och datastruktur.
  • Datastrukturer: Vektorer, strängar, stackar, köer, listor, träd, binära sökträd, hashtabeller, prioritetsköer, grafer, mängder. Vanliga användningsområden. Typiska egenskaper och tidskomplexitet för strukturernas operationer.
  • Standardiserade algoritmer och klasser för datastrukturer.
  • Implementering av datastrukturer.

Organisation

Undervisningen sker i form av föreläsningar och handledda övningar. Övningarna består dels i att analysera och modifiera givna program, dels i att konstruera egna program. Vissa av uppgifterna är obligatoriska och redovisas med skriftlig dokumentation. Stor vikt läggs vid de studerandes egen aktivitet i kunskapsinhämtandet.

Kurslitteratur

Robert Sedgewick and Kevin Wayne (2011). Algorithms, 4th edition. Boken finns tillgänglig via Chalmers store.

Boken har en mycket bra websida med ytterligare information, programkod, övningar, etc.: https://algs4.cs.princeton.edu/

Andra intressanta böcker och websiter finns på resurssidan.

Examination inklusive obligatoriska moment

Obligatoriska laborationer i form av inlämningsuppgifter (redovisas via Fire) och skriftlig tentamen. Slutbetyg i skala 3-5 ges efter godkända laborationer och baseras på tentamen.

Schema

TimeEdit

Länk till kursplanen i Studieportalen Studieplan

Kurssammanfattning:

Datum Information Sista inlämningsdatum