Werkblad Algoritmen & complexiteit met antwoorden

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

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

Wat is de looptijd van counting sort voor n gehele getallen in het bereik 0 tot k?

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

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

1. AConstant
2. BKwadratisch
3. CLineair
4. DLogaritmisch

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(n log n + k log n)
4. DO(k n log n)

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

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

Is het juist om te zeggen dat een O(n²)-algoritme ook O(n³) is?

1. ANee, omdat grote O altijd de exacte groeisnelheid van de functie moet geven
2. BJa, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
3. CJa, maar alleen als n kleiner is dan 100
4. DNee, omdat n³ voor grote n kleiner is dan n²

Welke bewering over P en NP is juist?

1. AOplossingen van NP-problemen kunnen niet snel worden geverifieerd
2. BNP betekent "niet polynomiaal"
3. CEr is bewezen dat P ≠ NP
4. DElk probleem in P zit ook in NP

Welke definitie van de klasse P is juist?

1. AProblemen die parallel kunnen worden opgelost
2. BProblemen die op elke computer exponentiële tijd nodig hebben
3. CBeslissingsproblemen die door een deterministisch algoritme in polynomiale tijd kunnen worden opgelost
4. DProblemen waarvan oplossingen wel kunnen worden gecontroleerd maar nooit in polynomiale tijd gevonden