[AlgEnComp] Vragen bij Hfst 3 van Algo

[Beatle]

Vraag 1:
Bij de mergesort tonen ze iets aan voor een welbepaalde n. Hoe zoude we dit verder moeten utiwerken voor alle n's zodat de bewering nog steeds klopt.
p 51

Vraag2:
Ze geven een redenering over de verwachte-tijd van een vergelijkings-gebasseerde zoekmethode.
Waarom geeft de som van Lb het gewenste?
Als er iemand zin heeft om de algemene bedoeling van die twee pagina's uit te leggen ook geen probleem. (De wiskundige stapen snap ik anders wel)
p57-58)

Vraag 3:
Het eerste algoritme voro het selecteren van het k-de element. Daar gaan ze een m bepalen. Hoe staat die m tegenover k? Kzie wel de werking van het algoritme. Maar zie ni in hoe je door die m weet waar k-de element staat.
p 63

Vraag 4:
Hoe ziet er ongeveer dat eenvoudig inductie bewijs eruit om de worste case-complexiteit van dat k-de selectie element te bepalen?
Dus hoe komen ze aan T(n) <= 20c*n voor elke n???
p64

Vraag 5:
Kan er mij iemand helpen om Rp+ te verduidelijken? Bij de stelling op p65. Zeg nu ni de transitieve sluiting daarmee snap ik het niet genoeg.
Een voobeeld is altijd handig.

Vraag 6:
Het lemma op p65 is heel vaag voor mij. Kan er iemand op een normale manier dit uitleggen? Wat, waarom,...

Vraag 7:
Deze vraag komt opzelfde neer. Is het mogelijk op het bewijs op p66 op een betere manier te verwoorden zodat het tot me doordringt?

Grtz

[Quintus Maximus]

Vraag1:

Vraag2: In een sorteeralgoritme komt erop neer dat je een aantal getallen moet permuteren
We krijgen dus een beslissingboom met aan elk blad een andere permutatie.
De tijdscomplexiteit is dus de kans op het blad en de tijd om tot dat blad te geraken. Dus we krijgen pb*lb
Dit voor alle mogelijke bladen: sommeer over b pb*lb

Wat is de bedoeling van die twee pagina's? --> Zie titel van die pagina!!!

Vraag3:

Vraag4:
basis n < 50 dan geldt T(n) <= c* n <= 20*c*n
inductie:
T(n) <= T(n/5) + T(3*n/4) + c*n
<= 20*c*n/5 + 20*c*3*n/4 + c*n = 4*c*n + 15*c*n + c*n = 20*c*n

Vraag5: Rp+ is gewoon een aantal Rp's achter elkaar
Als a1Rpa2 en a2Rpa3 en a3Rpa4 dan kan je gewoon zeggen a1Rp+a4
Dit houdt dus in dat a1 niet rechstreeks ergens vergeleken wordt met a4,
maar dat we wel tussenliggende a's kunnen vinden die vergeleken worden om tot de conclusie te komen dat a1<a4 of a1 <=a4


Vraag6: Het komt eigenlijk hier op neer:
Als we weten dat am het k-de element is, dan kunnen we besluiten dat alle andere a's ofwel kleiner zijn dan am ofwel groter zijn dan am.
aiRp+am zegt dat ai < am of ai <= am en
amRp+ai zegt dat am <ai of am<=ai

Vraag7: wss wel

[B_PC_Freak]

Vraag 1:

ze tonen dit aan voor n = 2^k
algemee: voor willekeurige n geldt: n = 2^(log2 n)

--> als we dit dan invullen in de berekening, geldt de voorwaarde van
blz 8 nog steeds dus is het nog steeds O(n*log(n))

Vraag 3:

de waarde van m doet er niet toe m is net zoals bij quicksort een pivot element om de rij op te delen in 3 verschillende rijen. Het is door naar de grootte van de rijen te gaan kijken dat we weten in welke rij we het k de element moeten gaan zoeken