ITF20006 Algoritmer og datastrukturer (Vår 2012)

Emnet er tilknyttet følgende studieprogram

Obligatorisk emne som inngår i:

• bachelorstudiet i informatikk (kull 2010)
• bachelorstudiet i informatikk - design og utvikling av IT-systemer

Valgfritt emne for bachelorstudiet i ingeniørfag, data (kull 2009 og 2010).

Forkunnskapskrav utover opptakskrav

Kunnskaper tilsvarende emnet ITF10609 Objektorientert programmering (10 studiepoeng).

Undervisningssemester

Bachelorstudiet i informatikk: 4. semester (vår) (kull 2010)
Bachelorstudiet i informatikk - design og utvikling av IT-systemer: 4. semester (vår)
Bachelorstudiet i ingeniørfag, data: 4. semester eller 6. semester (vår) (kull 2009 og 2010)

4 timer forelesning + øving pr. uke.

Studentens læringsutbytte etter bestått emne

Kunnskap

Etter avsluttet emne skal studentene kunne

• forklare oppbyggingen og hensikten med lineære datastrukturer (lister, køer), trestrukturer (binærtrær, søketrær, balanserte trær, binærheaper) og nettverkstrukturer
• greie ut om tabellbaserte og lenkede datastrukturer kunne forklare hva det ligger i begrepet "effektivt" i en algoritmisk sammenheng
• gjøre rede for virkemåten og effektiviteten til ulike algoritmer for lagring, innsetting, søking, sletting, sortering, traversering og backtracking, både som iterative og rekursive varianter

Ferdigheter

Etter avsluttet emne skal studentene kunne

• 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

Etter avsluttet emne skal studentene kunne

• føle glede over å ha innsikt i fundamentale og varige prinsipper innen klassisk informatikk, som vil bestå uavhengig av maskinplattformer og programmeringsspråk
• føle trygghet over å beherske begreper og terminologi som brukes i vide kretser i informatikken verden over
• diskutere i faglige fora og gi råd om bruk av datastrukturer og algoritmer i ulike situasjoner
• formidle viktigheten og nødvendigheten av å bruke hensiktsmessige strukturer og effektive algoritmer

Innhold

Rekursive problemer. Gjennomgang av de viktigste datastrukturer som tabeller, lister, køer, stakker, hashtabeller, trær, grafer med tilhørende operasjoner. Algoritmer for sortering, søking, lagring og rekursjon. Programmeringsspråket er Java.

Undervisnings- og læringsformer

Forelesninger og øvingstimer.

Arbeidskrav - vilkår for å avlegge eksamen

• Fire oppgaver må gjennomføres og godkjennes.

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

Eksamen

Skriftlig eksamen
4 timers skriftlig eksamen. Bokstavkarakter A-F.
Hjelpemiddel: Fire A4-ark (åtte sider) med egne notater.

Evaluering av emnet

Dette emnet evalueres på følgende måte:
- Midtsemesterevaluering (frivillig)
- Sluttevaluering (obligatorisk)

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

Litteratur

Litteraturlisten er sist oppdatert 10.12.09

Java software structures. Designing and using data structures, av Lewis og Chase. Tredje utgave.