Data structures and algorithms

Official syllabus

This is a mixture of the course syllabi for the courses DIT183, DAT038, DAT495, DAT525, and TDA417.

---

English version

Entry requirements

To be eligible for this course, students must have successfully completed:

• 15 hec in programming, of which at least 10 hec completed
• 7.5 hec in discrete mathematics, completed

Content

Data structures and algorithms are fundamental building blocks in almost all software products. Knowledge and skills in data abstraction, data structures, and algorithms are important in the construction, use, and maintenance of adaptable, reusable, correct, and efficient program components.

The course gives knowledge and skills in the construction and use of algorithms and data structures, an introduction to various techniques for the analysis of algorithms, and insights in the advantages of using data abstraction in program development.

The following topics are covered by the course:

• abstract data types
• data structures and algorithms focusing on imperative och object-oriented languages
• common data structures such as arrays, linked lists, unbalanced and balanced trees, heaps, and hash tables
• how these can be used to implement abstract data types such as stacks, queues, priority queues, maps, sets, and graphs
• standard algorithms for these data structures, including their resource demands
• searching and sorting algorithms
• using different libraries for data structures and algorithms
• basic complexity analysis of data structures and algorithms

Leaning objectives

On successful completion of the course the student will be able to:

Knowledge and understanding

• explain basic abstract data types and data structures, including lists, queues, hash tables, trees, and graphs
• explain some of the algorithms used to manipulate and query these data structures in an efficient way, and explain why they are correct

Competence and skills

• apply basic abstract data types and data structures, and algorithms related to these
• implement and use abstract data types as interfaces, and data structures as classes, in an object-oriented programming language
• read, specify, and describe algorithms, at a higher level of abstraction than code

Judgement and approach

• analyse the efficiency of basic algorithms and data structures
• make informed choices between different data structures and algorithms for different applications

Examination format

The course is examined by an individual written exam (4.5 hec), and assignments carried out in groups (3.0 hec). [In the course DAT525 the assignments give 1.5 hp]

The grading scale comprises: 5, 4, 3, and Fail (U). The final grade is given based on the grade for the written exam.

---

Swedish version

Behörighetskrav

För att vara behörig till kursen ska studenten ha avklarat:

• 15 hp programmering, varav minst 10 hp avklarade
• 7,5 hp diskret matematik, avklarade

Innehåll

Datastrukturer och algoritmer utgör grundläggande byggstenar i nästan alla programvaror. Kunskaper och färdigheter i dataabstraktion, datastrukturer och algoritmer är nödvändiga vid konstruktion, användning och underhåll av förändringsbara, återanvändbara, korrekta och effektiva programkomponenter.

Kursen ger kunskaper och färdigheter i konstruktion och användning av algoritmer och datastrukturer, introduktion till algoritmanalys och dataabstraktion, samt insikter i fördelarna med dataabstraktion vid programutveckling.

Följande ämnen täcks av kursen:

• abstrakta datatyper
• datastrukturer och algoritmer, med fokus på imperativa och objektorienterade programmeringsspråk
• vanliga datastrukturer, såsom fält (arrayer), länkade listor, obalanserade och balanserade träd, heapar och hashtabeller
• hur dessa kan användas för att implementera abstrakta datatyper, såsom stackar, köer, prioritetsköer, avbildningar, mängder och grafer
• standardalgoritmer för dessa datastrukturer, inklusive deras resurskrav
• söknings- och sorteringsalgoritmer
• att använda olika bibliotek för datastrukturer och algoritmer
• grundläggande komplexitetsanalys av datastrukturer och algoritmer

Lärandemål

Efter godkänd kurs ska studenten kunna:

Kunskap och förståelse

• redogöra för grundläggande abstrakta datatyper och datastrukturer, bland annat listor, köer, hashtabeller, träd och grafer
• redogöra för några av de algoritmer som används för att effektivt hantera dessa datastrukturer, och förklara varför de är korrekta

Färdigheter och förmåga

• tillämpa grundläggande abstrakta datatyper och datastrukturer, samt algoritmer relaterade till dessa
• implementera och använda abstrakta datatyper som gränssnitt, och datastrukturer som klasser, i ett objektorienterat programmeringsspråk
• läsa, specificera och beskriva algoritmer, på en högre abstraktionsnivå än programkod

Värderingsförmåga och förhållningssätt

• analysera effektivitet hos grundläggande algoritmer och datastrukturer
• göra välgrundade val mellan olika datastrukturer och algoritmer för olika tillämpningar

Examinationsformer

Kursen examineras genom en skritlig salstentamen (4,5 hp), och inlämningsuppgifter som genomförs i grupp (3.0 hp). [I kursen DAT525 ger inlämningsuppgifterna 1.5 hp]

På kursen ges något av betygen 5, 4, 3, och Underkänd (U). Det slutliga betyget bestäms utifrån betyget på den skriftliga tentamen.