Programmeringsmetodik: Tentamen 2010-12-11

Det här är datortentan som går lördag 11 december 2010 i kursen Programmeringsmetodik, kl 8:15-12:15. Lokal: T120, och vid behov T124.

Gäller som tentamen för:
DT2010 Datateknik B, Programmeringsmetodik, provkod 0100
DT2006 Datateknik B, Tillämpad datavetenskap B, provkod 0110

Ansvarig lärare är Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), telefon 070-73 47 013.

Instruktioner

  1. Det här är inte en hemtenta, utan man måste göra den i tentasalen, ungefär som en vanlig salstenta.
  2. Normalt används Visual Studio på era vanliga datorkonton, men man kan också använda en egen bärbar dator, om man har (egen, trådlös) nätuppkoppling på den. GCC under Linux går bra som alternativ till Visual Studio.
  3. Skicka in lösningarna till mig (thomas.padron-mccarthy@oru.se) senast klockan 12:15. Spara också själv en kopia, ifall det blir något fel med posten!
  4. Lämna också in den särskilda pappersblanketten, med dina lösta uppgifter förkryssade, så det finns på papper vilka som deltagit och vilka uppgifter de löst.
  5. Använd C eller C++.
  6. Packa ihop hela katalogen med applikationen i en Zip-fil, och skicka den som en bilaga. Men döp först om Zip-filen från nånting.zip till exempelvis nånting.info för att överlista överambitiösa virusfilter.
    Spara också själv en kopia, ifall det blir något fel med posten!
  7. För att en lösning på en uppgift ska bli godkänd krävs att den fungerar (utom möjligen för vissa konstiga specialfall) och att den inte strider mot specifikationen.
  8. För betyget 3 respektive G krävs godkänt på uppgift 1. För betyget 4 respektive VG krävs godkänt på både uppgift 1 och 2. För betyget 5 krävs godkänt på uppgift 1, 2 och 3.
  9. Godkänt resultat på denna tentamen ger betyget 3, 4 eller 5 (respektive G eller VG) på teoridelen av kursen. Tillsammans med godkända inlämningsuppgifter ger godkänt resultat på den här tentan ett godkänt betyg på hela kursen. Betyget på hela kursen blir samma som på tentan.

Hjälpmedel vid tentamen

  1. Uppgiften ska lösas enskilt, dvs inga grupper av två eller flera studenter.
  2. Du får använda datorn, böcker och vilka andra hjälpmedel som helst, men du får inte samarbeta eller fråga någon (utom mig). Det är alltså tillåtet att söka med Google, eller på frågeforum som Stack Overflow, men det är inte tillåtet att posta egna frågor.
  3. Om du behöver fråga något, så kontakta läraren. Jag finns på plats i datorsalarna, eller via mobilnumret ovan.

Scenario

Vi behöver räkna saker, och hålla reda på hur många av varje sak vi har. Det kan vara tändstickor, bilar eller vad som helst. Därför ska vi skapa ett program som håller reda på ett stort antal räknare.

Programmet ska läsa en textfil som innehåller några enkla kommandon, ett på varje rad i filen, och utföra dessa kommandon. Kommandona är till för att skapa, ta bort och öka värdet på räknare:

  1. Skapa en räknare. Skapa-kommandot har följande format:
    C heltal
    Till exempel:
    C 817
    Detta innebär att programmet ska skapa en räknare, som identifieras av heltalet 817, och som har ett initialt värde på 0.

    Programmet ska ge ett varningsmeddelande om man försöker skapa en räknare med ett nummer som redan har skapats (men inte tagits bort). Sen ska programmet ignorera det kommandot, och fortsätta.

  2. Ta bort en räknare. Borttagningskommandot har följande format:
    R heltal
    Till exempel:
    R 99682
    Detta innebär att programmet ska radera räknare nummer 99682.

    Programmet ska ge ett varningsmeddelande om man försöker ta bort en räknare som inte har skapats eller som redan har tagits bort. Sen ska programmet ignorera det kommandot, och fortsätta.

  3. Öka värdet på en räknare. Det kommandot har följande format:
    I heltal
    Till exempel:
    I 302122
    (Bokstaven "I" står för "increment", som betyder "öka" på engelska.) Detta innebär att programmet skall öka värdet på räknaren som identifieras med talet 302122. Om räknaren just hade skapats, så att dess värde var 0, kommer den nu att få värdet 1. Om den hade värdet 1, kommer den nu att få värdet 2, och så vidare.

    Programmet ska ge ett varningsmeddelande om man försöker öka en räknare som inte har skapats eller som redan har tagits bort. Sen ska programmet ignorera det kommandot, och fortsätta.

Man kan anta att alla rader i textfilen börjar med en bokstav (antingen C, R eller I), följt av ett mellanslag, följt av ett positivt heltal skrivet med vanliga decimala siffror, följt av radslut, så man behöver inte utföra någon felkontroll av filens formatering.

