Werkblad Algoritmen & complexiteit met antwoorden

Een probleem heet meestal handelbaar (tractable) als:

1. AHet geen oplossing heeft
2. BHet in constante tijd kan worden opgelost
3. CHet in polynomiale tijd kan worden opgelost
4. DHet alleen kan worden opgelost door elke mogelijkheid te proberen

Wat zijn de drie stappen van een verdeel-en-heersalgoritme?

1. ASorteren, zoeken, teruggeven
2. BLezen, berekenen, schrijven
3. CRaden, controleren, herhalen
4. DVerdelen, oplossen (heersen), combineren

Welk sorteeralgoritme kiest een pivot en verdeelt de array in kleinere en grotere elementen?

1. AQuicksort
2. BBubblesort
3. CMergesort
4. DInsertion sort

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

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

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

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

In een gesorteerde array zoek je twee elementen die samen een doelwaarde opleveren door vanaf elk uiteinde een pointer naar binnen te bewegen. Wat is de tijdcomplexiteit?

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

Waarom geeft binair zoeken op een enkelvoudig gelinkte lijst geen O(log n) tijd?

1. ABinair zoeken heeft minstens twee keer zoveel geheugen nodig
2. BHet middelste element bereiken kost O(n) stappen, omdat er geen directe toegang via een index is
3. CGelinkte lijsten kunnen niet worden gesorteerd
4. DVergelijkingen op knopen van een gelinkte lijst zijn trager

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