Labb 1

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.

Giriga/Dynamiska Algoritmer

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.

Datastrukturer

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.

Aritmetik

Lösningarna i detta avsnitt blir mycket mer användbara om man kan välja koefficienttyp med hjälp av templates/generics, men det är inte ett krav att implementera detta.

Uppgift 1.6 Polynom-multiplikation (1p)

Implentera multiplikation av två polynom med t.ex. Karatsubas algoritm eller FFT.

Problem-id hos Kattis: polymul2. (Det finns även ett problem polymul1 med mindre gränser där en kvadratisk multiplikations-algoritm blir godkänd, som ni kanske kan ha nytta av vid debuggning, men det är alltså polymul2-uppgiften som gäller för labben.)

Uppgift 1.7: Linjära ekvationssystem

1.7.1: Lösa system med unik lösning (1p)

Implementera en rutin för att lösa linjära ekvationssystem. Med andra ord: lös ekvationen A · x = b, där A är en n×n-matris och b är en n×1-vektor.

Om ekvationssystemet saknar unik lösning (d.v.s. om matrisen A är singulär) ska detta detekteras. Det finns två fall att skilja på: system med mer än en lösning och system som saknar lösning.

Problem-id hos Kattis: equationsolver.

1.7.2: System utan unik lösning (2p)

Lös ut så många variabler som möjligt, även om ekvationssystemet är underbestämt. T.ex., givet systemet:

x1	-2·x2		=	3
2·x1	-4·x2		=	6
x1	-2·x2	+x3	=	4

kan vi lösa ut x₃ = 1, emedan x₁ och x₂ inte kan lösas ut. Om systemet saknar lösning ska det detekteras.

Problem-id hos Kattis: equationsolverplus.