DAT102 Algoritmer og datastrukturer

Emnebeskrivelse for studieåret 2018/2019

Innhold og oppbygning

Faget skal gi studentene forståelse av begrepet abstrakte datatyper (ADT) og de operasjoner som hører med til disse. Gjennom teori og praktiske programmeringseksempler gis en grundig innføring i definisjon, bruk og implementering av grunnleggende klassiske datastrukturer og algoritmer. Det blir også lagt vekt på de ulike ADT-ers bruksområder og effektiviteten av de implementerte algoritmene.

Innhold

Abstrakte datatyper (ADT): grensesnitt og implementasjon; tid og plasseffektivitet og teknikker til analyse av effektivitet; teknikker til systematisk test; unntakshåndtering; samlinger av elementer; referanser og kjeda strukturer; stabel; kø og lister; rekursjon som programmeringsteknikk; søkning og sortering; trestrukturer; prioritetskø, haug; hash-teknikker; mengder og ordbøker; grafer; bruk av ADT til algoritmisk problemløsning.

Læringsutbytte

Etter å ha fullført dette emnet skal studenten kunne:

Kunnskaper

  • Beskrive kontrakten (interface) til standard abstrakte datatyper
  • Forklare oppbygging og virkemåte av grunnleggende datastrukturer
  • Forklare prinsipper og begreper som ligger til grunn for analyse av effektivitet

Ferdigheter

  • Implementere abstrakte datatyper og datastrukturer
  • Vurdere effektivitet for algoritmer og operasjoner på datastrukturer
  • Anvende systematiske teknikker til enhetstesting av klasser

Generell kompetanse

  • Arbeide i grupper
  • Anvende standard datastrukturer til algoritmisk problemløsning

Krav til forkunnskaper

Ingen

Anbefalte forkunnskaper

DAT100 Grunnleggende programmering og MAT101 Diskret matematikk og datamaskiner, eller tilsvarende emner.

Undervisnings- og læringsformer

 Forelesninger, øvingsoppgaver og prosjektarbeid i grupper.

Arbeidskrav

5 obligatoriske øvinger må være gjennomført til fastsatte frister og godkjent før eksamen kan avlegges. Aktuelle former kan være innleveringer og presentasjoner.

Godkjente øvinger gir også adgang til eventuell utsatt eksamen påfølgende semester. Ved utsatt og ny eksamen neste gang faget undervises, må nye øvinger leveres

Vurderingsform

Skriftlig skoleeksamen, 4 timer.

Tid og sted for eksamen blir opplyst på Studentweb og digitalt eksamenssystem.

Eksamen vil bli avholdt på digitalt eksamenssystem. Studentene må medbringe egen datamaskin. Programvaren som er nødvendig for å gjennomføre eksamen må være installert og testet før eksamensdagen.

Karakterskala A-F, der F tilsvarer ikke bestått.

Dersom det er 20 eller færre oppmeldt til eksamen, kan det bli arrangert muntlig eksamen.

Hjelpemidler ved eksamen

Ingen.

Faglig overlapping

  • TOD063 (1) - Datastrukturer og algoritmer - Reduksjon: 10 studiepoeng