Läs- och studieanvisningar

Kapitel 1

1. Kapitel 1.1 - 1.3: De grundläggande matematiska begreppen exponenter, logaritmer och serier skall du kunna sedan tidigare. Se till att du minns vad det hela handlar om. Speciellt kommer logaritmbegreppet att vara flitigt använt i kursen. 1.2.4, 1.2.5 och 1.3 skall du förstå ordentligt.

2. Kapitel 1.6 - 1.7: Dessa avsnitt bör du titta igenom för din egen skull för att fräscha upp dina Java-kunskaper.

Kapitel 2

Avsnitt 2.1 är mycket viktigt, du skall förstå begreppen Ordo, Omega och Theta ordentligt. Resten av kapitlet bör du läsa igenom en gång.

Kapitel 3

Listor, stackar och köer. Hela kapitlet är viktigt, utom första halvan av 3.2.6 (Polynomial ADT) och 3.2.7. Andra halvan av 3.2.6, radix sort behandlas i samband med sorteringsalgoritmer.

Om trädsturkturer och sökträd i kapitel 4, 10 och 12

• 4.1 och 4.2: Viktiga.

• 4.3: Mycket viktigt, se till att du dessutom verkligen förstår den Java-kod som finns beskriven för de grundläggande operationerna i ett binärt sökträd, och hur de fungerar rekursivt.

• 4.4, AVL-träd: Du behöbver endast känna till det balanseringskriterium som används för AVL-träd: I varje nod skall skillnaden mellan de två underträdens höjd vara högst 1. Du skall också veta att balanseringsalgoritmerna använder sig av rotationer, men inte exakt hur.

• 4.5, Splay-träd: Inte heller här behöver du kunna detaljer. Du skall känna till huvudprincipen: noder som varit aktiva genom insätting, uttag eller sökning, dras med till roten tillsammans med sina närmaste grannar. På så vis kommer de noder som besöks ofta att hamna nära roten. Splay-träd har en god förmåga att anpassa sin struktur efter hur elementen i trädet besöks.

• 4.6 och 4.7: Viktiga. Du skall kunna hur uppdateringar i ett B-träd går till.

• 12.4, AA-träd: Mycket viktigt. Du skall förstå koden ordentligt. Du skall också kunna balanseringskriteriet:
  • Noderna är indelade i nivåer (levels). Nivå 1 är längst ner.
  • Längs varje väg (path) ner i trädet finns minst en och högst två noder per nivå.
  • Om två noder är på samma nivå längs en väg, är den ena högerbarn till den andra.

  Följande faktum följer ur definitinen av AA-träd:

  1. På översta nivån finns minst en nod, på nästa nivå minst två, sedan minst fyra osv. Alltså är antalet nivåer högst log n.
  2. Eftersom den längsta vägen ner i trädet kan ha högst två noder per nivå, är den längsta vägen, och därmed trädets höjd, högst 2 log n.
  AA-träd uppdateras genoom två operationer, skew och split. Båda använder sig av rotationer. Iden är att, efter insättning eller uttag, göra en skew och en split på varje nivå uppåt i trädet. Därefter är man klar.

• 12.5, Randomiserade sökträd (Treaps): Mycket viktigt. Du skall förstå koden, definitionerna, algoritmerna.
  Den grundlägande iden är att trädet, oavsett i vilken ordning element sätts in och tas ut, alltid skall se ut som om elementen vore insatta i slumpmässig ordning. Detta ordnas genom att varje nod när den skapas tilldelas en sluimpmässig prioritet. Trädet hålls sedan arrangerat så att en förälder alltid har lägre prioritet än sina barn.
  • Vid insättning läggs en ny nod till längst ner i trädet. Noden tilldelas en slumpmässig prioritet. Sedan roteras noden uppåt i trädet tills prioritetsvillkoret är uppfyllt.
  • Vid uttag letas först den aktuella noden upp. Sedan roteras den neråt i trädet. Vid varje rotation låter man det barn som har lägst prioritet ersätta den nod som skall ut. När noden slutligen nått trädets botten, kan den tas bort.

• 10.4.2, skip-listor: Du skall känna till grundiden.

Kapitel 5: hashkodning

Hela kapitel 5, utom 5.4.2, är viktigt.

Du skall kunna grundläggande begrepp från föreläsningsbilderna, som finns på referensmaterial-sidan. Du skal också kunna databaslaborationen noga, En fråga om den kan mycket väl komma på tentamen.

