Oppgave 1

Se Oppgave 538-1.pdf.

Oppgave 2

Formel	n = 15	n = 31	n = 63	n = 127
(n + 1) log2(n + 1) − 2n	34	98	258	642
2 [n − log2(n + 1)]	22	52	114	240

Oppgave 3

En vil finne at den første versjonen har i gjennomsnitt ca. 20% flere sammenligninger enn den andre versjonen.

  int n = 100000;

  int[] a = Tabell.randPerm(n);
  int[] b = a.clone();

  System.out.println(opptelling1(a));
  System.out.println(opptelling2(b));

Oppgave 4

Det blir 1!·2!·4!·8! = 1·2·24·40320 = 1935360. For alle disse vil den andre versjonen av lagMaksimumsheap gi 22 sammenligninger. Men for den første versjonen vil det variere. F.eks. vil a = {1,3,2,7,6,5,4,15,14,13,12,11,10,9,8} gi 26 sammenligninger.

Oppgave 5

Hvis opptelling2 skal gi 14 som resultat, må tallet 15 ligge i rotnoden. Videre må de to subtrærne gi så få sammenligninger som mulig. Det får en til hvis 1) rotnoden i det venstre subtreet har en verdi som er større enn de øvrige verdiene i subtreet og 2) at det er på samme måte i det høyre subtreet.

La k være verdien i venstre barn til roten (dvs. rotnoden i det venstre subtreet). Da kan k være fra 7 til 14. De k−1 verdiene som er mindre enn k, kan velges på B(k−1,6) (binomialkoeffisienten) måter. Disse verdiene kan så permuteres på 6! (fakultet) måter. Resten av verdiene (7 verdier) må ligge i det høyre subtreet. Den største blant dem må ligge i subtreets rotnode. De 6 øvrige kan permuteres på 6! måter. Dermed blir det 6!·6!·B(k−1,6) forskjellige permutasjoner av tallene fra 1 til 15 som har k som verdi i rotens venstre barn og som gir 14 som resultat for opptelling2.

Vi finner det totale antallet ved å summere dette fra k = 7 til 14. Da trenger vi binomialkoeffisientene. Vi har B(6,6) = 1, B(7,6) = 7, B(8,6) = 28, osv. til B(13,6) = 1716. Summerer vi disse får vi 3432. Svaret blir derfor

6!·6!·3432 = 720·720·3432 = 1.779.148.800

Dette ser stort ut, men husk at det totalt er 15! = 1.307.674.368.000 permutasjoner.

Oppgave 6

a = {15,7,8,6,5,9,10,4,3,2,1,11,12,13,14} gir 16, a = {15,1,8,2,3,9,10,4,5,6,7,11,12,13,14} gir 18 og a = {14,1,8,2,3,9,10,4,5,6,7,11,12,13,15} gir 20.

Oppgave 7

Her kan det være lurt å kalle den første versjonen for lagMaksimumsheap1 og den andre for lagMaksimumsheap2. Da koden under ble kjørt en del ganger så det ut som at den andre versjonen kanskje var ca. 30% raskere enn den første.

  int n = 100_000_000;
  int[] a = Tabell.randPerm(n);

  long tid = System.currentTimeMillis();
  lagMaksimumsheap(a);
  tid = System.currentTimeMillis() - tid;

  System.out.println(tid);