Werkblad Algoritmen & complexiteit met antwoorden

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

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

Wat zijn de drie stappen van een verdeel-en-heersalgoritme?

1. ARaden, controleren, herhalen
2. BVerdelen, oplossen (heersen), combineren
3. CLezen, berekenen, schrijven
4. DSorteren, zoeken, teruggeven

Welke complexiteitsklasse groeit het snelst voor grote n?

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

Wat is de tijdcomplexiteit van het berekenen van het n-de Fibonaccigetal met een bottom-uptabel?

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

Dynamisch programmeren is nuttig wanneer een probleem het volgende heeft:

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

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

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

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

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

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 reduceert tot een probleem in P, en X zit in NP
3. CX zit in P, en X reduceert tot SAT
4. DX heeft geen polynomiaal algoritme, en X is beslisbaar