Werkblad Algoritmen & complexiteit met antwoorden

Een probleem heet meestal handelbaar (tractable) als:

1. AHet in constante tijd kan worden opgelost
2. BHet alleen kan worden opgelost door elke mogelijkheid te proberen
3. CHet geen oplossing heeft
4. DHet in polynomiale tijd kan worden opgelost

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

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

Wat beschrijft de worst-case looptijd van een algoritme?

1. ADe maximale tijd die het nodig heeft over alle invoeren van grootte n
2. BDe verwachte tijd die het nodig heeft voor een willekeurige invoer van grootte n
3. CDe tijd die het nodig heeft op een trage computer
4. DDe tijd die het nodig heeft voor de kleinste invoer

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

1. AOverlappende deelproblemen en optimale substructuur
2. BEén enkele lus
3. CHelemaal geen deelproblemen, dus het kan in één stap worden opgelost
4. DAlleen willekeurige invoer

Wat is de geamortiseerde tijdcomplexiteit van een element toevoegen aan het einde van een dynamische array die zijn capaciteit verdubbelt als hij vol is?

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

Is het juist om te zeggen dat een O(n²)-algoritme ook O(n³) is?

1. ANee, omdat grote O altijd de exacte groeisnelheid van de functie moet geven
2. BNee, omdat n³ voor grote n kleiner is dan n²
3. CJa, maar alleen als n kleiner is dan 100
4. DJa, omdat grote O een bovengrens is en n² niet sneller groeit dan 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. BHet stopprobleem zou beslisbaar worden
3. CElk probleem in NP zou in polynomiale tijd kunnen worden opgelost, dus P = NP
4. DAlle algoritmen met exponentiële tijd zouden meteen in lineaire tijd lopen

Zit 2²ⁿ in O(2ⁿ)?

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