Kapitel 6: Prioritetsköer

Kapitel 6.1 - 6.3 är mycket viktiga, kapitel 6.4 läser du igenom.

Du skall vara väl förtrogen med hur man representerar en heap som ett binärt träd i en vektor. Du skall också känna till hur man gör, insert, deleteMin, decreaseKey och buildHeap. Du skall kunna förklara varför insert, deleteMin och decreaseKey tar O(log n) tid, och varför buildHeap tar O(n) tid.

Kapitel 7: Sorteringsalgoritmer

• 7.1 och 7.2: Viktiga, du skall känna till hur insertion sort fungerar och varför komplexiteten är O(n^2).

• 7.5, Heapsort: Mycket viktigt. Du skall kunna algoritmen, kunna visa et komplett exempel hur den sorterar en vektor. du skalö kunna visa att värstafalls-komplexiteten är O(n log n).
  Iden bakom heapsort:
  1. Bygg en max-heap, dvs en heap med det största elementet överst. Detta steg tar O(n) tid.
  2. Låt heapen krympa genom att ta ut elementen ett och ett. Efterhand som heapen krymper, placeras de uttagna eleenten längst bak i vektorn. Varje uttag tar O(log n) tid.
  3. När heapen är helt tom, är vektorn sorterad.

• 7.6, Mergesort: Mycket viktigt. Du skall kunna algoritmen, kunna visa ett komplett exempel hur den sorterar en lista av element. Du skall kunna visa att värstafalls-komplexitetiten är O(n log n).
  Iden bakom mergesort:
  1. Dela upp listan med element i två halvor.
  2. Sortera verja halva (rekursivt) med mergesort.
  3. Sam-sortera de två halvorna till en sorterad lista.
  På varje rekursiv nivå görs det mesta av arbetet i det tredje steget, samsorteringen. Samsorteringen tar linjär tid i längden på de två listorna. Eftersom vi har totalt n element, kommer den totala tiden på varje nivå att vara O(n). Antalet rekursiva nivåer är log n, varför den totala tiden är O(n log n) i värsta fall.

• 7.7, Quicksort: Mycket viktigt. Även här skall du kunna algoritmen och kunna visa hur den sorterar en vektor med element. Eftersom pivot-elementet kan väljas på flera olika sätt, skall du åtminstone kunna metoden som kallas median-of-three. Du skall känna till att värstafallskomplexiteten är O(n^2) och medelfallskomplexiteten O(n log n). För medelfallskomplexiteten behöver du inte kunna ge ett bevis, men du skall kunna ge en troliggörande förklaring.
  Iden bakom quicksort:
  1. Välj ett delningselement (pivot).
  2. Dela elementen i två delar, de som är mindre resp störr eän pivot-elementet.
  3. Sortera de två delarna var för sig, rekursivt med quicksort.
  På varje rekursiv nivå görs merparten av arbetet i steg 1. Tiden för att dela upp i två delar är linjär i antalet inblandade element. På varje rekursiv nivå är det totala antalet element n. Om slunmpen inte spelar oss ett spratt, är antalet nivåer O(log n).

  Du skall dessutom kunna den quicksort-likande algoritmen för selection-problemet, dvs hitta det p:te elementet i storleksordning. Du skall kunna troliggöra att den förväntade exekveringstiden är O(n).

• 7.8, Informationsteoretisk undre gräns för sorteringsproblement (under förutsättning att man använder sig av jämförelser): Mycket viktigt. Du skal kunna ge beviset.

