ITF20006 Algoritmer og datastrukturer (Vår 2020)

Emnet er tilknyttet følgende studieprogram

Obligatorisk emne i

• bachelorstudiet i informatikk - design og utvikling av IT-systemer.

Valgfritt emne for øvrige.

Anbefalte forkunnskaper

Programmeringskunnskaper tilsvarende emnet Programmering 2.

Matematikkkunnskaper med vekt på grunnleggende reell analyse, spesielt funksjonslære.

Undervisningssemester

Bachelorstudie i ingeniørfag, data (Kull 2018 og 2019): 6.semester (vår)
Bachelorstudie i informatikk - design og utvikling av IT-systemer: 4.semester (vår)

Studentens læringsutbytte etter bestått emne

Kunnskap

Studenten kan

• forklare oppbyggingen og hensikten med lineære datastrukturer (lister, køer, stack), trestrukturer (binærtrær, søketrær, balanserte trær, binærheaper, B-trær), hashtabeller og nettverkstrukturer/grafer

• forstå og forklare effektivitet av algoritmer, med spesiell vekt på asymptotisk analyse

• gjøre rede for virkemåten og effektiviteten til standard algoritmer for lagring, innsetting, søking, sletting, sortering, traversering og backtracking, både som iterative og rekursive varianter

Ferdigheter

Studenten kan

• designe, implementere og anvende datastrukturer for ulike behov

• analysere, designe, implementere og anvende fundamentale og klassiske algoritmer

• bruke både egenutviklede og ferdig tilgjengelige algoritmer og datastrukturer til å løse sammensatte og kompliserte problemer

Generell kompetanse

Studenten

• har innsikt i fundamentale og varige prinsipper innen klassisk informatikk, som vil bestå uavhengig av maskinplattformer og programmeringsspråk

• behersker begreper og terminologi som brukes i vide kretser i informatikken verden over

• kan diskutere i faglige fora og gi råd om bruk av datastrukturer og algoritmer i ulike situasjoner

• kan formidle viktigheten og nødvendigheten av å bruke hensiktsmessige strukturer og effektive algoritmer

Innhold

• Algoritmeanalyse

• Rekursiv programmering

• Sentrale datastrukturer som tabeller, lister, køer, stakker, hashtabeller, søketrær, heap, B-trær og grafer

• Algoritmer for sortering, søking, lagring og rekursjon.

Undervisnings- og læringsformer

Forelesninger og øvingstimer.

Arbeidsomfang

Ca 250 timer.

4 timer forelesning + øving per uke.

Arbeidskrav - vilkår for å avlegge eksamen

Inntil fem oppgaver må gjennomføres og godkjennes.

Arbeidskrav må være godkjent før studenten kan fremstille seg til eksamen.

Eksamen

Skriftlig eksamen

4 timers skriftlig eksamen. Det benyttes bokstavkarakter A-F.

Hjelpemiddel: Alle trykte og skrevne hjelpemidler er tillatt.

Sensorordning

Emneansvarlig sensurerer sammen med ekstern eller intern sensor.

Evaluering av emnet

Dette emnet evalueres på følgende måte:

• Midtsemesterevaluering (obligatorisk)

Den emneansvarlige lager en oppsummering på bakgrunn av studentenes tilbakemeldinger og sine egne erfaringer med emnet. Oppsummeringen behandles av studiekvalitetsutvalget ved avdeling for informasjonsteknologi.

Litteratur

Litteraturlista oppdatert 15.11.2019:

Lewis, John; Chase, Joseph: "Java Software Structures - Designing and Using Data Structures (Fourth Edition)", ISBN-13: 978-0-273-79332-8, ISBN-10: 0-273-79332-2