Werkblad Algoritmen & complexiteit met antwoorden

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

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

Wat is de best-case tijdcomplexiteit van insertion sort op een al gesorteerde array?

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

Hoe heet groei van O(2ⁿ)?

1. ALineair
2. BLogaritmisch
3. CExponentieel
4. DPolynomiaal

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

Waarom schakelen veel sorteerroutines in bibliotheken over op insertion sort voor heel kleine deelarrays?

1. ARecursieve algoritmen kunnen geen arrays van minder dan 10 elementen aan
2. BInsertion sort heeft weinig overhead en is snel op kleine of bijna gesorteerde invoer
3. CInsertion sort is in het slechtste geval O(n log n)
4. DInsertion sort gebruikt voor grote invoer minder geheugen dan elk ander sorteeralgoritme

De ondergrens voor sorteren op basis van vergelijkingen in het slechtste geval is:

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

Welke definitie van de klasse NP is juist?

1. AProblemen die geen enkel algoritme kan oplossen
2. BProblemen die niet in polynomiale tijd kunnen worden opgelost
3. CProblemen die niet polynomiaal zijn
4. DBeslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd

Hoe detecteert het algoritme van Bellman-Ford een cykel met negatief gewicht die vanuit de bron bereikbaar is?

1. AHet voert het algoritme van Dijkstra twee keer uit en vergelijkt de twee afstandsresultaten
2. BHet controleert of er een kant met negatief gewicht is
3. CHet telt de cykels met diepte-eerst zoeken
4. DNa V − 1 rondes controleert het of er nog een kant kan worden gerelaxeerd