Werkblad Algoritmen & complexiteit met antwoorden

Welk sorteeralgoritme verwisselt herhaaldelijk naast elkaar liggende elementen die in de verkeerde volgorde staan?

1. AHeapsort
2. BMergesort
3. CQuicksort
4. DBubblesort

Wat is memoisatie?

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

Hoe heet groei van O(2ⁿ)?

1. AExponentieel
2. BLineair
3. CLogaritmisch
4. DPolynomiaal

In een gesorteerde array zoek je twee elementen die samen een doelwaarde opleveren door vanaf elk uiteinde een pointer naar binnen te bewegen. Wat is de tijdcomplexiteit?

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

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

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

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)

Wat moet je doen om aan te tonen dat een nieuw probleem X NP-moeilijk is?

1. AEen bekend NP-moeilijk probleem in polynomiale tijd reduceren tot X
2. BX in polynomiale tijd reduceren tot een bekend NP-moeilijk probleem
3. CAantonen dat X in polynomiale tijd kan worden geverifieerd
4. DAantonen dat X geen polynomiaal algoritme heeft voor kleine invoer

Welke definitie van de klasse NP is juist?

1. ABeslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd
2. BProblemen die geen enkel algoritme kan oplossen
3. CProblemen die niet in polynomiale tijd kunnen worden opgelost
4. DProblemen die niet polynomiaal zijn