Informationsteknik – Datastrukturer och algoritmer

Efter avslutad kurs skall den studerande känna till och kunna använda vanligt förekommande datastrukturer och algoritmer.
För att uppfylla målet skall den studerande kunna:
– redogöra för och använda sig av sammansatta datatyper och tekniker för dynamisk minneshantering
– redogöra för olika kategorier av körtidskomplexitet
– redogöra för rekursionsbegreppet
– redogöra för och använda sig av vanliga datastrukturer
– redogöra för och använda sig av vanliga söknings- och sorteringsalgoritmer

After completing the course, the student shall know and be able to use commonly occurring data structures and algorithms.
To fulfill the goal, the student shall be able to:
– explain and use composite data types and techniques for dynamic memory management
– explain different categories of run time complexity
– explain the concept of recursion
– explain and use common data structures
– explain and use common algorithms for searching and sorting

Sammansatta datatyper
Dynamisk minneshantering
Algoritmer och algoritmanalys
Rekursion
Listor, stackar, köer
Trädstrukturer
Hashtabeller
Sökning, sortering

Composite data types
Dynamic memory management
Algorithms and algorithm analysis
Recursion
Lists, stacks, queues
Tree structures
Hash tables
Searching, sorting

1-5 (för betygssättning)

Informationsteknik

Utbildningsprogrammet för informationsteknik

Skriftlig tentamen samt godkända inlämningsuppgifter.

Bedömningskriterier – tillfredsställande insikter (1-2)
Kan använda sammansatta datatyper.
Förstår grundprinciperna och tillämpningsområdena för dynamisk minneshantering.
Förstår begreppet komplexitetsmått och kunna rangordna vanliga komplexitetsmått samt härleda dessa från enkla programkonstruktioner.
Kan redogöra för och använda sig av grundläggande datastrukturer och algoritmer.

Bedömningskriterier – goda insikter (3-4)
Kan tillämpa dynamisk minneshantering på ett efffektivt sätt.
Förstår kopplingen datastruktur-algoritm, samt hur kombinationen inverkar på tids- och rumskomplexitet.
Kan implementera grundläggande datastrukturer och algoritmer utgående från pseudokod.

Bedömningskriterier – berömliga insikter (5)
Kan välja mellan olika algoritmer och datastrukturer för att implementera en effektiv lösning med beaktanda av föreliggande problem.
Kan implementera olika datastrukturer och algoritmer så att den producerade koden blir effektiv och tydlig.

Grading – Satisfactory (1-2)
Be able to use composite data types.
Understand the basic principles and application areas of dynamic memory management.
Understand the concept of runtime complexity. Be able to rank common complexity categories and derive these from simple program constructions.
Be able to explain and use basic data structures and algorithms.

Grading – Good (3-4)
Be able to apply dynamic memory management effectively.
Understand the connection between data structures and algorithms, and how the combination affects time and space complexity.
Be able to implement basic data structures and algorithms based on pseudocode.

Grading – Excellent (5)
Be able to choose among different algorithms and data structures to implement an efficient solution considering the problem at hand.
Be able to implement various data structures and algorithms, such that the produced code is efficient and clear.

Kochan, S. G. (2014). Programming in C. (4th ed.). Addison-Wesley. 525 s.
Kubica, J. (2022). Data Structures the Fun Way. No Starch Press. 304 s.

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 och inlämningsuppgifter.

Lectures, laborations and assignments.

Totalt 5sp*26.7h/sp=133h
16h Föreläsningar
18h Gemensamma övningar
22h Grupphandledning
73h Självständigt arbete
4h Tentamen