Informationsteknik – Datastrukturer och algoritmer

Efter avslutad kurs skall den studerande känna till och kunna använda vanligen förekommande datastrukturer, kunna analysera kod och algoritmer med tanke på körtidskomplexitet samt känna till olika sorteringsalgoritmer. För att uppfylla målet skall den studerande kunna:
– redogöra för skillnader i olika kategorier av körtidskomplexitet
– redogöra för rekursionsbegreppet
– räkna ut ”big-Oh” för givna kodavsnitt och beskrivna algoritmer
– redogöra för och använda sig av de vanligaste abstrakta datatyperna
– redogöra för och använda sig av de vanligaste sorteringsalgoritmerna

Algoritmer och algoritmanalys
Rekursion
Abstrakta datatyper
Listor, stackar, köer, prioritetsköer
Träd, binära sökträd och balanserade sökträd (Red-Black trees)
Hashning
Sökning, sortering

Obligatorisk närvaro vid redovisning av inlämningsuppgift.
Närvaro vid laborationer alternativt motsvarande uppgift som inlämningsuppgift.

Compulsory attendance at assignment presentation.
Attendance at laborations, alternatively corresponding task as assignment.

1-5 (för betygssättning)

Informationsteknik

Utbildningsprogrammet för informationsteknik

Bedömningskriterier – tillfredsställande insikter (1-2)
Förstå sig på begreppet och kunna rangordna vanliga komplexitetsmått samt härleda dessa från enkla programkonstruktioner.
Förstå begreppet datastruktur och algoritm.

Bedömningskriterier – goda insikter (3-4)
Kunna härleda komplexitet från mera komplexa program och algoritmer, samt utföra mätningar experimentellt.
Förstå kopplingen datastruktur-algoritm, hur valet av den ena delvis eller helt bestämmer valet av den andra, samt hur kombinationen av de två inverkar på tids- och rumskomplexitet.

Bedömningskriterier – berömliga insikter (5)
Förstå sig på hur man väljer bland olika lösningar och implementerar optimal lösning med beaktande av föreliggande problem.
Kunna välja bland ett brett sortiment av datastrukturer och algoritmer. Kunna hitta och använda implementationer av dessa i standard bibliotek, samt ha goda färdigheter i att själv implementera dessa vid behov, på ett effektivt och välstrukturerat sätt.

Grading – Satisfactory (1-2)
Understanding of run time complexity and knowledge of analysis of algorithms.
Understanding of different data structures and algorithms.

Grading – Good (3-4)
Be able to analyze code and algorithms considering run time complexity and know how to do experimental tests of code.
Understanding of differences in complexity depending on which data structure versus algorithm is applied

Grading – Excellent (5)
Good understanding of how to choose and implement the most optimal solution with respect to underlying problem.
Good skills in implementing different data structures and using different algorithms, such that the produced code is efficient and clear.

Thareja, R. (2014). Data Structures using C. (2nd ed.). Oxford University Press, 560 p.

Övrigt material enligt lärarens anvisningar.

Thareja, R. (2014). Data Structures using C. (2nd ed.). Oxford University Press, 560 p.

Additional material according to the lecturer’s instructions.

Programmering 1.

Godkänt vitsord noteras i studiekort. 1-5 (vid validering används vitsordet Godkänd).

Passed grade, 1-5, will be noted in the study card. (in validation Passed is applied).

Föreläsningar, laborationer, inlämningsuppgifter och tent.

Lectures, laborations and assignment.