Werkblad Algoritmen & complexiteit met antwoorden

Hoe heet groei van O(2ⁿ)?

1. APolynomiaal
2. BExponentieel
3. CLineair
4. DLogaritmisch

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 tijd voor een invoer van gemiddelde lengte
4. DDe middelste waarde tussen de looptijden in het beste en het slechtste geval

Welke ontwerpstrategie gebruikt mergesort?

1. AGulzige keuze (greedy)
2. BBrute kracht
3. CVerdeel en heers
4. DDynamisch programmeren

Wat meet geamortiseerde analyse?

1. ADe verwachte kosten over willekeurige invoer
2. BDe gemiddelde kosten per bewerking over een worst-casereeks van bewerkingen
3. CDe kosten van de ene duurste bewerking ergens in de reeks
4. DDe kosten van een algoritme bij de beste invoer

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

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

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

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

Zit 2²ⁿ in O(2ⁿ)?

1. ANee, want 2²ⁿ = 4ⁿ en 4ⁿ / 2ⁿ = 2ⁿ groeit onbegrensd
2. BJa, want beide zijn exponentieel
3. CNee, want 2²ⁿ groeit langzamer dan 2ⁿ
4. DJa, want constante factoren in de exponent worden in grote O altijd genegeerd

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

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