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 skillnader i abstraktionsnivåer vad gäller datatyper, strukturer och funktioner
– redogöra för olika kategorier av 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 sök/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 differences in level of abstraction for data types, structures and functions
– explain different categories of algorithms
– explain and use the most common abstract data types
– explain and use the most common search/ sorting algorithms

Algoritmer och algoritmanalys
Rekursion
Abstrakta datatyper
Listor, stackar, köer, trädstrukturer
Hashing
Sökning, sortering

Algorithms och algorithm analysis
Recursion
Abstract data types
Lists, stacks, queues, trees
Hashing
Searching, sorting

Obligatorisk närvaro vid laborationer och redovisning av inlämningsuppgifter.

Compulsory attendance at laborations and assignment presentations.

VG, G (för betygssättning)

Informationsteknik

Utbildningsprogrammet för informationsteknik

Godkända laborationer och inlämningar samt skriftlig tentamen.

Approved laborations, assignments and written exam.

Weiss M.A. (1997). Data Structures and Algorithm Analysis in C (2nd ed.). Menlo Park, Calif. : Addison-Wesley. 600 s.

Övrigt material enligt lärarens anvisningar.

Weiss M.A. (1997). Data Structures and Algorithm Analysis in C (2nd ed.) Menlo Park, Calif. : Addison-Wesley. 600 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).

Passed grade will be noted in the study card

Föreläsningar, laborationer och inlämningsuppgifter

Lectures, laborations and assignments.