• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges.
• Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

Prioritet och associativitet hos operatorerna i C

Uppgift 1 (1 p)

Uppgift 2 (3 p)

b) (1p) Beskriv något sätt att hantera kollisioner.

c) (1p) En hashtabell har storleken 10 och hashfunktionen h(k) = k mod 10. (C-programmerare kanske hellre skulle skriva den som h(k) = k % 10.) För att hantera kollisioner används metoden från deluppgift b. Talen 1, 100, 10, 1000 och -10 läggs in i hashtabellen, i den ordningen. Rita upp hur hashtabellen ser ut när talen är inlagda.

Uppgift 3 (5 p)

    int m[N][N];

a) Vi vill summera talen i matrisen m med de här programraderna:

    int summa = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            summa += m[i][j];

b) Vi provkör matrissummeringen i deluppgift a med N = 1000000 (en miljon), och ser att summeringen av matrisen m tar 1 sekund. Hur lång tid kan vi räkna med att summeringen tar om N är tre gånger så stor, dvs 3000000 (tre miljoner)?

c) Jämför datorn som vi använde i b-uppgiften med en vanlig, modern skrivbordsdator. Är datorn från b-uppgiften snabbare, ungefär lika snabb, eller långsammare?

d) Nu vill vi i stället summera talen i diagonalen i matrisen m:

    int summa = 0;
    for (int i = 0; i < N; ++i)
        summa += m[i][i];

e) Vi provkör diagonal-summeringen i deluppgift d med N = 1000000 (en miljon), på en annan dator än den i b-uppgiften, och ser att summeringen av matrisen m tar 1 sekund. Hur lång tid kan vi räkna med att summeringen tar om N är tre gånger så stor, dvs 3000000 (tre miljoner)?

f) Jämför datorn som vi använde i e-uppgiften med en vanlig, modern skrivbordsdator. Är datorn från e-uppgiften snabbare, ungefär lika snabb, eller långsammare?

g) Får matrisen m plats i minnet på en vanlig, modern skrivbordsdator, när N = 1000000 (en miljon)? (Motivera svaret.)

Uppgift 4 (4 p)

Vi kan tända alla åtta ljusen så här:

    g = 255; // 255 har bitmönstret 1111 1111

    g = 0; // 0 har förstås bitmönstret 0000 0000

    g = 5; // 5 har bitmönstret 0000 0101

Skriv C-kod för följande:

a) Tänd alla ljus utom nummer 1, som ska vara släckt.

b) Tänd ljus nummer 2, utan att påverka de andra ljusen.

c) Släck ljus nummer 3, utan att påverka de andra ljusen.

d) Heltalsvariabeln ljusnummer innehåller numret på ett ljus (1 till 8). Tänd det ljuset, utan att påverka de andra ljusen.

Scenario till uppgift 5-7

Rymdpolisen skriver upp sina utryckningar i en fil, utryckningar.txt. Varje rad i filen bekriver en utryckning, och består av ett datum, ett klockslag, namnet på den planet som utryckningen gällde, samt vad det handlade om. Exempel:

2210-08-12 18:04 Saturnus Fortkörning
2210-08-12 18:07 Glorbatron Inbrott
2210-08-13 01:33 Saturnus Bråkiga rymdmonster
2210-08-13 02:19 Zoflomork Fortkörning

För att spara bensin till rymdskeppen vill rymdpolisen upprätta en lokal polisstation på den mest brottsbelastade planeten. Vi ska därför skriva ett program som läser filen utryckningar.txt, räknar antalet utryckningar till varje planet, och till sist talar om vilken planet som hade flest utryckningar.

I exemplet ovan har vi haft två utryckningar till planeten Saturnus, och en var till planeterna Glorbatron och Zoflomork. Det är alltså Saturnus som är den mest brottsbelastade planeten.

Planetnamn består av ett enda ord. Planeternas namn är unika. Det finns flera miljoner planeter. Filen innehåller flera miljarder utryckningar.

Uppgift 5 (10 p)

Så här kan man göra:

• Läs en utryckning i taget från filen.
• För varje utryckning, leta i den länkade listan efter planeten med det namnet.
• Om planeten fanns i listan, öka antalet utryckningar för den planeten med ett.
• Om planeten inte fanns i listan, lägg in den, med antalet utryckningar satt till ett.
• När alla utryckningarna är lästa, gå igenom alla posterna i den länkade listan för att hitta planeten med flest utryckningar, och skriv ut namnet.

Programkoden ska vara tydligt och lättbegriplig, men du behöver inte dela upp programmet i filer och abstrakta datatyper. Ett tips är dock att strukturera programmet så att delar av det enkelt kan återanvändas i uppgiften nedan.

Uppgift 6 (13 p)

Skriv ett nytt program (i C eller C++) som gör samma sak, men välj nu datastrukturer som gör att programkörningen går rimligt fort.

Programkoden ska vara tydligt och lättbegriplig, men du behöver inte dela upp programmet i filer och abstrakta datatyper. Du får återanvända delar av programmet från uppgiften ovan, utan att skriva samma programkod igen.

Uppgift 7 (4 p)

a) Hur lång tid tar ditt program från uppgift 5 (det med länkade listor) att köra, om antalet utryckningar fördubblas från 3 miljarder till 6 miljarder, men antalet planeter är oförändrat 4 miljoner?

b) Hur lång tid tar ditt program från uppgift 5 (det med länkade listor) att köra, om i stället antalet planeter fördubblas från 4 miljoner till 8 miljoner, men antalet utryckningar är oförändrat 3 miljarder?

c) Hur lång tid tar ditt program från uppgift 6 (det med bättre datastrukturer) att köra, om antalet utryckningar fördubblas från 3 miljarder till 6 miljarder, men antalet planeter är oförändrat 4 miljoner?

d) Hur lång tid tar ditt program från uppgift 6 (det med bättre datastrukturer) att köra, om antalet planeter fördubblas från 4 miljoner till 8 miljoner, men antalet utryckningar är oförändrat 3 miljarder?

Förklara kort hur du räknat eller resonerat.