Werkblad Algoritmen & complexiteit met antwoorden

Ruimtecomplexiteit meet:

1. ADe hoeveelheid geheugen die een algoritme nodig heeft naarmate de invoer groeit
2. BHet aantal regels code
3. CDe schijfruimte van het programmabestand nadat het is gecompileerd
4. DDe fysieke grootte van de computer

Welke notatie beschrijft een bovengrens voor de groei?

1. AKleine omega (little omega)
2. BGrote Theta (Big Theta)
3. CGrote Omega (Big Omega)
4. DGrote O (Big O)

Wat beschrijft de worst-case looptijd van een algoritme?

1. ADe maximale tijd die het nodig heeft over alle invoeren van grootte n
2. BDe tijd die het nodig heeft voor de kleinste invoer
3. CDe verwachte tijd die het nodig heeft voor een willekeurige invoer van grootte n
4. DDe tijd die het nodig heeft op een trage computer

Quicksort gebruikt altijd het eerste element als pivot. Bij welke invoer vertoont het zijn worst-casegedrag?

1. AEen array die al gesorteerd is
2. BEen array waarvan alle elementen verschillend zijn
3. CEen array in willekeurige volgorde
4. DEen array van lengte 2

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

1. ADynamisch programmeren werkt alleen op grafenproblemen, niet op arrays
2. BDe deelproblemen overlappen niet, dus er valt niets te hergebruiken
3. CMergesort is al O(n)
4. DMergesort heeft geen recursieve structuur

De recurrente betrekking T(n) = 2T(n/2) + O(n) heeft als oplossing:

1. AO(log n)
2. BO(n log n)
3. CO(n²)
4. DO(n)

Zit 2²ⁿ in O(2ⁿ)?

1. AJa, want beide zijn exponentieel
2. BJa, want constante factoren in de exponent worden in grote O altijd genegeerd
3. CNee, want 2²ⁿ groeit langzamer dan 2ⁿ
4. DNee, want 2²ⁿ = 4ⁿ en 4ⁿ / 2ⁿ = 2ⁿ groeit onbegrensd

Het algoritme van Held-Karp voor dynamisch programmeren lost het handelsreizigersprobleem exact op. Wat is de looptijd voor n steden?

1. AO(n³)
2. BO(n² 2ⁿ)
3. CO(2^n²)
4. DO(n!)