Kurswiki för Algorithms(TIN092)
Tentor
Det är lite blandat men de flesta är skapade av Erland och passar inte lika bra för en kurs med Peter.
Länkar
Wikipedia
Allmänt
Algoritmer
Problem
Lösningar
[Solved excercises i boken]
Kapitel 3 - Graphs
3.11 Virus
Man kan definiera varje tidpunkt som en "nivå" i grafen och på denna nivå skapa noder för alla datorer som kommunicerar vid denna tidpunkt och förbinda dessa med varandra med oriktade kanter. Sedan drar man från varje nod i varje nivå en riktad kant till nästa tillfälla samma nod kommunicerar igen.
För att undersöka om nod Ca som infekterades vid tidpunkt x kan ha infekterat nod Cb vid tidpunkt y letar man reda på första tidpunkt >= x som Ca kommunicerar vid och startar en BFS (eller DFS) i denna nod. När sökningen är avslutad (eller under tiden) undersöker man om Cb påträffas på en nivå som motsvarar tidpunkt <= y. Efter som BFS tar O(m+n) tid kommer även denna algoritm att göra det.
Ex. för
(C1, C2, 4), (C2, C4, 8), (C3, C4, 8), (C1, C4, 12)
blir trädet
C1 - C2 (4)
| |
| v
| C2 - C3 - C4 (8)
| |
v v
C1 ----------- C4 (12)
Kapitel 4 - Greedy Algorithms
4.4 Undersök om S' är en delsekvens av S.
Använd en pekare för varje lista som pekar på första elementet i listan. Jämför pekarna med varandra:
- Om elementen stämmer, avancera båda pekarna.
- Om de inte gör det, avancera endast S-pekaren.
Avsluta när en av pekarna når slutet av respektive lista:
- Om S'-pekaren når slutet först -> S' är en delsekvens av S.
- Om S-pekaren når slutet först -> S' är inte en delsekvens av S.
Kapitel 5 - Divide and Conquer
5.3 Finns det mer än n/2 kort som är likvärdiga?
Detta kan lösas mha d&c. Tänk dig att du delar upp mängden i allt mindre halvor. Till sist kommer du att ha n/2 delmängder med två kort i varje. Om det finns mer än n/2 kort som är likvärdiga kommer åtminstone ett av dessa par vid undersöknung befinnas vara likvärdiga (om det hade funnits n/2 st kunde precis ett av de n/2 likvärdiga korten finnas i vart och ett av paren, och då inte upptäckas). Genom att jämföra svaren från testen av de olika delmängderna och returnera sant om ett av delmängderna returnerar sant kommer man kunna ta reda på om det finns mer än n/2 likvärdiga par på O(n log n) tid.
Equivalent(S) := Equivalent(Sleft half) OR Equivalent(Sright half)
5.6 Hitta en nod vars barn och förälder har högre värde än noden själv.
Trädet är komplett, dvs antalet noder per nivå är 1, 2, 4, 8 osv.
Börja i roten av trädet och jämför nodens värde med värdena på nodens barn. Är barnens värde högre än noden har du hittat ett lokalt minimum. Är något av barnen lägre, gå dit istället. Upprepa förfarandet. Eftersom vi gick till en nod som hade lägre värde än den förra vet vi att föräldern till aktuell nod har ett högre värde en aktuell nod och vi behöver bara kontrollera barnen. Har vi nått ett löv är detta ett lokalt minimum eftersom lövet inte har några barn och föräldern har ett högre värde.
T(n) = T(n/2) + O(1) -> O(log n)
Kapitel 6 - Dynamic Programming
6.1 OPT(j) = max { OPT(j-1), OPT(j-2) + vj }
6.2 OPT(j) = max { OPT(j-1) + lj, OPT(j-2) + hj }
6.4
OPT() = min { OPT_NY(n), OPT_SF(n) }
OPT_NY(j) = min { OPT_NY(j-1) + NYj, OPT_SF(j-1) + NYj + M }
OPT_SF(j) = min { OPT_SF(j-1) + SFj, OPT_NY(j-1) + SFj + M }
6.5 OPT(j) = max { qualityi j + OPT(i-1) }, 1 <= i <= j
6.11 OPT(j) = min { OPT(j-1) + r * si, OPT(j-4) + c * 4 }
6.17 (Jag vet inte om detta är en optimal lösning eller om den kan klassas som dynamisk programmering)
Definiera:
- SUB(1) := 1
- SUB(j) := max { SUB(i) + 1 }, 1 <= i < j & P[i] < P[j] om P[j] > P[1]
- SUB(j) := 0 annars (P[j] <= P[1])
Optimala lösningen fås sedan av max { SUB(j) }, 1 <= j <= n
Kapitel 8 - NP and Computational Intractability
8.3 Efficient Recruiting Problem
För att visa att detta problem är NP-fullständigt kan man reducera från Vertex Cover enligt följande.
Skapa en lägerledare för varje nod i grafen och för varje kant, skapa en ny sport. Låt de två lägerledare som förbinds av kanten vara utbildade i sporten som kanten motsvarar.
Exempelgrafen på s. 454 i Algorithm Design kan beskrivas på följande sätt mha en "incidence matrix" där Li står för lägerledare i och Sj sport j:
S1 S2 S3 S4 S5 S6 S7 S8 S9 S10
L1 x x
L2 x x x x
L3 x x x x
L4 x x
L5 x x
L6 x x
L7 x x x x
Lösningar är bl.a. {L1, L2, L6, L7} och {L2, L3, L7}
Bevis någon?
8.5 Hitting Set Problem
Detta problem kan visas vara NP-fullständigt genom att reducera från Vertex Cover på följande sätt.
För en graf G = (V, E), sätt A = V och skapa en samling Bi för varje par av noder som förbinds av en kant och lägg i samlingen de noder som kanten förbinder. Ex. för kanten e = (v, w) och samlingen Bj så gäller Bj = {v, w}.
Vanliga problem
Subset Sum
Knapsack
Interval Scheduling
Weighted Interval Scheduling
Skyline
Problem
You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom (the city they are built in is very flat). The city is also viewed as two-dimensional. A building is specified by an ordered triple (Li,Hi,Ri) where Li and Ri are left and right coordinates, respectively, of building i and Hi is the height of the building.
Example input triples: (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)
The output should consist of the vector (v1,v2,...,vn-1,vn) that describes the skyline. In the skyline vector, the vi such that i is an even number represent a horizontal line (height). The vi such that i is an odd number represent a vertical line (x-coordinate). The skyline vector should represent the "path" taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in the skyline vector will be a 0. The coordinates must be separated by a blank space.
Example output vector: (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)
Lösning
You need to Merge two skylines, similar to the merge sort
For instance: there are two skylines,
- A: a1, h11, a2, h12, a3, h13, ..., an, 0
- B: b1, h21, b2, h22, b3, h23, ..., bm, 0
Merge (list of a’s, list of b’s) form into (c1, h11, c2, h21, c3, ..., cn+m, 0)
Clearly, we merge the list of a's and b's just like in the standard Merge algorithm. But, it addition to that, we have to properly decide on the correct height in between each set of these boundary values. We can keep two variables, one to store the current height in the first set of buildings and the other to keep the current height in the second set of buildings. Basically we simply pick the greater of the two to put in the gap.
After we are done, (or while we are processing), we have to eliminate redundant "gaps", such as 8, 15, 9, 15, 12, where there is the same height between the x-coordinates 8 and 9 as there is between the x-coordinates 9 and 12. (Similarly, we will eliminate or never form gaps such as 8, 15, 8, where the x-coordinate doesn't change.)
Since merging two skylines of size n/2 should take O(n), letting T(n) be the running time of the skyline problem for n buildings, we find that T(n) satisfies the following recurrence:
T(n) = 2T(n/2) + O(n)
Thus, just like Merge Sort, for the Skyline problem T(n) = O(n log n).
Independent Set
Clique
Vertex Cover
The Vertex Cover problem takes as input a graph G and an integer k and asks whether G contains a vertex cover of at most k nodes. We show that Independent Set and Vertex Cover are polynomial-time reducible to each other. The key observation is that C (subset of) V is a vertex cover if and only if V \ C is an independent set. Vertex covers and independent sets are complementary sets in the same graph. Hence, a vertex cover of size at most k exists if and only if an independent set of size at least n − k exists (and similarly in the other direction).
