Programmeringsmetodik: Tentamen 2011-12-10

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

Gäller som tentamen för:
DT2011 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.

Tillägg: Lösningsförslag till uppgift 1 och 2

Instruktioner

Det här är inte en hemtenta, utan man måste göra den i tentasalen, ungefär som en vanlig salstenta.
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.
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!
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.
Använd C eller C++.
Packa ihop hela katalogen med applikationen i en Zip-fil (eller motsvarande), 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!
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.
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.
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

Uppgiften ska lösas enskilt, dvs inga grupper av två eller flera studenter.
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.
Om du behöver fråga något, så kontakta läraren. Jag finns på plats i datorsalarna, eller via mobilnumret ovan.

Scenario

Det är inte så många som vet det, men sökmotorn Google sköts egentligen från ett callcenter i Bangalore i Indien. När någon skriver in en sökning på Googles hemsida, slår Googles anställda i Indien upp sökorden i sina pärmar.

Trafiken till Google ökar för varje år, och nu börjar det bli svårt för de anställda att hinna med. Dessutom har pärmarna blivit ganska slitna.

Därför vill Google nu bygga en datoriserad sökmotor.

Det man vill bygga är ett program som läser in en fil med sökord och webbadresser, till exempel dessa:

bil http://en.wiktionary.org/wiki/bil
konceptteater http://www.unt.se/kultur/essa/klassiker-och-konceptteater-211678.aspx
svampskog http://lt.se/asikter/debatt/1.1338633-odelagd-svampskog
bil http://acronyms.thefreedictionary.com/BIL

Varje rad innehåller ett sökord, ett mellanslag, och en adress till en webbsida. Inga sökord är längre än 100 tecken. Inga webbadresser är längre än 1000 tecken. Samma sökterm kan förekomma på många webbsidor. På riktigt kan filen ha många miljoner rader.

När filen med sökord och webbadresser är inläst, ska man kunna använda programmet för att slå upp ord och få reda på vilka webbsidor de finns på.

1. Uppgift för betyget 3 respektive G

Skriv ett program som läser filen med sökord och webbsidor, och lagrar dessa i en lämplig datastruktur. Programmet ska sedan upprepat fråga efter en sökterm. För varje sökterm ska programmet skriva ut antalet webbsidor där den finns, och sedan lista deras adresser.

Ett körexempel som använder exempelfilen ovan, med användarens inmatning i rött:

Ange indatafilens namn: exempel4.txt
Läser filen...
Klar. 3 unika sökord. 4 webbadresser.

Ange ett ord: svampskog
Hittade 1 webbsida.
http://lt.se/asikter/debatt/1.1338633-odelagd-svampskog

Ange ett ord: bild
Hittade 0 webbsidor.

Ange ett ord: bil
Hittade 2 webbsidor.
http://en.wiktionary.org/wiki/bil
http://acronyms.thefreedictionary.com/BIL

Ange ett ord:

Programmet måste kunna hantera miljoner sökord och webbadresser. Det finns inga krav på felhantering.

Använd en array eller en länkad lista. (Eller flera.) Det ska vara datastrukturer gjorda specifikt för detta ändamål, så använd inte någon generell datatyp som till exempel std::list. Man får, men behöver inte, dela upp programmet i flera filer.

Exempelfiler som man kan provköra med:

exempel4.txt. Filen innehåller 4 rader och 3 unika ord, enligt exemplet i scenariot. Sökordet bil förekommer två gånger.
exempel10.txt. Filen innehåller 10 rader och 6 unika ord. Sökordet apa förekommer fem gånger.
exempel1000.txt. Filen innehåller 1000 rader och 991 unika ord. Sökordet apa förekommer 10 gånger.
skapa1M.c. Det här är inte en testfil, utan ett C-program som skapar en testfil. Det skapar filen exempel1M.txt, som innehåller 1 miljon rader och 999991 unika ord. Sökordet apa förekommer 10 gånger.

Dessa filer finns även som en zip-fil: testfiler.zip

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 i uppgift 1 behöver bli snabbare. Gör därför en ny version av programmet, men med snabbare datastrukturer. Vi vill ha en enorm förbättring av prestanda.

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.

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 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 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), 10 december 2011