Opgave 1 *********************************************************** i) T(n) = Theta(n) via Master Theorem Case III ii) T(n) = Theta(log(n)n^2.5) via Master Theorem Case II Opgave 2 *********************************************************** i) Sand ii) Sand iii) Sand iv) Falsk v) Sand vi) Falsk vii) Sand viii) Sand ix) Sand x) Falsk Opgave 3 *********************************************************** 10 8 9 7 6 3 5 2 4 1 Opgave 4 *********************************************************** H: 18 x 8 3 x 6 5 x 30 25 15 2 23 Opgave 5 *********************************************************** A: 5001 7112 9112 2222 8345 4345 6363 1830 Opgave 6 *********************************************************** a: 111 e: 0 i: 110 o: 1011 u: 100 y: 1010 Fillængde: 4450 bits Opgave 7 *********************************************************** ** Spørgsmål a: (b,c), (a,f), (a,c), (d,e), (d,f) ** Spørgsmål b: {a,b,c,d,e,f} {g} ** Spørgsmål c: 45 ** Spørgsmål d: Træ 1: (a,b),(b,c),(a,f),(a,d),(d,e), rod=a, rang=2 Træ 2: rod=g, rang=0 [ingen kanter i træet] Opgave 8 *********************************************************** Worst case Best case CountingSort A A InsertionSort C A MergeSort B B QuickSort C C Opgave 9 *********************************************************** Algoritme1: O(n^2) Algoritme2: O(n log(n)) Algoritme3: O(n^3) Algoritme4: O(n) Opgave 10*********************************************************** ** Spørgsmål a: n = k^2 n = 3k^2 - 3k ** Spørgsmål b: O(k^2 log(k)) ** Spørgsmål c: Lad v være en vilkårlig knude. Der findes [som bekendt fra pensum] altid en korteste sti fra startknuden til v, som er simpel, dvs. som er uden gentagne knuder. [Argumentet er: en gentagen knude i en sti betyder nemlig at der er en kreds (cykel) i stien, og da alle kantvægte er ikke-negative, kan sådanne kredse blot skæres væk uden at gøre stien længere.] En simpel sti fra startknuden v_{1,1} til v må pga. grafens udseende have følgende form: 0 eller flere kanter mod højre 1 skridt op 0 eller flere kanter mod højre ELLER 0 eller flere kanter mod venstre 1 skridt op 0 eller flere kanter mod højre ELLER 0 eller flere kanter mod venstre . . Fra lemma 24.15 vides, at hvis kanterne på en korteste sti fra startknuden til en knude v relaxeres i stiens rækkefølge (gerne med relaxering af andre kanter blandet ind i mellem), så vil v.d derefter være sat korrekt, dvs. til v's afstand fra startknuden (og kan derefter ikke ændres via relaxeringer). Kombineres dette med ovenstående viden om udseendet af simple stier i grafen, ser vi at følgende algoritme ved dens afslutning vil have sat v.d korrekt for alle knuder, eftersom den for alle knuder relaxerer kanterne på en korteste sti til knuden i denne stis rækkefølge: //Initialiser for i = 1 to k: for j = 1 to k: v.d = infinity v_{1,1}.d = 0 // relax højrevendte kanter i lag 1, fra venstre mod højre for j = 1 to k-1: relax(v{1,j},v_{1,j+1}) // for alle lag i >= 2 for i = 2 to k: // relax opvendte kanter fra lag i-1 til lag i for j = 1 to k: relax(v{i-1,j},v_{i,j}) // relax højrevendte kanter i lag i, fra venstre mod højre for j = 1 to k-1: relax(v{i,j},v_{i,j+1}) // relax venstrevendte kanter i lag i, fra højre mod venstre for j = 1 to k-1: relax(v{i,k-j+1},v_{i,k-j}) Algoritmen relaxerer hver kant højst een gang, hvilket tager O(m) tid. Derudover bruger den O(n) tid på initialisering. Da n er O(m) for kvadrat-grafer, kører den i O(m) tid. [Dvs. i tid O(k^2), hvilket er en faktor log(k) hurtigere end Dijkstra].