Werkblad Algoritmen & complexiteit met antwoorden

Wat beschrijft de worst-case looptijd van een algoritme?

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

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

1. A1 seconde
2. B8 seconden
3. C4 seconden
4. D2 seconden

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

1. ALogaritmisch
2. BLineair
3. CKwadratisch
4. DConstant

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

1. AOverlappende deelproblemen en optimale substructuur
2. BEén enkele lus
3. CAlleen willekeurige invoer
4. DHelemaal geen deelproblemen, dus het kan in één stap worden opgelost

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

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

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

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

Waarom geeft binair zoeken op een enkelvoudig gelinkte lijst geen O(log n) tijd?

1. AVergelijkingen op knopen van een gelinkte lijst zijn trager
2. BGelinkte lijsten kunnen niet worden gesorteerd
3. CBinair zoeken heeft minstens twee keer zoveel geheugen nodig
4. DHet middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is

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, de ondergrens is dus fout
2. BNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer
3. CNee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is
4. DJa, maar alleen voor arrays korter dan 100