Werkblad Algoritmen & complexiteit met antwoorden

Wat is een brute-force-algoritme?

1. AEen algoritme dat altijd recursie gebruikt
2. BEen algoritme dat willekeurig een antwoord raadt
3. CEen algoritme dat op veel processoren draait
4. DEen algoritme dat alle mogelijke kandidaatoplossingen probeert

Wat zijn de drie stappen van een verdeel-en-heersalgoritme?

1. ALezen, berekenen, schrijven
2. BSorteren, zoeken, teruggeven
3. CVerdelen, oplossen (heersen), combineren
4. DRaden, controleren, herhalen

Welke complexiteitsklasse groeit het snelst voor grote n?

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

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

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

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 log n)
3. CO(n)
4. DO(n³)

Wat is de tijdcomplexiteit van het vermenigvuldigen van twee n × n-matrices met de standaard drievoudige lus?

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

Wat is het verschil tussen een onbeslisbaar en een onhandelbaar probleem?

1. AEen onbeslisbaar probleem heeft geen algoritme voor alle invoer; een onhandelbaar probleem wel, maar dat is te traag
2. BBeide betekenen dat het probleem helemaal geen algoritme heeft
3. COnbeslisbare problemen zitten in NP, terwijl onhandelbare problemen in P zitten
4. DOnhandelbare problemen kunnen door geen enkel algoritme worden opgelost, terwijl onbeslisbare alleen exponentiële tijd nodig hebben

Met het mastertheorema heeft T(n) = 8T(n/2) + O(n²) als oplossing:

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n log n)