Opgave 1 *********************************************************** ** Spørgsmål a: i) Kan løses (med Case I). ii) Kan løses (med Case II) iii) Kan ikke løses (falder mellem Case 2 og 3). iv) Kan løses (med Case III). ** Spørgsmål b: i) T(n) = Theta(n). ii) T(n) = Theta(n log n) iv) T(n) = Theta(n^2). Opgave 2 *********************************************************** i) Sand ii) Sand iii) Sand iv) Falsk v) Sand vi) Sand vii) Falsk viii) Falsk ix) Sand x) Falsk Opgave 3 *********************************************************** Efter Build-Max-Heap: 9 8 7 4 2 6 5 1 3 Opgave 4 *********************************************************** Efter insert af 18: 67 20 17 x 33 x 16 2 x 18 15 Efter insert af 22: 67 20 17 26 33 x 16 2 x 18 15 Opgave 5 *********************************************************** Ét muligt svar (mange andre gyldige svar kan fås ved at rotere børn af en eller flere knuder i træet - dette ændrer ikke kodelængder og dermed ikke samlet antal bits): x: 01 y: 0000 z: 10 æ: 11 ø: 0001 å: 001 Samlet antal bits: 8000 Opgave 6 *********************************************************** ** Spørgsmål a: Knuder v ud af kø: a b c e d f g h i j Værdier af v.d: 0 1 2 2 3 3 4 4 5 6 ** Spørgsmål b: Knude v: a b c d e f g h i j v.d/v.f: 1/20 2/19 3/18 4/17 9/10 7/12 5/16 8/11 6/15 13/14 ** Spørgsmål c: Knuder v ud af PQ: a b e c d g i f j h Værdier af v.d: 0 6 14 15 17 22 26 29 38 39 ** Spørgsmål d: MST: (a,b), (b,c), (b,e), (c,d), (d,g), (f,i), (g,i), (h,j), (i,j) Opgave 7 *********************************************************** ** Spørgsmål a: 5 træer ** Spørgsmål b: 6 træer ** Spørgsmål c: 5 træer ** Spørgsmål d: 1 træ Opgave 8 *********************************************************** i) Er ikke en invariant ii) Er ikke en invariant iii) Er ikke en invariant iv) Er en invariant v) Er en invariant Opgave 9 *********************************************************** Algoritme1: Theta(n^2) Algoritme2: Theta(log n) Algoritme3: Theta(1) Algoritme4: Theta(n) Opgave 10 ********************************************************** ** Spørgsmål a: K(19) = 3 19 = 3^2 + 3^2 + 1^2 ** Spørgsmål b: MinimumSumOfSquares(n) create new array K of size n+1 K[0] = 0 for (i=1;i<=n;i++) minimum = infinity for(a=1;a^2<=i,a++) if K(i-a^2) < minimum minimum = K(i-a^2) K[i] = 1 + minimum return K[n] Detalje: Eftersom n altid kan skrives 1^2 + 1^2 + ... + 1^2 (n led) gælder K(n) <= n for alle n. Derfor kan vi bruge værdien n+1 på "infinity"'s plads ovenfor. For hver af de n pladser i array K bruges højst n^0.5 iterationer i det indre loop, hvilket i alt er O(n^1.5) tid. Omvendt, for hver af de sidste n/2 pladser bruges mindst (n/2)^0.5 > n^0.5/2 iterationer i det indre loop, hvilket i alt er Omega(n^1.5). Alt i alt er svaret: Theta(n^1.5) tid og Theta(n) plads. ** Spørgsmål c: Under udfyldelse af K[i], husk den værdi af a i det indre loop som gav minimum's værdi. Nu kan løsningen udskrives via backtracking. I større detalje: MinimumSumOfSquaresPrintSolution(n) create new array K of size n+1 create new array A of size n+1 K[0] = 0 for (i=1;i<=n;i++) minimum = infinity for(a=1;a^2<=i,a++) if K(i-a^2) < minimum minimum = K(i-a^2) aMin = a K[i] = 1 + minimum A[i] = aMin i = n while i > 0 print A[i] i = i - A[i]^2 ** Spørgsmål d: Hvis n = 0, er n lig summen af ingen kvadrater, og dette er optimalt (færrest mulige led). Så K(0) er lig 0. For n >=1 ser vi på en optimal opskrivning (færrest mulige led) af n som en sum af kvadrater, n = (a_1)^2 + (a_2)^2 + ... (a_k)^2. Da n >= 1 er k >=1 og der gælder 1 <= (a_1)^2 <= n. Resten af opskrivningen (a_2)^2 + ... (a_k)^2 må være optimal for n' = n-(a_1)^2, for hvis der fandtes en opskrivning for n' med færre led end k-1, ville man kunne finde en for n med færre led end k. Så k = K(n) må være lig 1 + K(n-(a_1)^2). For alle heltal a med 1 <= a^2 <= n findes en opskrivning af n som 1 + K(n-a^2) kvadrater (nemlig som a^2 plus en opskrivning af n-a^2 som en sum af K(n-a^2) kvadrater). Blandt disse må være en af længden k (nemlig når a = a_1), og ingen af de andre kan være bedre (da k er det optimale antal led for n). Derfor er K(n) = 1 + min {K(n-a^2) | a heltal hvor 1 <= a^2 <= n}.