Algoritmer og datastrukturer

Dette emnet skal dekke følgende tema:

1. Teknikker og algoritmer: Abstrakte datatyper. Rekursjon. Sortering. Søking. Hashing. Algoritmer for korteste vei, Maksimum flyt. Datakompresjon.Grådige algoritmer. Dynamisk programmering.
2. Datastrukturer: Tabeller/array. Lister. Kø. Stakk. Trær. Grafer.
3. Teori om kompleksitet og asymptotisk notasjon. Tids- og plassforbruk

Kunnskap

Kandidaten skal:

• være kjent med, kunne forklare og anvende en del standard algoritmer for bl.a. sortering, søking og grafteori.
• kunne beskrive og forklare ulike datastrukturer (arrayer/tabeller, lenkede lister, køer, stakker, trær og grafer).
• forstå rekursiv tankegang/metode ved problemløsning og programmering.
• kunne sammenligne algoritmers kompleksitet, og slik velge den mest bærekraftige løsningen
• kunne beskrive kompleksitetsklasser og np-kompletthet

Ferdigheter

Kandidaten skal:

• kunne benytte en rekke kjente algoritmer for å løse praktiske programmeringsproblemer effektivt.
• kunne skrive programkoden som løser avanserte og kompliserte problemstillinger (D)
• kunne håndtere avanserte datastrukturer (med særlig vekt på trær og grafer)

Generell kompetanse

Kandidaten skal:

• kunne kombinere standardalgoritmer til større programenheter

Forelesninger og øvingsoppgaver