Werkblad Algoritmen & complexiteit met antwoorden

Hoeveel extra geheugen gebruikt een standaard mergesort op basis van arrays?

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

Wat is de worst-case tijdcomplexiteit van mergesort?

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

Wat betekent het als een bewerking in O(1) tijd loopt?

1. AHet duurt altijd precies één seconde
2. BHet kan maar één keer worden uitgevoerd
3. CHet verwerkt precies één element per seconde looptijd
4. DDe looptijd groeit niet met de invoergrootte

Welk sorteeralgoritme is stabiel?

1. AMergesort
2. BHeapsort
3. CQuicksort (gangbare in-place-versie)
4. DSelectionsort (gangbare versie)

Wat meet geamortiseerde analyse?

1. ADe gemiddelde kosten per bewerking over een worst-casereeks van bewerkingen
2. BDe kosten van een algoritme bij de beste invoer
3. CDe kosten van de ene duurste bewerking ergens in de reeks
4. DDe verwachte kosten over willekeurige invoer

Wat is de looptijd van LSD-radix sort op n gehele getallen met d cijfers in grondtal k?

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

Insertion sort loopt in O(n) op gesorteerde invoer. Is dit in tegenspraak met de ondergrens Ω(n log n) voor sorteren met vergelijkingen?

1. ANee, omdat insertion sort geen sorteeralgoritme op basis van vergelijkingen is
2. BJa, maar alleen voor arrays korter dan 100
3. CJa, de ondergrens is dus fout
4. DNee, de ondergrens geldt voor het slechtste geval over alle invoeren, niet voor elke invoer

Welke definitie van de klasse NP is juist?

1. AProblemen die niet polynomiaal zijn
2. BBeslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd
3. CProblemen die niet in polynomiale tijd kunnen worden opgelost
4. DProblemen die geen enkel algoritme kan oplossen