Informationsteknik – Datastrukturer och algoritmer

Kurskod I161204
Studiepoäng 4
Lärandemål

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

After completing the course, the student shall know and be able to use commonly occurring data structures, be able to analyze code and algorithms considering run time complexity and know different sorting algorithms. To fulfill the goal, the student shall be able to:
– explain differences in different categories of run time complexity
– explain the concept of recursion
– calculate ”big-Oh” for given code sections and described algorithms
– explain and use the most common abstract data types
– explain and use the most common sorting algorithms

Innehåll

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

Algorithms och algorithm analysis
Recursion
Abstract data types
Lists, stacks, queues, priority queues
Trees, binary search trees and balanced search trees (Red-Black trees)
Hashing
Searching, sorting

Närvaro

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.

Vitsordsskala

1-5 (för betygssättning)

Ämnesområde

Informationsteknik

Utbildningsprogram

Utbildningsprogrammet för informationsteknik

Examination

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.

Kurslitteratur och studiematerial

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.

Förkunskaper

Programmering 1.

Dokumentering

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).

Arbetsformer

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

Lectures, laborations and assignment.

Utskriven 29 mars 2024 kl 14:24