Werkblad Algoritmen & complexiteit met antwoorden

De looptijd van een algoritme is O(n). Hoe heet deze groei?

1. AKwadratisch
2. BLogaritmisch
3. CConstant
4. DLineair

Wat beschrijft de average-case looptijd?

1. ADe middelste waarde tussen de looptijden in het beste en het slechtste geval
2. BDe tijd op de meest gebruikte computer
3. CDe tijd voor een invoer van gemiddelde lengte
4. DDe verwachte tijd over een gegeven verdeling van invoeren van grootte n

Wat is memoisatie?

1. AGeheugen vrijgeven nadat een functie is teruggekeerd
2. BResultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
3. CRecursie automatisch omzetten in een equivalente lus, zodat geen call stack nodig is
4. DCommentaar schrijven naast elke regel code

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

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

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

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

Een gretig (greedy) algoritme:

1. AProbeert elke mogelijke oplossing
2. BGebruikt alleen recursie
3. CGeeft altijd de optimale oplossing
4. DMaakt bij elke stap de lokaal beste keuze

Waarom is een opzoeking in een hashtabel gemiddeld O(1) maar in het slechtste geval O(n)?

1. AVeel sleutels kunnen in dezelfde bucket botsen
2. BHashfuncties zijn traag
3. CSleutels moeten eerst gesorteerd worden
4. DArrays hebben O(n) toegang

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 is NP-moeilijk
2. BHet kan worden opgelost met het algoritme van Dijkstra met negatieve gewichten
3. CHet is onbeslisbaar
4. DHet is altijd oplosbaar in O(V + E)