DAT102 Algoritmer og datastrukturer

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øking 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 1, eller tilsvarende emner.

Undervisnings- og læringsformer

Forelesninger, øvingsoppgaver og prosjektarbeid i grupper.

Obligatorisk læringsaktivitet

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.

Vurderingsform

4 timer skriftlig eksamen.

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

Eksamen vil bli avholdt på digitalt eksamenssystem. Studentene må ta med 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.

Hjelpemidler ved eksamen

Ingen.

Mer om hjelpemidler

Faglig overlapping

• TOD063 - Datastrukturer og algoritmer - Reduksjon: 10 studiepoeng