Opgave 1 *********************************************************** ** Spørgsmål a: Sorte: a,b,c,d,e,g,h,i Røde: f ** Spørgsmål b: Sorte: a,h,i,j,k,l,m,n,o, b,c Røde: d,e,f,g Sorte: a,h,i,j,k,l,m,n,o, b,f,g Røde: d,e,c Sorte: a,h,i,j,k,l,m,n,o, c,d,e Røde: b,f,g Sorte: a,h,i,j,k,l,m,n,o, d,e,f,g Røde: b,c Sorte: a,h,i,j,k,l,m,n,o, b,c,d,e,f,g Røde: (ingen) Opgave 2 *********************************************************** ** Spørgsmål a: A2, A4 ** Spørgsmål b: 2 3 5 4 7 9 6 8 10 Opgave 3 *********************************************************** ** Spørgsmål a: T(n) = log(n)*n^1.5 ** Spørgsmål b: [NB: Denne besvarelse indeholder argumenter for svarene, men dette er ikke krævet - den sidste linie i svaret for hver rekursionsligning er nok for fuldt point.] i) Her er log_b(a) = log_13(14) > 1.02 og f(n) = n. Case 1 af master theorem matcher med f.eks. epsilon = 0.01 [da n = O(n^(1.02-0.01)] = O(n^1.01). Så i) kan løses med master theorem, case 1. ii) Her er log_b(a) = log_13(13) = 1 og f(n) = n log(n). Da n^(1-epsilon) < n og n log(n) asymptotisk vokser skarpt hurtigere end n [dvs. n log(n) = lille-omega(n)], kan hverken case 1 eller case 2 af master theorem matche. For ethvert epsilon > 0 gælder at n log(n) = o(n^(1+epsilon)) [da (n log(n))/n^(1+epsilon) = log(n)/n^epsilon -> 0 for n -> infinity]. Derfor kan heller ikke case 3 af master theorem matche. Så ii) kan ikke løses med master theorem. iii) Her er log_b(a) = log_13(14) > 1.02 og f(n) = n log(n). Case 1 af master theorem matcher med f.eks. epsilon = 0.01 [da n log(n) = O(n^(1.02-0.01)), da (n log(n))/n^1.01 = log(n)/n^0.01) -> 0 for n->infinity]. Så iii) kan løses med master theorem, case 1. iv) Her er log_b(a) = log_14(13) < 0.98 og f(n) = n. Case 3 af master theorem matcher derfor med f.eks. epsilon = 0.01 [da n = store-omega(n^(0.98+0.01)], hvis den ekstra sidebetingelse for case 3 også er opfyldt. Da 13*f(n/14) = 13*n/14 <= 13/14*f(n) er denne sidebetingelse opfyldt. Så iv) kan løses med master theorem, case 3. Opgave 4 *********************************************************** ** Spørgsmål a: a.d = 0, b.d = 17, c.d = 9, d.d = 1, e.d = 7, f.d = -10, g.d = 12, h.d = 0 ** Spørgsmål b: (g,h), (f,h), (b,g), (e,h), (c,g), (d,h), (a,e) ** Spørgsmål c: Discovery/finish tider: a: 1/16, b: 2/15, c: 4/13, d: 5/12, e: 6/11, f: 8/9, g: 3/14, h: 7/10 Opgave 5 *********************************************************** ** Spørgsmål a: 2250 bits ** Spørgsmål b: abbedcd ** Spørgsmål c: H2, H5 Opgave 6 *********************************************************** ** Spørgsmål a: i: 53 52 26 13 12 6 3 2 1 k: 0 0 1 2 2 3 4 4 5 ** Spørgsmål b: Basis/initialisering: i) k=0 og i=n => floor(log(i)) + k = floor(log(n)) + 0 = floor(log(n)) ii) i = n og n er et heltal => i er et heltal Induktionsskridt: Antag invarianten gælder før en iteration af while-løkken. Vi skal vise at den så gælder efter. For de to variable lad i', k' stå for deres værdi før iterationen, og lad i, k stå for deres værdi efter. Pr. antagelse ii) er i et heltal. Hvis det er lige, fås ifølge oplysning 1), invariant i), samt algoritmens handlinger at floor(log(i)) + k = floor(log(i'/2)) + (k'+1) = floor(log(i')) - 1 + (k'+1) = floor(log(i')) + k' = floor(log(n)). Derudover er i = i'/2 et heltal. Hvis det er ulige, fås ifølge oplysning 2), invariant i), samt algoritmens handlinger at floor(log(i)) + k = floor(log(i'-1)) + k' = floor(log(i')) + k' = floor(log(n)). Derudover er i = i' et heltal. I begge tilfælde er vist at invariant i) og ii) gælder efter iterationen. ** Spørgsmål c: Når i > 1 er et heltal, er i/2 <= i-1. Derfor falder i med mindst een pr. iteration af while-løkken. Algoritmen må derfor stoppe. Hvis nul iterationer har været udført, gælder n <= 1. Vi skal kun argumentere for korrekthed for n >= 1, så i dette tilfælde er n = 1. Da algoritmen returnerer 0, er svaret korrekt. Hvis mindst een iteration har været udført, ser vi på den sidste. Ved indgangen til iterationen galdt i > 1 (da iterationen fandt sted). Da i er et heltal pga. invariant ii), galdt faktisk i >=2. Så efter sidste iteration gælder derfor i >= 1, pga. algoritmens mulige handlinger under iterationen (if- og else-del). Da iterationen var den sidste, gælder samtidig i <= 1 (ellers ville en iteration mere have fundet sted). Dvs. at i = 1 efter den sidste iteration. Via invariant i) gælder floor(log(n)) = floor(log(i)) + k = floor(log(1)) + k = floor(0) + k = 0 + k = k. Da algoritmen returnerer k, er svaret korrekt. ** Spørgsmål d: I mindst hver anden iteration af while-løkken er i lige og bliver derfor halveret. Da i = n til start, er køretiden derfor O(log n). Omvendt giver hver iteration højst en halvering (eftersom i/2 <= i-1 for heltal i > 1 gælder dette også for else-delen), så køretiden er samtidig Omega(log n). Dermed er køretiden Theta(log n).