Werkblad Algoritmen & complexiteit met antwoorden

Welke hiervan groeit het langzaamst als n groot wordt?

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

Wat vereist binair zoeken van de invoer?

1. ADe array moet gesorteerd zijn
2. BDe lengte van de array moet een macht van twee zijn
3. CDe array mag alleen positieve getallen bevatten
4. DDe array mag niet meer dan 1000 elementen hebben

Een lus begint met i = 1 en verdubbelt i bij elke iteratie totdat i > n. Hoeveel iteraties voert hij uit?

1. AOngeveer n / 2
2. BOngeveer log₂ n
3. COngeveer n
4. DOngeveer n²

Welk sorteeralgoritme is stabiel?

1. AQuicksort (gangbare in-place-versie)
2. BMergesort
3. CHeapsort
4. DSelectionsort (gangbare versie)

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

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

Wat is de tijdcomplexiteit van: for i = 1 to n: for j = 1 to i: doe O(1) werk?

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

Welke twee dingen moeten worden aangetoond om te bewijzen dat een beslissingsprobleem X NP-volledig is?

1. AX zit in P, en X reduceert tot SAT
2. BX zit in NP, en een bekend NP-volledig probleem reduceert in polynomiale tijd tot X
3. CX reduceert tot een probleem in P, en X zit in NP
4. DX heeft geen polynomiaal algoritme, en X is beslisbaar

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. BAantonen dat X geen polynomiaal algoritme heeft voor kleine invoer
3. CX in polynomiale tijd reduceren tot een bekend NP-moeilijk probleem
4. DAantonen dat X in polynomiale tijd kan worden geverifieerd