Datastrukturer, 6 hp (TND004)

Huvudområde

Datateknik, Medieteknik

Utbildningsnivå

Grundnivå

Fördjupningsnivå

G2X

Kursen ges för

• Civilingenjör i elektronikdesign
• Civilingenjör i medieteknik

Förkunskapskrav

OBS! Tillträdeskrav för icke programstudenter omfattar vanligen också tillträdeskrav för programmet och ev. tröskelkrav för progression inom programmet, eller motsvarande.

Rekommenderade förkunskaper

Programmering i C++

Lärandemål

Målet med kursen är att ge studenten redskap att självständigt kunna skapa program som löser praktiska problem med stora mängder data, med hänsyn taget till effektivt utnyttjande av tid och minne. För att bli godkänd på kursen ska studenten ha uppnått följande lärandemål.

• Föreslå specifika datastrukturer för att hantera praktiska problem.
• Att objektivt kunna motivera de val som gjorts gällande datastrukturer och relatera dessa till vetenskapliga resultat inom området.
• Analysera fördelar och nackdelar beträffande effektiviteten för olika datastrukturer som har föreslagits för att lösa ett praktiskt problem.
• Implementera och använda datastrukturer och algoritmer som har behandlats i kursen i olika applikationsprogram.

Kursinnehåll

Algoritmanalys. Rekursion. Listor, stackar och köer.
Träd och trädtraversering. Binära sökträd, trådade träd och balanserade träd.
Hashing och hashtabeller. Prioritetsköer och binära heapar.
Sortering och sökning. Indexerade filer.
Grafer och graftraversering. Fundamentala grafalgoritmer.

Undervisnings- och arbetsformer

Föreläsningar, lektioner, och laborationer.

Examination

UPG1	Frivilliga uppgift	U, G	0 hp
LAB1	Laborationskurs	U, G	3 hp
TEN1	Skriftlig tentamen	U, 3, 4, 5	3 hp

Betygsskala

Fyrgradig skala, LiU, U, 3, 4, 5

Övrig information

Om undervisningsspråk

Undervisningsspråk visas på respektive kurstillfälle på fliken "Översikt".

• Observera att även om undervisningsspråk är svenska kan delar av kursen ges på engelska.
• Om undervisningsspråk är Svenska/Engelska kan kursen i sin helhet ges på engelska vid behov.
• Om undervisningsspråk är Engelska ges kursen i sin helhet på engelska. 

Övrigt

Kursen bedrivs på ett sådant sätt att både mäns och kvinnors erfarenhet och kunskaper synliggörs och utvecklas.

Planering och genomförande av kurs skall utgå från kursplanens formuleringar. Den kursvärdering som ingår i kursen skall därför genomföras med kursplanen som utgångspunkt. 

Institution

Institutionen för teknik och naturvetenskap

Studierektor eller motsvarande

Camilla Forsell

Examinator

Aida Nordman

Kurshemsida och andra länkar

http://weber.itn.liu.se/~aidvi05/courses/14/index.html

Undervisningstid

Preliminär schemalagd tid: 60 h
Rekommenderad självstudietid: 100 h

Kurslitteratur

Data Structure and Algorithm Analysis in C++, Mark Allen Weiss, Addison Wesley, 4th edition, year 2014.