Spørgsmål 1
- Linear probing i dynamiske arrays
Antag vi ønsker at gemme en mængde af $n$ tal vha. hashing med
linear probing i et array af størrelse $N$. Vi garanterer at
arrayet altid er mellem 1/4 og 3/4 fyldt. Hvis der bliver færre
end $N/4$ eller flere end $3N/4$ tal i mængden genindsætter vi
alle tal i et nyt array af størrelse $2n$, dvs. det nye array er
1/2 fyldt. Angiv en potentiale funktion hvormed man kan vise at
det totalle antal genindsættelser i hashtabellerne er
amortiseret $O(1)$ per indsættelse og slettelse i mængden.
Spørgsmål 3
- Binære heaps i dynamiske arrays
Antag at en binær max-heap med $n$ elementer er gemt i de første $n$
indgange i et array af størrelsen $N$. Operationerne Insert
og Extract-Max implementeres som for en standard binær
max-heap, på nær Insert når $n=N$, hvor heapen først kopieres over
i et nyt array af dobbelt størrelse $2N$, dvs. $N$ fordobles, hvorefter
Insert operationen udføres som for en standard binær max-heap.
Angiv en potentialefunktion hvormed man kan argumentere for at
Insert tager amortiseret $O(\log n)$ tid og Extract-Max
tager amortiseret $O(1)$ tid.
Spørgsmål 4
- Binære tællere i dynamiske arrays
Betragt et array $A[0..N-1]$ af længde $N$, hvor hver
indgang er enten 0 eller 1. $A$ opfattes som et binært tal med værdien
$n$, hvor $n=\sum_{i=0}^{N-1} 2^i\cdot A[i]$. Operationen
Inc$(A)$ øger værdien af $n$ med 1 ved at flippe
$A[0],A[1],...$ indtil det første $A[i]$ flippes fra 0 til 1. Hvis
alle indgange i $A$ indeholdt 1 (dvs. $n=2^N-1$ før
Inc$(A)$ udføres), så kopieres $A$ over i nyt array af
dobbelt størrelse $2N$, hvor alle $A[i]=0$ bort set fra $A[N]=1$.
Angiv en potentialefunktion kan man argumentere for at Inc
tager amortiseret $O(1)$ tid. I nedenstående betegner $k$ antal
$A[i]=1$, dvs. $k=|\{ i \mid A[i]=1\}|$.