Werkblad Algoritmen & complexiteit met antwoorden

Een algoritme met twee geneste lussen die elk n keer worden doorlopen, heeft doorgaans welke complexiteit?

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

Wat is een brute-force-algoritme?

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

Welke complexiteitsklasse groeit het snelst voor grote n?

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

Wat is de tijdcomplexiteit van het algoritme van Bellman-Ford op een graaf met V knopen en E kanten?

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

Hoeveel stackruimte gebruikt een eenvoudige recursieve faculteitsfunctie fact(n) = n × fact(n − 1)?

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

Wat betekent het dat een probleem een optimale deelstructuur heeft?

1. AHet probleem kan in constante tijd worden opgelost
2. BHet probleem heeft precies één optimale oplossing, die alle deelproblemen delen
3. CElk deelprobleem heeft dezelfde grootte
4. DEen optimale oplossing kan worden opgebouwd uit optimale oplossingen van de deelproblemen

Een probleem is NP-volledig als het:

1. AIn NP zit en elk NP-probleem er in polynomiale tijd naar te reduceren is
2. BBuiten NP valt maar moeilijker is dan alle NP-problemen, zoals het stopprobleem
3. CIn polynomiale tijd oplosbaar is
4. DOnmogelijk op te lossen is

Welke definitie van de klasse NP is juist?

1. AProblemen die niet polynomiaal zijn
2. BProblemen die geen enkel algoritme kan oplossen
3. CBeslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd
4. DProblemen die niet in polynomiale tijd kunnen worden opgelost