* Dagens Plan
 - Generelle tips til eksamen
 - Kort oppsummering av kursets tema

 - Q/A 

 
 - Peer Instructions
 
 
* Generelle tips
  #+BEGIN_NOTES
  her er litt notater for ? hjelpe meg ? huske
  #+END_NOTES
  #+ATTR_REVEAL: :frag roll-in
  - Du blir bed?mt etter hva du /viser/ at du kan
  - Du m? /begrunne/ svar
  - Du m? ikke /skrive/ av b?ker eller foiler
  - Gj?r de /enkleste/ oppgavene f?rst
  - Les oppgavene n?ye!
    

* Tema vi har sett p? i kurset s? langt
  - Kompleksitet
  - Bin?re s?ketr?r
  - Maps/Hashing
  - Rekursjon/Kombinatorisk s?k
  - Prioritetsk?/Heap
  - Grafer
  - Sortering
  - Boyer Moore
  - Huffman encoding

* Kompleksitet
  - Klasser og BigO
  - Hvordan klassifisere en generell algoritme
  - Opptelling av antall operasjoner

* Bin?re s?ketr?r

  - Ordningskrav
  - Typisk bruk
  - Kompleksitet
  - Problemer
    + Balansering
    + R?d-sorte tr?r
   
  - B-tr?r

* Maps/Hashing
  - N?kkel $\rightarrow$ Verdi mapping
  - Hashfunksjoner 
    + Hva gj?r en hashfunksjon bra/d?rlig?
    + Hva blir brukt som n?kler?
  - ?pne hashtabeller 
  - Lukkede hashtabeller
  - Kollisjonsh?ndtering / Re-hashing
    
* Rekursjon/Kombinatoriske s?k

  - Rekursjon
    + Funksjoner som kaller seg selv
    + Rekursive strukturer (bin?rtre, grafer ... )
  - Kombinatoriske s?k
    + Rekursiv funksjon som genererer permutasjoner
    + I kurset brukt for ? illustrere filtrering/avskj?ring

* Prioritetsk?/Heap
  - Sorter jobber etter prioritet
  - Bin?rheap: komplett bin?rtre med ordningskrav
    + Foreldre har h?yere prioritet enn barn
    + Rot-node vil ha h?yest prioritet
    + Array blir brukt til ? lagre treet
  - Bin?rheap kan brukes til sortering

* Grafer
  - Konsept: Noder, Kanter, Rettet, Urettet, Vektet
  - Representasjon
  - Grafalgoritmer
    + Topologisk sortering
    + Korteste vei (vektet/uvektet) (Dijkstra, Bellman-Ford)
    + Minimale spenntre (Kruskal/Prim)
    + Biconnectivity
    + Strongly connected components  
      
 * Sortering
   - To hovedtyper sorteringsalgoritmer
   - Sammenligningsbaserte
     + Bubble-sort 
     + Quick-sort
     + Heap-sort
     + Insertion-sort
     + Shell-sort
     + Merge-sort
   - Verdibaserte
     + Bucket-sort
     + Radix-sort
      
* Boyer Moore
  - Rask substring algoritme
  - Matcher baklengs, tar utgangspunkt i byte verdier (256)
  - Preprosessering av n?l
  - bad-character-shift
    + Beregn avstand til neste gang n?l er p? linje med h?ystakk 
  - good-suffix-shift
    +  Bruk antall match f?r missmatch til ? finne skip-avstand

* Huffman enkoding
  - Komprimering basert p? frekvens av bokstaver
  - Bokstaver blir til bitsekvenser av forskjellig lengde
    + Lag et frekvenstre (bokstav : antall)
    + Legg bokstavene p? en Heap
    + Sl? sammen basert p? frekvens
    + Lag bitsekvenser for hver l?vnode (bokstav)
    + Skriv ny fil der bokstav byttes ut med bitsekvens

* Dynamisk programmering
  - Brukes p? optimaliseringsproblemer
    + Enkle delproblemer
    + Delproblem-optimalisering
    + Overlapp av delproblemer
  - Floyds algoritme


* Q/A
* Lykke til p? eksamen og takk for semesteret! :-)