Werkblad Algoritmen & complexiteit met antwoorden

Hoeveel extra geheugen gebruikt een standaard mergesort op basis van arrays?

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

Welk sorteeralgoritme kiest een pivot en verdeelt de array in kleinere en grotere elementen?

1. AQuicksort
2. BMergesort
3. CInsertion sort
4. DBubblesort

Wat is de tijdcomplexiteit van diepte-eerst zoeken (DFS) in een graaf die als adjacentielijsten is opgeslagen?

1. AO(V²)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

Welke gulzige regel geeft bij het activiteitenselectieprobleem altijd een maximaal aantal niet-overlappende activiteiten?

1. AKies de activiteit die het vroegst eindigt en herhaal dat met de compatibele activiteiten
2. BKies eerst de kortste activiteit
3. CKies eerst de activiteit met de minste overlappingen en herhaal dat met de compatibele activiteiten
4. DKies de activiteit die het vroegst begint

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 is de oplossing van de recurrente betrekking T(n) = 2T(n − 1) + O(1)?

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

Welke uitspraak over het selecteren van het k-de kleinste element van een ongesorteerde array is juist?

1. AQuickselect loopt verwacht in O(n), en median-of-medians garandeert O(n) in het slechtste geval
2. BQuickselect loopt in het slechtste geval in O(log n), omdat het maar aan één kant van de pivot recursief verdergaat
3. CSelectie heeft altijd Ω(n log n) nodig, omdat er gesorteerd moet worden
4. DSelectie is alleen mogelijk in O(n²)

Wat zou er volgen als iemand een algoritme in polynomiale tijd vond voor één NP-volledig probleem?

1. AAlleen dat ene probleem zou naar P verhuizen
2. BAlle algoritmen met exponentiële tijd zouden meteen in lineaire tijd lopen
3. CHet stopprobleem zou beslisbaar worden
4. DElk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP