Werkblad Algoritmen & complexiteit met antwoorden

Wat is memoisatie?

1. ARecursie automatisch omzetten in een equivalente lus, zodat geen call stack nodig is
2. BResultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
3. CGeheugen vrijgeven nadat een functie is teruggekeerd
4. DCommentaar schrijven naast elke regel code

Ruimtecomplexiteit meet:

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

Wat betekent het als een bewerking in O(1) tijd loopt?

1. AHet kan maar één keer worden uitgevoerd
2. BDe looptijd groeit niet met de invoergrootte
3. CHet verwerkt precies één element per seconde looptijd
4. DHet duurt altijd precies één seconde

Wat is de oplossing van de recurrente betrekking T(n) = 2T(n/2) + O(1)?

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

Waarom wordt het grondtal van een logaritme in grote-O-notatie meestal weggelaten, zoals in O(log n)?

1. AAlle logaritmen in de informatica hebben grondtal 10, dus het is impliciet
2. BLogaritmen met verschillende grondtallen verschillen alleen een constante factor
3. CHet grondtal doet er alleen toe voor kleine n
4. DLogaritmen worden altijd afgerond op gehele getallen

Wat is de oplossing van de recurrente betrekking T(n) = T(n/2) + O(1)?

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

Wat is de oplossing van de recurrente betrekking T(n) = 2T(n/2) + n log n?

1. AΘ(n log² n)
2. BΘ(n)
3. CΘ(n log n)
4. DΘ(n²)

Het 0/1-knapzakprobleem opgelost met dynamisch programmeren kost O(nW) tijd. Waarom heet dit pseudo-polynomiaal?

1. AOmdat n altijd klein is
2. BOmdat het alleen werkt voor W = 0
3. CW is een getal, dus de tijd is exponentieel in het aantal bits waarmee W wordt genoteerd
4. DOmdat het algoritme gerandomiseerd is en de looptijd per invoer verschilt