Opgave 1 *********************************************************** ** Spørgsmål a: i) Kan løses (med Case I). ii) Kan ikke løses (falder mellem Case 2 og 3). iii) Kan løses (med Case III). iv) Kan ikke løses (forkert form på rekursionsligning). ** Spørgsmål b: i) T(n) = Theta(n^a) med a = log_2(5) = 2.321.. . iii) T(n) = Theta(n^0.5). Opgave 2 *********************************************************** i) Falsk ii) Sand iii) Sand iv) Falsk v) Falsk vi) Falsk vii) Sand viii) Sand ix) Sand Opgave 3 *********************************************************** Efter IncreaseKey: 18 15 16 9 8 12 13 1 4 Efter ExtractMax: 16 15 13 9 8 12 4 1 Opgave 4 *********************************************************** Efter insert af 22: 13 39 x 36 x 22 x x 23 5 x Efter insert af 16: 13 39 16 36 x 22 x x 23 5 x Efter insert af 17: 13 39 16 36 x 22 x 17 23 5 x Opgave 5 *********************************************************** Knuder ud af prioritetskø: a, d, e, c, b Kanter i MST: (a,d), (a,e), (e,c), (e,b) Opgave 6 *********************************************************** ** Spørgsmål a: Knude v: a b c d e f g h i v.d/v.f: 3/4 2/7 5/6 8/9 12/13 11/14 10/17 15/16 1/18 ** Spørgsmål b: Tree edges: (b,i), (a,b), (b,c), (d,i), (g,i), (f,g), (e,f), (g,h) Back edges (a,i), (c,i), (e,i), (f,i) Forward edges: (h,i) Cross edges: (c,d), (d,e), (a,h) Opgave 7 *********************************************************** ** Spørgsmål a: D BF DAG BFS DFS G_1: x x x G_2: x x G_3: x ** Spørgsmål b: D: O(n (log n)^2) BF: O(n^2 log n) DAG: O(n log n) Opgave 8 *********************************************************** ** Spørgsmål a: Sorte: a, b, c, e Røde: d ELLER Sorte: a, b, d Røde: c, e ** Spørgsmål b: T_3 Opgave 9 *********************************************************** Algoritme1: Theta(n^2) Algoritme2: Theta(n) Algoritme3: Theta(n) Algoritme4: Theta(n log n) Opgave 10*********************************************************** ** Spørgsmål a: Lad en knude v have højre barn v.right og venstre barn v.left, begge forskellige fra NIL. Informationen i v kan da findes således: v.xmax = v.right.xmax v.xmin = v.left.xmin v.ymax = max(v.left.ymax, v.right.ymax, v.y) v.ymin = min(v.left.ymin, v.right.ymin, v.y) hvor v.y er den i knuden gemte y-koordinat. ** Spørgsmål b: Dette følger af spørgsmål a, Sætning 14.1 (side 346) i lærebogen, samt antagelsen om at ingen x-koordinat optræder i mere end eet punkt. Uden antagelsen ville de søgenøgler, vi anvender, ikke være unikke for punkterne. Sletningen af punktet (5,100) i en samling punkter (5,1), (5,2), (5,3),.... ville f.eks. ikke kunne gennemføres i O(log n) tid. ** Spørgsmål c: Dette areal kan findes som (r.xmax - r.xmin)*(r.ymax - r.ymin), hvor r er roden i træet. Denne beregning tager O(1) tid ud fra informationen gemt i roden. ** Spørgsmål d: At finde punkterne på de lodrette sider er blot kald til Tree-Maximum(r) og Tree-Minimum(r) (side 291 i lærebogen). Disse bruger O(h) tid, hvor h er højden af træet, og for rød-sorte træer gælder h = O(log n). Punktet på den øverste, vandrette side kan findes ved en rekursiv søgealgoritme, der starter i roden, og som for en besøgt knude v med begge børn forskellige fra NIL undersøger om v.ymax er lig v.y, v.left.ymax eller v.right.ymax (den bliver nødt til at være lig én af dem). I det første tilfælde returneres punktet gemt i v. I det andet tilfælde kaldes rekursivt på v.left, i det tredie på v.right. Hvis et eller begge af børnene er NIL, undlades testen for de pågældende børn. Køretiden er O(h), som er O(log n). Punktet på den nederste, vandrette side kan findes på samme måde, med ymin i stedet for ymax. ** Spørgsmål e: Man kan i stedet for gemme alle punkter i to rød-sorte træer, et som bruger x-koordinater som søgenøgler, og et som bruger y-koordinater som søgenøgler. Under vores antagelser er de brugte søgenøgler i begge træer unikke for punkterne, så træerne kan vedligeholdes på normal vis (inklusive sletninger), med operationer i O(log n) tid. Ved indsættelse og sletning af et punkt skal dette ske i begge træer. For at finde punkter på de fire sider af rektanglet i O(log n) tid skal man blot kalde Tree-Maximum() og Tree-Minimum() på hvert af træernes rod. For at finde arealet af rektanglet i O(1) tid, skal man for hvert træ blot huske største og mindste nøgle i hele træet (dvs. ikke længere information i alle knuder). Denne information kan vedligeholdes under updates (indsættelser/sletninger) ved at kalde Tree-Maximum() og Tree-Minimum() på begge træer hver update. Dette ændrer ikke køretiden O(log n) for en update.