Werkblad Algoritmen & complexiteit met antwoorden

Welke notatie beschrijft een bovengrens voor de groei?

1. AGrote Theta (Big Theta)
2. BGrote Omega (Big Omega)
3. CKleine omega (little omega)
4. DGrote O (Big O)

Een algoritme met twee geneste lussen die elk n keer worden doorlopen, heeft doorgaans welke complexiteit?

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

De looptijd van een algoritme is O(n). Hoe heet deze groei?

1. AConstant
2. BLogaritmisch
3. CLineair
4. DKwadratisch

Je sorteert een array van n elementen één keer en beantwoordt daarna k lidmaatschapsvragen met binair zoeken. Wat zijn de totale kosten?

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

Een gretig (greedy) algoritme:

1. AGebruikt alleen recursie
2. BGeeft altijd de optimale oplossing
3. CMaakt bij elke stap de lokaal beste keuze
4. DProbeert elke mogelijke oplossing

Waarom levert dynamisch programmeren geen echte versnelling op voor mergesort?

1. ADe deelproblemen overlappen niet, dus er valt niets te hergebruiken
2. BMergesort is al O(n)
3. CMergesort heeft geen recursieve structuur
4. DDynamisch programmeren werkt alleen op grafenproblemen, niet op arrays

Wat is het verschil tussen een onbeslisbaar en een onhandelbaar probleem?

1. AOnhandelbare problemen kunnen door geen enkel algoritme worden opgelost, terwijl onbeslisbare alleen exponentiële tijd nodig hebben
2. BBeide betekenen dat het probleem helemaal geen algoritme heeft
3. CEen onbeslisbaar probleem heeft geen algoritme voor alle invoer; een onhandelbaar probleem wel, maar dat is te traag
4. DOnbeslisbare problemen zitten in NP, terwijl onhandelbare problemen in P zitten

Het algoritme van Held-Karp voor dynamisch programmeren lost het handelsreizigersprobleem exact op. Wat is de looptijd voor n steden?

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