Werkblad Algoritmen & complexiteit met antwoorden

Wat is de looptijd van counting sort voor n gehele getallen in het bereik 0 tot k?

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

Wat is een brute-force-algoritme?

1. AEen algoritme dat willekeurig een antwoord raadt
2. BEen algoritme dat altijd recursie gebruikt
3. CEen algoritme dat op veel processoren draait
4. DEen algoritme dat alle mogelijke kandidaatoplossingen probeert

Wat is het basisgeval van een recursieve functie?

1. AHet geval met de grootste invoer, dat vóór alle recursieve aanroepen wordt afgehandeld
2. BEen geval dat direct wordt beantwoord zonder nog een recursieve aanroep
3. CDe eerste regel van de functie
4. DDe aanroep die het meeste geheugen gebruikt

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(mn)
3. CO(mn log n)
4. DO(m + n)

Wat is de tijdcomplexiteit van het algoritme van Bellman-Ford op een graaf met V knopen en E kanten?

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

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

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

Karatsuba-vermenigvuldiging voldoet aan T(n) = 3T(n/2) + O(n). Wat is de oplossing?

1. AΘ(n³)
2. BΘ(n^{log₂ 3}), ongeveer n^1,585
3. CΘ(n log n)
4. DΘ(n²)

Hoe wordt het handelsreizigersprobleem geclassificeerd?

1. AHet zit in P, omdat het algoritme van Dijkstra het oplost door elke stad één keer te bezoeken
2. BDe beslissingsversie is NP-volledig en de optimalisatieversie is NP-moeilijk
3. CHet is onbeslisbaar
4. DDe beslissingsversie zit in P, maar de optimalisatieversie is NP-volledig