Werkblad Algoritmen & complexiteit met antwoorden

Wat is de best-case tijdcomplexiteit van insertion sort op een al gesorteerde array?

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

Wat is memoisatie?

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

Wat is de worst-case tijdcomplexiteit van mergesort?

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

Breedte-eerst zoeken (BFS) op een ongewogen graaf vindt:

1. AKortste paden in aantal kanten vanaf de startknoop
2. BKortste paden in grafen met negatieve kantgewichten
3. CEen topologische volgorde in alle grafen
4. DDe minimaal opspannende boom

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

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

Wat berekent het algoritme van Floyd-Warshall, en hoe snel?

1. AEen minimale opspannende boom in O(E log V)
2. BEen topologische ordening in O(V²)
3. CKortste paden tussen alle paren knopen in O(V³)
4. DKortste paden vanuit één bronknoop naar alle andere in O(V + E)

Het stopprobleem (halting problem) laat zien dat:

1. ALussen vermeden moeten worden
2. BElk programma uiteindelijk stopt
3. CSommige programma's sneller draaien op snellere computers, dus stoppen hangt van de hardware af
4. DGeen enkel algoritme voor elk programma en elke invoer kan beslissen of het stopt

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

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