• 7.9, bucket sort: Mycket viktigt, se även avsnittet om radix sort från kapitel 3.2.6.

  Iden bakom bucket sort är enklast att beskriva om vi sorterar tal. Antag att vi sorterar n tal som alla ligger i intervallet 0 - max. Vi använder oss av en vektor (array) med n änkade listor. Sedan sorterar vi talen genom att multiplicera varje tal med n/max och låta resultatet (avrundat neråt) ge i vilken lista talet skall placeras. Om vi håller de länkade listoran sorterade, kan vi sedan gå igenom vektorn och samla in alla tal i tur och ordning. Är talen någorlunda jämnt fördelade, kommer varje lista att innehålla O(1) element (utom någon enstaka). Detta innebär att insättningskostnaden per element är O(1). Insamlingen av alla element tar O(n) tid. Hela algoritmen tar under dessa förutsättningar O(n) tid.

  Exempel:
  Vi sorterar talen 1544 3215 120 2222 878 797 3330 981 3114 4674 2980 520 3981 4121 673 250 1990 2016 3876 1771.
  Vi har n = 20 och talen ligger i intervallet 0 - 5000. Detta ger en vektor av längden 20, numrerad 0 - 19. När vi sätter in talen i listorna, skall vi multiplicera varje tal med 20/5000, dvs 1/250. Vi avrundar neråt, vilket ger.
  1544 / 250 = 6
  3125 / 250 = 12
  120 / 250 = 0
  2222 / 250 = 8
  osv. Vektorn med listor blir
  

   0: (intervallet    0 -  249) 120
   1: (intervallet  250 -  499) 250
   2: (intervallet  500 -  749) 520 673
   3: (intervallet  750 -  999) 797 878 981
   4: (intervallet 1000 - 1249)
   5: (intervallet 1250 - 1499)
   6: (intervallet 1500 - 1749) 1544
   7: (intervallet 1750 - 1999) 1771 1990
   8: (intervallet 2000 - 2249) 2016 2222
   9: (intervallet 2250 - 2499) 
  10: (intervallet 2500 - 2749) 
  11: (intervallet 2750 - 2999) 2980
  12: (intervallet 3000 - 3249) 3114 3215
  13: (intervallet 3250 - 3499) 3330
  14: (intervallet 3500 - 3749)
  15: (intervallet 3750 - 3999) 3876 3981
  16: (intervallet 4000 - 4249) 4121
  17: (intervallet 4250 - 4499)
  18: (intervallet 4500 - 4749) 4674
  19: (intervallet 4750 - 4999)
  

  ...och vi kan samla in dem i ordning.

Kapitel 9, Grafer, grafalgoritmer

Avsnitt i läroboken:

• kapitel 9.1 - 9.3.1: Mycket viktigt. Du skall kunna visa hur Dijkstras algoritm fungerar på ett exempel.
  Iden bakom Dijkstras algoritm för att från en nod hitta kortaste vägen til alla andra noder (single source shortest paths):
  • Dela in noderna i två grupper. I gruppen known finns de noder för vilka vi känner den kortaste vägen och i unknown finns resten. För varje nod, även de i unknown, lagrar vi det hittills kortaste kända avståndet (om det finns något). I början är known tom, och vi startar det hela genom att flytta ursprungsnoden till known.
  • Så fort en nod flyttas från unknown till known, gör följande:
    1. Vi kallar noden för p. För alla bågar som går ut från p vet vi att avståndet till ps granne kan vara högst avståndet till p plus längden på bågen från p till grannen; vi kan ju alltid gå via p. Om grannen inte har något som helst känt kortaste avstånd sedan tidigare, eller om grannens bästa kända avstånd är större än det avstånd vi får via p, så låt avståndet via p vara grannens bästa kända avstånd.
    2. Efter att detta är gjort, tar vi den nod i unknown vars kända avstånd är kortast och flyttar noden till known. (Detta kan vi göra eftersom det inte kan finnas någon ännu kortare väg till denna nod.)
  • Flytta på så vis noderna en och en, tills samtliga noder finns i known.
  Tidskomplexiteten hos Dijkstras algoritm uttrycker vi som funktion av antalert noder |V| och antalet bågar |E|. Låt oss anta att noderna i unknown lagras i en prioritetskö efter bästa kända avstånd.
  • Varje nod (utom ursprungsnoden) kommer att plockas ut ur prioritetskön exakt en gång med en deleteMin, vilket tar O(log|V|) tid. total tid för alla noder blir O(|V| log|V|).
  • Varje båge kommer exakt en gång att kontrolleras (se "För alla bågar..." ovan) och kan då ge upphov till att en nod får sitt kända avstånd minskat. Detta i sin tur kan ge upphov till en decreaseKey i prioritetskön med noder, vilket kostar O(log |V|) tid. Totalt ger detta en kostnad som är O(|E| log|V|).
  Summerar vi kostnaderna får vi O(|V| log|V| + |E| log|V|). Om varje nod har minst en inkommande båge, blir detta O(|E| log|V|).

• Övrigt i kapitlet: Du skall känna till begreppen network flow problems och minimum spanning trees.

Kapitel 10.1.2, Huffman-kodning

Viktigt, du skall kunna visa hur Huffman-koder beräknas för en given uppsättnnig tecken. Du skall också förstå hur man använder Huffman-koder för datakompression.