Werkblad Algoritmen & complexiteit met antwoorden

Welke notatie beschrijft een bovengrens voor de groei?

1. AGrote Theta (Big Theta)
2. BGrote O (Big O)
3. CGrote Omega (Big Omega)
4. DKleine omega (little omega)

Wat beschrijft de worst-case looptijd van een algoritme?

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

Welke van deze looptijden is polynomiaal?

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

Welke uitspraak over een recursieve functie zonder bereikbaar basisgeval is juist?

1. ADe compiler maakt er altijd een lus van die veilig eindigt
2. BZe loopt in O(1) tijd
3. CZe blijft zichzelf aanroepen totdat de call stack overloopt
4. DZe geeft automatisch 0 terug

Welk algoritme vindt de kortste paden vanuit één bron in een graaf met niet-negatieve kantgewichten?

1. ADiepte-eerst zoeken (DFS)
2. BHet algoritme van Kruskal
3. CBellman-Ford is in alle gevallen vereist
4. DHet algoritme van Dijkstra

De tijdcomplexiteit van naïef recursief Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

1. ALineair
2. BConstant
3. CExponentieel
4. DLogaritmisch

Welke twee dingen moeten worden aangetoond om te bewijzen dat een beslissingsprobleem X NP-volledig is?

1. AX zit in NP, en een bekend NP-volledig probleem reduceert in polynomiale tijd tot X
2. BX heeft geen polynomiaal algoritme, en X is beslisbaar
3. CX reduceert tot een probleem in P, en X zit in NP
4. DX zit in P, en X reduceert tot SAT

Wat zijn de tijd- en ruimtekosten van het berekenen van het n-de Fibonaccigetal met een lus die alleen de laatste twee waarden bewaart?

1. AO(2ⁿ) tijd en O(1) ruimte
2. BO(log n) tijd en O(n) ruimte
3. CO(n) tijd en O(n) ruimte
4. DO(n) tijd en O(1) ruimte