Werkblad Algoritmen & complexiteit met antwoorden

Wat is de worst-case tijdcomplexiteit van insertion sort?

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

Een element in een array via de index benaderen kost:

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

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

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

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

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

Een gretig (greedy) algoritme:

1. AGebruikt alleen recursie
2. BProbeert elke mogelijke oplossing
3. CGeeft altijd de optimale oplossing
4. DMaakt bij elke stap de lokaal beste keuze

Welke gulzige regel geeft bij het activiteitenselectieprobleem altijd een maximaal aantal niet-overlappende activiteiten?

1. AKies eerst de activiteit met de minste overlappingen en herhaal dat met de compatibele activiteiten
2. BKies de activiteit die het vroegst eindigt en herhaal dat met de compatibele activiteiten
3. CKies eerst de kortste activiteit
4. DKies de activiteit die het vroegst begint

Een probleem is NP-volledig als het:

1. AOnmogelijk op te lossen is
2. BBuiten NP valt maar moeilijker is dan alle NP-problemen, zoals het stopprobleem
3. CIn NP zit en elk NP-probleem er in polynomiale tijd naar te reduceren is
4. DIn polynomiale tijd oplosbaar is

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