DD1320 Tilda: lösningsskiss (med kommerntarer) till tenta den 24 oktober 2007

Uppgift 1: KMP-automat

a) next-vektorn blev: 010131
Automaten och next-vektorn ger tillsammans 8p (en minuspoäng per fel)
b) Tillstånden som gås igenom: 1234534567 (max 4p, en minuspoäng per fel)
c) Välmotiverat svar ger 2p

Denna uppgift hade de flesta lyckats mycket bra med. Vanligaste felet var att man gjorde en ny automat i b-uppgiften istället för att visa hur den första fungerade.

Uppgift 2: Hashning

Hasha in mangan på två ställen, en gång på titel och en på författare (3p). Med pekare till noderna slösar man inte minnesutrymme (2p). Krockar fixas med krocklistor. Söker man på en författare kan man då gå igenom krocklistan för att hitta alla dennes manga (1p). En bild som visar hur det går till ger 2p.
Om hashtabellens storlek ändras måste modulo-delen av hashningen ändras (2p). Och då måsta de gamla värdena hashas om, annars hittar man dom inte (2p). Exempel: 14%13=1 men 14%26=14

Många har missat att rita en bild, vilket alltså ger två poängs avdrag. Det råder oenighet om vad som ska ligga i hashtabellen, vissa föreslår två olika typer av noder, en för titlar och en för författare (pekare till en manga-nod med all information är bäst).

Uppgift 3: Teori

Varje teorifråga kan ge 4p. Att man visar hur fenomenet fungerar kan ge 2p även om man kommit till fel slutsats.

a) Det går inte att använda krocklistor i ett Bloomfilter. Det är bara True eller False (inte noder med värden) som lagras i tabellen. Många vet hur Bloomfilter fungerar men har inte kläm på krocklistor.
b) Ett Huffmannträd bör inte vara balanserat - komprimeringen bygger på att ofta förekommande tecken har kortare koder än ovanliga och i ett balanserat träd blir koderna lika långa.
c) Både binärsökning i sorterad vektor och sökning i binärträd är O(logn), men binärträdssökningen kan ta längre tid om trädet är obalanserat, O(n) i värsta fall.
d) Om man använder en prioritetskö blir det inte breddenförstsökning (kortaste vägen till lösningen) utan bästaförstsökning (billigaste vägen).
e) I RSA har jag två nycklar - en publik som mina vänner kan använda för att koda meddelanden till mig, och en privat som jag avkodar med.

Genomgående bra resultat på denna uppgift.

Uppgift 4: Binärträd

a) Om vi tar ett ord i taget och sorterar in i binärträdet får vi följande (4p):

            
                                            Netsunari
                                     
                           Kengai                             Sekijoju

              Hokidachi             Moyogi        

      Chokkan       Ishizuke

Enstaka missad nod ger en minuspoäng (det är knepigt med bokstavsordning). Den som först sorterat i bokstavsordning och sedan satt in en nod i taget får också 4p, men andra varianter ger 0p.

b) Utskrift i preorder (roten, vänster delträd, höger delträd) ger: Netsunari Kengai Hokidachi Chokkan Ishizuke Moyogi Sekijoju (4p)
Vissa vet att preorder betyder roten-vänster delträd-höger delträd men tänker inte på att tillämpa det rekursivt, och får bara 1p. Inorder/postorder eller andra varianter ger 0p.
c) Totala antalet noder i trädet är summan av antal noder i vänster delträd och antal noder höger delträd och ett (för roten). Ett tomt träd har noll noder. (6p)
Basfallet ger 1p, rekursiva tanken 5p. Om man glömt antalet för roten ELLER delträden får man minuspoäng, men om man inte nämner antalet alls får man 0p.
d) Ur bilden ska framgå att det är värden som beräknas och returneras, annars 0p.

Rekursion brukar vara knepigt, men den här uppgiften har de flesta lyckats bra med. I d-uppgiften syns att man fattat hur rekursionen fungerar.

Uppgift 5: Algoritm

Läs in alla tecknen i kön.
Upprepa följande n gånger:
- Låt k = m, m-1, m-2, ... 1
- Ta ut k-1 tecken ur kön och lägg sist (ett i taget)
- Ta ut och skriv ut det k:e tecknet
Ta till sist ut ett tecken i taget ur kön och skriv ut det tills kön är tom.

Att visa hur algoritmen fungerar för exemplet ger 4p
Komplexitet: n*(m + m-1 + ... + 1) = n*m*(m+1)/2 = O(n*m*m) ger 4p
O(m*n) ger 2p, inkonsekvent användning av m och n ger -2p

Den här uppgiften borde varit lätt - algoritmen liknar ju den i labb 2! Om man har föreslagit Quicksort, urvalssortering, prioritetskö eller liknande får inga poäng (det är inte fråga om sortering - talen visar bara i vilken ordning tecknen ska läsas). Inte heller den som läser in kolumnvis eller fixar alltihop med en matris får poäng - här gällde det att visa att man kunde göra en algoritm med den givna datastrukturen.

Uppgift 6: Syntax

   sats    ::= if tangent: kanjinr |
		 if tangent: sats |
		 if tangent: kanjinr else: kanjinr |
		 if tangent: kanjinr else: sats |
		 if tangent: sats else: kanjinr |
		 if tangent: sats else: sats |
   tangent ::= A...Z
   kanjinr :: = 1...9999

Syntaxen (10p) Syntax utan if och else kan ge 1p för tangent och 1p för kanjinr -1p för varje miss i en för övrigt korrekt syntax
Datastrukturen syntaxträd (6p) Trädstruktur utan bild ger 2p Här kan hashning ge 2p
Beskrivning (4p) Här behöver man inte alls berätta hur trädet byggs upp, det räcker att man visar vad som händer när tangenter trycks ner.

Den här uppgiften testade inte bara syntax utan även abstraktion. Många hade svårt att generalisera och reducerade problemet till just specialfallet i exemplet.