Labb 1

Deadline för labb 1 är 2013-02-12 kl 12:00

Läs igenom labbinstruktionerna innan ni börjar.

Tips: I speciellt C++ men även Java är det ganska praktiskt att använda iteratorer för att representera vektorer/mängder/etc. För ett exempel på detta för längsta ökande delsekvens (uppgift 1.3 nedan), se här. En stor fördel med detta är att funktionen inte kräver att talen är lagrade i någon speciellt datatyp, man kan använda array, vector, list, eller vilken annan container som helst som har de operationer man behöver kunna utföra på containern.

Observera att API-förslagen nedan är att betrakta som pseudo-kod, ni får översätta dem till ert favoritspråk på det sätt ni tycker verkar bäst.

Rekommenderad tidskomplexitet innebär att du bör sikta på denna komplexitet för att klara tidskraven på Kattis-uppgifterna.

Uppgift 1.1: Intervalltäckning

(1p)

I problemet intervalltäckning har vi ett målintervall som vi vill övertäcka med hjälp av ett antal givna intervall, och vi vill använda så få av dem som möjligt.

Om målintervallet t.ex. är [-0.5, 1] och vi har intervallen {[-0.9, -0.1], [-0.2, 2], [-0.7, 1]} skulle vi kunna använda de två första intervallen för att täcka in målintervallet, men en bättre (den bästa i det här fallet) lösning vore att bara använda ett intervall, det sista.

Förslag till API:
int[] cover(interval, interval[])
(där den returnerade int-vektorn är indexen för de utvalda intervallen)

Rekommenderad tidskomplexitet: O(n log n), där n är antalet intervall vi har tillgängliga.

Problem-id hos Kattis: intervalcover.

Uppgift 1.2: Kappsäck

(1p)

I kappsäcksproblemet har vi n saker (t.ex. ädelstenar). Varje sak har ett värde och en vikt. Vi har en kappsäck i vilken vi kan packa ner saker, men den totala vikten av sakerna vi packar ner får vara högst capacity. Vi vill packa ner saker så att det totala värdet av de nedpackade sakerna blir så stort som möjligt.

Implementera en funktion som löser kappsäcksproblemet när vikterna är heltal. Funktionen ska returnera de saker som ingår i någon optimal packning.

Förslag till API:
int[] knapsack(capacity, value/weight[])
(där den returnerade int-vektorn är indexen för de utvalda sakerna)

Rekommenderad tidskomplexitet: O(n·capacity).

Problem-id hos Kattis: knapsack.

Uppgift 1.3: Längsta ökande delsekvens

(1p)

Implementera en funktion som finner en längsta ökande delsekvens i en given sekvens.

Förslag till API:
int[] lis(object[])
(där den returnerade int-vektorn är de index som utgör en längsta ökande delsekvens)

Rekommenderad tidskomplexitet: O(n log n), där n är antalet objekt i sekvensen.

Problem-id hos Kattis: longincsubseq.

Uppgift 1.4: Disjunkta mängder / ekvivalensrelation

(1p)

Implementera en datastruktur för att hantera disjunkta mängder, med följande operationer:

union(int a, int b) - anger att mängderna innehållande a och b ska slås ihop
boolean same(int a, int b) - testar om a och b ligger i samma mängd

Vid start är alla element i en egen mängd för sig själva.

Problem-id hos Kattis: unionfind.

Uppgift 1.5: Prefixsummor

(1p)

Implementera en datastruktur för att hantera prefixsummor av en array a[0], a[1], ..., a[N-1], med följande operationer:

add(index i, number delta) - anger att a[i] ska inkrementeras med delta
number sum(index end) - beräknar summan av de första talen upp till (men ej inräknat) a[end]

Problem-id hos Kattis: fenwick.

Uppgift 1.6: Strängsökning

(1p)

Implementera en funktion med vilken man kan hitta alla förekomster av en sträng pattern i en annan sträng text.

Förslag till API:
position[] find(string pattern, string text)

Rekommenderad tidskomplexitet: O(text + pattern).

Problem-id hos Kattis: stringmatching.

Ett bra testfall att tänka på om er kod är för långsam, är text = aaa...a (200000 tecken), pattern = aaaa...a (100000 tecken). Alla index från 0 till 100000 är då matchande positioner. Prova även att göra detta testfall dubbelt så stort (dvs dubblera text och pattern). Er lösning borde bara ta ca dubbel så lång tid på detta testfall (emedan en kvadratisk lösning skulle ta fyra gånger så lång tid).

Bonus (1p): Implementera en funktion som hittar alla förekomster av flera strängar pattern[] i en annan sträng text.

Förslag till API:
position[][] find(string pattern[], string text)

Rekommenderad tidskomplexitet: O(text + pattern[] + k), där k är det totala antalet matchningar av alla mönster.

Problem-id hos Kattis: stringmultimatching.

Obs! En lösning på bonus-uppgiften utgör även en lösning på den enklare uppgiften (eftersom k högst är textlängden om vi bara har ett mönster).

Uppgift 1.7: Suffixsortering

(2p)

Ett suffix är en del av en sträng som utgör slutet av strängen. Strängen "popup" har 5 suffix: "p", "up", "pup", "opup", och slutligen "popup". Ett suffix kan betraktas som en position i strängen, som anger vart suffixet börjar.

Implementera en datatyp som sorterar en strängs suffix i lexikografisk ordning. Datatypen ska ha följande operationer:

constructor(string s) - skapar ett suffixobjekt från en sträng.
position getSuffix(i) - returnerar det i:te minsta suffixet.

Sorterar vi suffixen från strängen popup får vi: "opup", "p", "popup", "pup", "up". Om vi konstruerar ett suffixobjekt från "popup" ska vi alltså få: getSuffix(0) = 1, getSuffix(1) = 4, getSuffix(2) = 0, getSuffix(3) = 2, getSuffix(4) = 3.

Rekommenderad tidskomplexitet: O(s log s) för konstruktorn (obs! tänk på att jämförelser av strängar tar tid!), och konstant tid för getSuffix.

Problem-id hos Kattis: suffixsorting.

Ett bra testfall att tänka på om er kod är för långsam, är s = <W><W>, där W är en 50000 tecken lång slumpsträng.