Werkblad Algoritmen & complexiteit met antwoorden

Wat is de tijdcomplexiteit van lineair zoeken in een ongesorteerde array van n elementen (worst case)?

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

Wat betekent het als een bewerking in O(1) tijd loopt?

1. AHet verwerkt precies één element per seconde looptijd
2. BDe looptijd groeit niet met de invoergrootte
3. CHet duurt altijd precies één seconde
4. DHet kan maar één keer worden uitgevoerd

Wat is de tijdcomplexiteit van binair zoeken in een gesorteerde array?

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

Breedte-eerst zoeken (BFS) op een ongewogen graaf vindt:

1. AEen topologische volgorde in alle grafen
2. BKortste paden in grafen met negatieve kantgewichten
3. CDe minimaal opspannende boom
4. DKortste paden in aantal kanten vanaf de startknoop

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

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

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

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

Het 0/1-knapzakprobleem opgelost met dynamisch programmeren kost O(nW) tijd. Waarom heet dit pseudo-polynomiaal?

1. AOmdat het alleen werkt voor W = 0
2. BOmdat het algoritme gerandomiseerd is en de looptijd per invoer verschilt
3. COmdat n altijd klein is
4. DW is een getal, dus de tijd is exponentieel in het aantal bits waarmee W wordt genoteerd

Met het mastertheorema heeft T(n) = 8T(n/2) + O(n²) als oplossing:

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n² log n)