Werkblad Algoritmen & complexiteit met antwoorden

Een O(n²)-algoritme doet 1 seconde over n = 1000. Hoe lang doet het ongeveer over n = 2000?

1. A4 seconden
2. B1 seconde
3. C2 seconden
4. D8 seconden

Wat is de tijdcomplexiteit van diepte-eerst zoeken (DFS) in een graaf die als adjacentielijsten is opgeslagen?

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

Een O(n)-algoritme doet 3 seconden over n = 1 miljoen. Hoe lang doet het ongeveer over n = 2 miljoen?

1. A6 seconden
2. B12 seconden
3. C3 seconden
4. D9 seconden

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

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

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

1. AMergesort is al O(n)
2. BMergesort heeft geen recursieve structuur
3. CDynamisch programmeren werkt alleen op grafenproblemen, niet op arrays
4. DDe deelproblemen overlappen niet, dus er valt niets te hergebruiken

Wat is de tijdcomplexiteit van het standaardalgoritme voor dynamisch programmeren voor de langste gemeenschappelijke deelrij van strings met lengte m en n?

1. AO(m + n)
2. BO(mn)
3. CO(2^m+n)
4. DO(mn log n)

Topologisch sorteren is alleen mogelijk voor:

1. AGerichte acyclische grafen (DAG)
2. BVolledige grafen
3. COngerichte grafen
4. DGrafen met negatieve gewichten

Welke uitspraak over de kleine-o-notatie is juist?

1. An = o(n²), maar n is niet o(n)
2. B2n = o(n), omdat 2n langzaam groeit
3. Cn = o(n), omdat elke functie kleine o van zichzelf is
4. Dn² = o(n)