Werkblad Algoritmen & complexiteit met antwoorden

Een O(n)-algoritme doet 3 seconden over n = 1 miljoen. Hoe lang doet het ongeveer over n = 2 miljoen?

1. A6 seconden
2. B9 seconden
3. C3 seconden
4. D12 seconden

Wat beschrijft de average-case looptijd?

1. ADe tijd op de meest gebruikte computer
2. BDe verwachte tijd over een gegeven verdeling van invoeren van grootte n
3. CDe middelste waarde tussen de looptijden in het beste en het slechtste geval
4. DDe tijd voor een invoer van gemiddelde lengte

Welke notatie beschrijft een bovengrens voor de groei?

1. AGrote O (Big O)
2. BGrote Omega (Big Omega)
3. CKleine omega (little omega)
4. DGrote Theta (Big Theta)

Quicksort gebruikt altijd het eerste element als pivot. Bij welke invoer vertoont het zijn worst-casegedrag?

1. AEen array waarvan alle elementen verschillend zijn
2. BEen array die al gesorteerd is
3. CEen array van lengte 2
4. DEen array in willekeurige volgorde

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)

Hoe bouwt het algoritme van Prim een minimale opspannende boom?

1. AHet laat één boom groeien vanaf een startknoop en voegt de goedkoopste kant toe die de boom verlaat
2. BHet voert breedte-eerst zoeken uit en houdt de BFS-boom over
3. CHet sorteert alle kanten op gewicht en voegt elke kant toe, tenzij die een cykel in het bos zou vormen
4. DHet verwijdert de duurste kant totdat er geen cykels meer zijn

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

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

Het algoritme van Strassen vermenigvuldigt matrices met 7 in plaats van 8 recursieve vermenigvuldigingen van blokken van halve grootte. Wat is de looptijd?

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n^{log₂ 7}), ongeveer n^2,81