Lösningsförslag med kommentarer 030308

Tal 1

← ← ← ← ← ← ←
↓ ↑ ↑ ↑ ↑ ↑
o I R A N I R A Q
↑ ← ↓ ← ← ← ↓↑ ← ← ↓


Nextvektorn :
0 1 1 1 0 1 1 4

De flesta har klarat det här talet. En del fel som förekommit:

Tal 2

Det här talet var ganska snårigt men innehöll å andra sidan ingen rekursivitet. Tanken var att det skulle vara ganska enkelt att skriva den amerikanska syntaxen och lite snårigare med den engelska. 
[datum]    ::= [us_datum] | [uk_datum]
[us_datum] ::= [us_month_day]/[year]
[uk_datum] ::= [uk_month_day]/[year]


Året är lika för båda.


[year]       ::= 00 | 01 | 02 | 03 | 04 ... | 99


Månad och dag måste paras ihop. Februari kan
hårdkodas direkt. Amerikanska datumet: 

[us_month_day]::= [us_month31]/[us_day31] | 
                  [us_month30]/[us_day30] |
                  2/[us_day28]
	     
[us_day28]   ::= 1 | 2 | 3 | 4 | 5 ... | 28
[us_day30]   ::= [us_day28] | 29 | 30
[us_day31]   ::= [us_day30] | 31

[us_month31] ::= 1 | 3 | 5 | 7 | 8 | 10 | 12
[us_month30] ::= 4 | 6 | 9 | 11 


Det engelska datumet kan fås på samma sätt med en 
annan definition på månad och dagar.


[uk_month_day]::= [uk_day31]/[uk_month31] | 
                 [uk_day30]/[uk_month30] |
                 [uk_day28]/02

[uk_day28]   ::= 01 | 02 | 03 | 04 | 05 ... | 28
[uk_day30]   ::= [uk_day28] | 29 | 30
[uk_day31]   ::= [uk_day30] | 31

[uk_month31] ::= 01 | 03 | 05 | 07 | 08 | 10 | 12
[uk_month30] ::= 04 | 06 | 09 | 11
Det finns elegantare lösningar. T.ex. är skillnaden mellan uk_day28 och us_day 28 inte så stor utan går att separera ut. Fel som förekommit:

Tal 3

Det här talet knöt an till tal 2. Datum kan representeras på olika sätt. Första delen av talet gällde fördelarna av att ha en abstrakt datatyp för ett datum (3p).

Exempel på metoder: 
interface Datum {
    Datum(int millisekunder);   // Konstruktor
    String getUSDate();         // Accessor
    String getUKDate();         // Accessor
}
Exempelfrågan var egentligen tänkt att gälla enbart för datum men kan misstolkas och har därför rättats snällare (2p). Man kan få 1p avdrag för t.ex.

Tal 4a

MASSA DAMM HOS SADDM
Som de flesta har uppmärksammat har ett A kommit bort i öknen.

Tal 4b

Basfall: Om noden inte har några barn (= löv). Skriv ut värdet i noden.

Rekursivt tanke: Om noden har ett vänsterbarn, anropa rekursivt med vänsterbarnet. Om noden har ett högerbarn, anropa rekursivt med högerbarnet.

Eftersom trädet i det här fallet är ett Huffman träd så är det tillåtet att definera löv som noder som har ett värde. Eftersom icke-löven inte ska skrivas ut eller behandlas på något sätt så spelar inorder, preorder och postorder ingen roll. Detta var förvirrande för de flesta.

Tal 5

I uppgiften efterfrågas dels de datastrukturer som behövs, dels en beskrivning av algoritm och dels vilka datastrukturer som behöver sparas. Det är OK att svara med bredden först, djupet först eller iterativ djupet först (har vi inte gått igenom).

Bredden först använder en kö. Djupet först använder en stack, alternativt används programstacken vid rekursiva anrop.

Prioritetskö är fel eftersom det inte är givet något om hur information viktas. Jag har dragit poäng men fortsatt att rätta algoritmen.

Det är ett allvarligt fel att först generera ett träd och först därefter traversera det.

Bredden först i korta drag:
  1. Stoppa in den ursprungliga listan i en kö och ett dumträd.
  2. Plocka ut ett element (en person) från kön.
  3. Fråga om personen känner till något dundervapen, i så fall avbryt.
  4. Annars fråga personen vem som skulle kunna känna till dundervapen.
  5. För varje person som nämns kolla om de finns i dumträdet, om inte så stoppa in dem i kön och i dumträdet.
    Det är lite mer kvalitativt att kolla mot dumträdet innan någon stoppas in i kön eftersom man i det här fallet kan misstänka att kön blir väldigt lång.
  6. upprepa från 2.
De klasser som behövs är en personklass, en kö och ett dumträd. "Faderspekare" efterfrågas inte. Man kan även använda en hashtabell istället för dumträd. För djupet först används en stack.

Kön och dumträdet måste sparas för att kunna återuppta arbetet. Om trädet gås igenom med preorder får man samma träd igen. Alternativt kan man spara trädet inorder för att sedan balansera trädet vid inläsning.

Man kan föra en liknande diskussion om hur man sparar en hashtabell t.ex. att man måste hasha in alla nycklar igen vid inläsning.

Tal 6

  1. Det som gör att koden inte fungerar är att det inte finns någon krockhantering. 
    hashvektor[hashcode] = info;
    För att lösa det kan man använda t.ex. krocklistor eller linjär sökning. Linjär sökning fungerar så att om det är upptaget på den givna positionen så söker man tills man antingen hittar nyckeln (den var redan instoppad sedan tidigare) eller tills man hittar ett tomt element i vektorn.

  2. Hashkoden är ganska korkat implementerad. Strängarna "AB" och "BA" får samma värde. 
    hashcode += (int) s.charAt(i);
    För att lösa det kan man vikta genom att multiplicera med t.ex. 1, 100 och 10000.

  3. Längden på hashvektorn är lite för liten och dessutom inget primtal. Välj istället hashvektorns storlek till exempelvis 151 (dubbel så stor som förväntade antalet element). Det är dessutom dålig programmeringsstil att hårdkoda värdet på flera ställen, använd en variabel istället.

Väldigt många har svårt att räkna ut primtal. För att hitta ett primtal i ett givet intervall t.ex. 150-160 gör följande. Undersök alla primtal upp till det primtal som är större än roten av talet, i det här fallet 2, 3, 5, 7, 11, 13. Stryk de tal som är delbara med dessa tal. Först stryker vi alltså alla jämna tal.

150 151 152 153 154 155 156 157 158 159 160

Sedan stryker vi de som är delbara med 3. 50*3 = 150 så vi kan börja från 150 och räkna till 3.

150 151 152 153 154 155 156 157 158 159 160

Sedan stryker vi de som är delbara med 5, d.v.s slutar på en 5:a eller 0:a

150 151 152 153 154 155 156 157 158 159 160

Sedan stryker vi de som är delbara med 7. 20*7 = 140 alltså är 22 * 7 = 154 men det talet är redan struket eftersom det är ett jämnt tal. Därefter undersöker vi 11 och 13. 11 * 13 = 143 så de kommer också att ha jämna och redan strukna tal i intervallet. Det är ingen mening med att undersöka talet 17 eftersom man måste multiplicera med ett redan undersökt tal (mindre tal än 13) för att få något tal i intervallet.

Talen 151 och 157 är således primtal.

En annan missuppfattning är att modulo kan returnera negativa tal även om båda argumenten är positiva. Det stämmer inte! Javas hashcode kan däremot bli negativ.

Tal 7

Räknesortering fungerar bra eftersom det bara är tre sorters element vi är intresserade av.

Räknesortering fungerar så att man först räknar förekomsten av ja-, nej- och blank-rösterna. Dessa sparar vi i en hjälpvektor.

ja nej blanka
264 514 533

Sedan använder vi hjälpvektorn för att sortera in på rätt plats.







261262263264





511512513514





531532533






jajajaja





nejnejnejnej





blankablankablanka

Komplexiteten är O(N).

I andra fallet så blir hjälpvektorn i samma storleksordning som den ursprungliga vektorn. Man vinner alltså ingenting. Om man slår upp linjärt i hjälpvektorn och sorterar in i nya vektorn blir komplexiteten kvadratisk.

Bara att bilda hjälpvektorn är komplext (nyckeln består av namn + röst) och kräver genomsökning och uppslagning.

Tal 8

D = Damer
H = Herrar
X = Fingrarna korsas
Pivot elementet är längst till höger i varje delvektor (fetmarkerad)

813524796
D





H
813524796
D



H
413528796





X
413526798
41352
D

H
41352
DH
14352

X
12354


354


DH


354



X


345






798






DH






798







X






789
Efter varje delsortering sorteras pivotelementet in på rätt plats och delvektorerna till höger och vänster sorteras. Flera har missat att sätta pivotelementet på rätt plats efter en delsortering.

Ett allvarligare fel är att skifta in element istället för att byta plats. Då är det inte quicksort längre.

813524796
D



H
135248796