Uitwerking 1ste tentamen.
Mon Jun 30 20:49:38 CEST 2008

1a. Een functie f(n) is O(g(n)) als er een constante c en n0 gevonden kan
worden zodanig dat c * g(n) + n0 groter is dan f(n), voor alle n.
b. Voor c=2 en n0=1 zal gelden dat f(n) altijd kleiner is dan 2*n log n + 1.
c.
Als f(n) en g(n) allebei O(h(n)) zijn, dan betekent dat dat er constantes c_f,
c_g, n0_f, en n0_g zijn, zodat c*h(n)+n0 groter is dan f en g, voor alle n.

f(n)+g(n) zal ook onder O(h(n)) vallen, omdat de gezochte constanten c en n0
berekend kunnen worden uit die van f(n) en g(n) afzonderlijk. Zodoende zal c
gelijk zijn aan c_f * c_g, en n0 gelijk zijn aan n0_f + n0_g

2a.
s=0
s=01
q=0
q=10
s=0
s=01
q=1
q=11

Uiteindelijk: s=01 (top als laatste) q=11 (front als eerste)

b.

#given a string of characters, determine if it constitutes a palindrome
for a=1 to input.length divided by two (int division)
	stack.push character at a
if input.length and 1 (odd)
	a=a+1
for b=a to input.length
	if NOT character at a equals stack.pop
		return FALSE
return TRUE

3a. De maximum hoogte van een boom is O(n), in het gedegenereerde geval dat de
boom een linked list wordt.
De minimum hoogte is O(log n), in het optimale geval dat de boom perfect
gebalanceerd is.
Deze ruimte complexiteiten zijn ook de tijdscomplexiteiten voor insert, delete
en find. Dat wil zeggen, een optimaal gebalanceerde boom geeft ook optimale
tijden voor operaties.

b.
na insert(11)
       5
   3       8
     4   6   10
            9  13
              11

na delete(5)
       6
   3       8
     4       10
            9  13
              11

na insert(5)
       6
   3       8
     4       10
       5    9  13
              11
       
na insert(12)
        6
   3       8
     4       10
       5    9  13
              11
               12
c
         5(4)
   3(2)         8(3)
     4(1)   6(1)    10(2)
                  9(1)  13(1)

Dit betekent dat dit inderdaad een AVL boom is, geen van de nodes heeft
kinderen met hoogtebalansen met een verschil van meer dan 1.

d

na insert(11)
       5
   3       8
     4   6    13
            10  11
           9        

na delete(5)
       6
   3       8
     4       10
            9  13
              11

na insert(5)
       6
   3       8
     4       10
       5    9  13
              11
       
na insert(12)
        6
   3       8
     4       10
       5    9  13
              11
               12

e. Het voordeel van een AVL boom is dat hij altijd gebalanceerd zal zijn, en
dus altijd asymptotisch optimaal zal zijn. De zoek en update operaties zullen
snel zijn. Bij een normale binaire zoekboom zijn er niet zulke garanties, in
het slechtse geval (gesorteerde data), zal de boom zeer langzaam zijn.



4a. Een heap is een binaire boom waarbij elke node (behalve de root) aan de
heap-property voldoet:
    - Een node is groter dan of gelijk aan zijn parent. (Of omgekeerd, klijner
      dan of gelijk aan).
b. 
          1
     2        5
   8   25   19  20
 23 18

c. Na insert(6)
          1
     2        5
   8    6   19  20
 23 18 25

d.
We overschrijven de root met de waarde van de tail, en daarna bubbelen we deze
naar beneden.  Eerst verwisselen we met 2, dan met 6. De boom voldoet nu weer
aan de heap property:

          2
     6         5
   8    25   19  20
 23 18

5.