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

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

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

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.

VG, G (för betygssättning)

Informationsteknik

Utbildningsprogrammet för informationsteknik

Godkända laborationer samt skriftlig tentamen.
Godkänd programmeringsinlämning. Studerande som planerar att läsa ekonomiinriktning kan välja att ersätta denna med en dokumentationsinlämning.

Approved laborations, assignment and written exam.
Approved programming assignment. Students who plan to study the ecomomics specialization can select to replace this with a documentation assignment,

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

Övrigt material enligt lärarens anvisningar.

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

Additional material according to the lecturer’s instructions.

Programmering 1.

Godkänt vitsord noteras i studiekort. U, G eller VG (vid validering används vitsordet Godkänd).
Godkänd programmeringsinlämning noteras i studiekortet.

Passed grade will be noted in the study card.
Approved programming assignment will be noted in the study card.

Föreläsningar, laborationer och inlämningsuppgift

Lectures, laborations and assignment.