Föreläsning 14 - Tentaåterlämning och -genomgång
Kursenkät
Fyll i kursenkäten! Du hittar den på kurshemsidan, här:
http://www.csc.kth.se/utbildning/kth/kurser/2D1320/tilda07/kursenkat/
Laborationerna
Kom ihåg att sista redovisningsdag för laborationerna är den 14/11!
Man måste bli godkänd på laborationsdelen (dvs redovisa alla sju labbarna)
för att bli godkänd på kursen. Använd de kommande laborationspassen 1/11, 7/11, 9/11 och 14/11.
Tentaresultatet
Tentan har 100 poäng. Så här gick det:
Gränser |
Betyg |
Antal |
<47 |
F |
8 |
47-49 |
Fx |
2 |
50-59 |
E |
20 |
60-69 |
D |
28 |
70-79 |
C |
26 |
80-89 |
B |
22 |
90-110 |
A |
27 |
Totalt var ni 135 som skrev tentan, varav två kom från andra kursomgångar.
Antalet godkända var alltså 125, 82%
Fick du 47-49 poäng? Då har du också fått en individuell
kompletteringsuppgift utdelad tillsammans med tentan.
Den ska redovisas för Linda på labbtillfället den 7 november.
I kurspm står följande:
"Klagomål på rättning av tentan lämnas till kursledaren inom tre veckor
från det att tentaresultatet anslagits. Observera att du inte bör ta med
dig tentan från expeditionen eller tentaåterlämningen om du vill klaga
på rättningen. Kolla tentan på expeditionen, skriv ned dina kommentarer
och kontakta sedan kursledaren."
Läs igenom nedanstående innan du klagar!
Tentagenomgång
Här följer några kommentarer om tentan och lösningarna som inkommit.
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 - ni är datalogiskt allmännbildade!
Uppgift 4: Binärträd
Rekursion brukar vara knepigt, men den här uppgiften har ni lyckats bra med.
I d-uppgiften syns att ni 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.
Algoritmen ger 8p.
- 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
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.