Werkblad Algoritmen & complexiteit met antwoorden

Hoe heet groei van O(2ⁿ)?

1. ALineair
2. BPolynomiaal
3. CLogaritmisch
4. DExponentieel

Wat is log₂ 1024?

1. A32
2. B512
3. C10
4. D12

Wat is een brute-force-algoritme?

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

Een gretig (greedy) algoritme:

1. AGeeft altijd de optimale oplossing
2. BMaakt bij elke stap de lokaal beste keuze
3. CGebruikt alleen recursie
4. DProbeert elke mogelijke oplossing

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

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

Je sorteert een array van n elementen één keer en beantwoordt daarna k lidmaatschapsvragen met binair zoeken. Wat zijn de totale kosten?

1. AO(n + k)
2. BO(k n log n)
3. CO(n log n + k log n)
4. DO(nk)

Insertion sort loopt in O(n) op gesorteerde invoer. Is dit in tegenspraak met de ondergrens Ω(n log n) voor sorteren met vergelijkingen?

1. AJa, maar alleen voor arrays korter dan 100
2. BJa, de ondergrens is dus fout
3. CNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
4. DNee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is

Kortste enkelvoudige paden kunnen in polynomiale tijd worden gevonden. Wat is bekend over het vinden van het langste enkelvoudige pad tussen twee knopen in een algemene graaf?

1. AHet kan worden opgelost met het algoritme van Dijkstra met negatieve gewichten
2. BHet is NP-moeilijk
3. CHet is altijd oplosbaar in O(V + E)
4. DHet is onbeslisbaar