Forelesningsplan

Her finner du en plan over hva som skal foregå i de nærmeste forelesningene.

Fra og med mandag 9. januar:

• Mandag 09:15 - 11:00, D1-057
• Torsdag 10:15 - 12:00, D1-052
• Torsdag 10:15 - 12:00, D1-052 (Øving)

Jeg regner læreboka som støttelitteratur. I de tilfellene det vil være særlig nyttig å konsultere læreboka, vil jeg referere til spesifikke kapitler i oversikten over forelesningene.

Gjennomgåtte temaer

Java

• Pakker, primitive typer (int, char etc.), referanser
• Løkker
• Tabeller
• Klasser: Arv, Interface, Generics

Datastrukturer

• Definisjon
• Lineære, hierarkiske og nettverksstrukturer
• Lister
• Tabellbaserte lister
• Lenkede lister
• Kø (FIFO), Stack (LIFO)
• Binære trær
• Binære søketrær
• AVL trær
• Komplett binærtre
• Hash tabell
• Prioritetskø
• Max- og Min-Heap
• Hash tabell
• Nettverk: matrise
• Nettverk: Noder og kanter

Algoritmer

• Definisjon
• Pseudokode
• Iterativ løsning av Hanoi's tårn
• Søking, innsetting og fjerning av elementer i lister
• Binærsøk
• Innsettingssorterting, utvalgssortering
• Pseudokode
• Rekursjon
• Effektivitet, algoritmeanalyse, Store O, Big Oh
• Flettesorterting (Mergesort)
• QuickSort
• Syntax sjekking med stack
• Konvertering fra infix til postfix
• Evaluering av postfix-uttrykk
• Søking i binære søketrær
• Beregne høyden i et binærtre
• Innsetting og sletting i binære søketrær
• AVL-balansering
• Permutasjoner
• Hashing
• Sette inn og ta ut i max(min)heap
• Bygge heap
• Heapsort
• Dybdesøk
• Breddesøk
• Korteste vei: Dijkstra

Anvendelser

• Google Maps
• Hanoi's tårn
• Palindromsjekking
• Syntaxsjekking
• Dronningproblemet (8-queens, N-queens)

Diverse

• Summen av de N første heltall: (N²+N)/2
• Her er er et eksempel på løsning av en typisk Dijkstra oppgave (v08-5): Ferdigbehandlede noder er streket under. Oppdaterte noder (der veien er blir kortere enn før) er uthevet med fet skrift.

  	a	b	c	d	e	Kommentar
  Init	a:0	-:∞	-:∞	-:∞	-:∞	Avstanden fra a til a settes til 0. De andre avstandene settes til uendelig, og deres "via"-noden settes til "-"
  1	a:0	a:13	a:4	a:7		Vi velger noden med kortest avstandsverdi, dvs. a. Dernest oppdaterer vi avstanden til a ("via a") i alle nabonodene som ikke er ferdigbehandlet, dvs,. b, c, og d. Noden a er etter dette ferdig behandlet, og vi markerer med å sette strek under den.
  2			a:4		c:11	Vi velger node c (kortest vei). For alle naboene til c som ikke er ferdigbehandlet, dvs e, sjekker vi om veien til a er kortere via c enn den til nå korteste veien, og det er den, og vi oppdaterer.
  3				a:7	d:9	Vi velger node d (korteste vei til nå). For alle noboer som ikke er ferdigbehanldet (e), sjekker vi om veien er kortere via d enn via c, og det er den, og vi oppdaterer e.
  4		e:10			d:9	Blant nodene som ikke er ferdighbehandlet, har e har nå kortest vei. Den har en nabo som ikke er ferdig, b, og veien til a vi e er 9, som er mindre enn 13, og vi oppdaterer.
  5		e:10				Det er nå kun en node som ikke er ferdigbehandlet, b, og den har jo da ingen naboer som ikke er ferdigbehandlet, og vi er framme!