bild
Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD2458 / popup11 / Labbar / Labb 1

Labb 1

Deadline för labb 1 är måndag 14 februari 20: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.4 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 betraktas 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: 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 (100000 tecken), pattern = aaaa...a (50000 tecken). Alla index från 0 till 50000 är då matchande positioner.

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.2: 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.

Uppgift 1.3: Indexmappning

(1p)

Implementera en datatyp med följande operationer:

  • int getIndex(object o) - mappar objektet o till ett index.
  • object getObject(int i) - mappar ett index till ett objekt.

Notera att getIndex() har bieffekter när man anropar den med ett objekt som man inte använt förut, i det att den tilldelar objektet ett index.

Ni ska också kunna hantera anrop med index som inte har något objekt mappat till sig.

Följande måste alltid gälla:

  • getObject(getIndex(o)) == o
  • getIndex(getObject(i)) == i
  • Det i:te unika objekt som getIndex anropas med får index i-1.

Rekommenderad tidskomplexitet: genomsnittlig körtid O(log n) för getIndex och konstant körtid för getObject.

Problem-id hos Kattis: indexmapping.

Uppgift 1.4: Längsta ökande delsekvens

(2p)

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.5: 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.6: 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.

Copyright © Sidansvarig: Mikael Goldmann <migo@kth.se>
Uppdaterad 2011-02-01