Werkblad Algoritmen & complexiteit met antwoorden

Wat is een brute-force-algoritme?

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

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

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

Welke van deze looptijden is polynomiaal?

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

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

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

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

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

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

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

Wat is de looptijd van het algoritme van Dijkstra met een binaire heap op een graaf met V knopen en E kanten?

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

Welke twee dingen moeten worden aangetoond om te bewijzen dat een beslissingsprobleem X NP-volledig is?

1. AX reduceert tot een probleem in P, en X zit in NP
2. BX zit in P, en X reduceert tot SAT
3. CX zit in NP, en een bekend NP-volledig probleem reduceert in polynomiale tijd tot X
4. DX heeft geen polynomiaal algoritme, en X is beslisbaar