Efter bearbetning av textfilen ska programmet skriva ut nummer och värde på alla räknare som då finns.

Exempel

Det finns tre textfiler som man kan använda för att provköra programmet: counters1.txt, counters2.txt och counters3.txt.

Här nedan ser vi hur utmatningen från programmet kan se ut, när det körs med dessa tre filer som data. Dialogen och varningsmeddelanden behöver inte se ut exakt så här, men de data som skrivs ut för räknarna ska vara desamma.

Med filen counters1.txt: 

Ge filens namn: counters1.txt
Det finns 4 räknare:
2: 4
3: 1
1000: 1
1: 0
Med filen counters2.txt: 
Ge filens namn: counters2.txt
Det finns 7 räknare:
101: 10
103: 12
104: 10
105: 8
10000: 10
107: 10
110: 10
Med filen counters3.txt: 
Ge filens namn: counters3.txt
Varning: Räknare 1000 fanns redan, så den skapades inte.
Varning: Räknare 1001 fanns inte, så den kunde inte ökas.
Varning: Räknare 1000 fanns inte, så den kunde inte ökas.
Varning: Räknare 1000 fanns inte, så den kunde inte tas bort.
Varning: Räknare 1000 fanns redan, så den skapades inte.
Varning: Räknare 1002 fanns inte, så den kunde inte tas bort.
Det finns 2 räknare:
1003: 0
1000: 1

Tips

Detta program kan skrivas på olika sätt, men en möjlig väg är att lägga alla räknare i en länkad lista. När en räknare skapas (med "C"-kommandot), sätts en ny post ("struct") in i listan. När en räknare ökas (med "I"-kommandot), letar vi först igenom listan för att hitta rätt post, och sedan ökas värdet som lagrats i den. När en räknare tas bort (med "R"-kommandot), letar vi i listan för att hitta rätt post, och tar sedan bort den ur listan.

1. Uppgift för betyget 3 respektive G

Lös denna uppgift först, och skicka in den. Spara också själv en kopia, ifall det blir något fel med posten! Börja inte med de andra uppgifterna innan du är klar med denna, och har skickat in den.

Skriv räknarprogrammet. Gör en lösning där räknarna lagras i en länkad lista. Söknyckeln ska vara räknarnas nummer.

Det ska vara en länkad lista specifikt för detta ändamål, så använd inte någon generell datatyp (som std::list).

Alla positiva heltal (som går att representera med den vanliga datatypen int) kan användas som nummer på räknare. Det ska gå att lagra många miljoner räknare i listan, även om programmet då kommer att gå ganska långsamt.

Man får, men behöver inte, dela upp programmet i flera filer.

2. Uppgift för betyget 4 respektive VG

Lös först uppgift 1, och skicka in den. Därefter kan du lösa, och skicka in, den här uppgiften. Spara också själv en kopia, ifall det blir något fel med posten! Börja inte med uppgift 3 innan du är klar med denna, och har skickat in den.

Programmet från uppgift 1 ovan fungerar bra på små exempeldata, som våra exempelfiler, men om man har flera miljoner räknare tar programmet mycket lång tid att köra.

Gör en ny version av programmet som använder en bättre datastruktur, förslagsvis en hashtabell eller ett binärt träd. Vi vill ha en enorm förbättring av körtiden.

Datastrukturerna som används ska vara skapade specifikt för detta ändamål, så använd inte någon generell datatyp. Man får, men behöver inte, dela upp programmet i flera filer.

Programmet generate-big-test-file.c kan användas för att generera en fil, "counters4.txt", som först skapar 100000 räknare, sen räknar upp alla dessa med ett, och till sist tar bort alla utom den sista (med nummer 100000). På min dator tog den drygt en minut att köra med länkad-liste-programmet från uppgiften ovan, och det ska alltså gå enormt mycket snabbare med programmet från den här uppgiften.

3. Uppgift för betyget 5

Lös först uppgift 1 och 2, och skicka in dem. Därefter kan du lösa, och skicka in, den här uppgiften. Spara också själv en kopia, ifall det blir något fel med posten!

Gör om uppgift 1 eller 2 med hjälp av en generell datatyp.

Skapa först den generella datatypen (till exempel hashtabellen GenericHashTable). Välj själv metod för att skapa en generell datatyp. Dela upp på lämpliga filer. Det är inte förbjudet att inspireras av existerande lösningar, men du ska lämna in en som du gjort själv.

Använd den därefter i räknar-programmet.

Den här sista-uppgiften för betyget 5 kanske kan ta lite längre tid att lösa. Om den inte är helt klar när tentatiden tar slut, är det därför tillåtet att skicka in en preliminär lösning, som man sedan kan komplettera. Ange tydligt att det är en preliminär lösning. Kompletteringen ska skickas in senast en vecka efter tentan.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 9 december 2010