Set EEN

Eerste Huiswerk Algoritmiek
18 februari 2015, uitwisselen, WerkCollege.
Kijk een huiswerkset na met een team van twee, voorzie de uitwerking van commentaar en becijfering, en neem de nagekeken set mee naar het werkcollege van 25 februari (duidelijk voorzien van
de namen en studentnummers van de nakijkers). Inleveren bij Roel.
Cijfer: Te behalen 22 punten, cijfer is punten gedeeld door 2 (max 10).
1. Substitutie-methode: Bewijs met de substitutie-methode dat de oplossing van T (n) =
T (n/3) + T (n/3) + T (n/4) + O(n) voldoet aan T (n) = O(n).
Oplossing: Je moet altijd de impliciete constante expliciteren, dus bewijzen dat T (n) ≤ c.n
voor een c uit gegeven T (n) ≤ T (n/3) + T (n/3) + T (n/4) + d.n. Neem aan dat T (n0 ) ≤ c.n0
(Ind Hyp) voor n0 < n, dan volgt
T (n) ≤
≤
≤
≤
T (n/3) + T (n/3) + T (n/4) + d.n
c.n/3 + c.n/3 + c.n/4 + d.n
(11/12.c + d).n
c.n
Gebruik Gegeven
Gebruik Ind Hyp
Vereenvoudig
mits c ≥ 12d
Beoordeling: Als het bewijs goed is 2pt. Als explicitering van constanten goed, maar
rekenwerk fout, 1pt.
A = Komt uit op O(n) ipv c.n. Het is verleidelijk om in de laatste stap (11/12.c + d).n in
een keer te vervangen door O(n), want “dat is wat je wilt bewijzen”. Het is fout, want na
explicitering van de constante is wat je wilt bewijzen: T (n) ≤ c.n; 0pt.
C = Geen of onjuiste Conditie op c afgeleid; aftrek 1pt.
E = Vergeet de Explicitering van constanten. Als je dit niet doet voor het gegeven krijg je
vaak een Vage stap.
I = Let op, IndHyp gaat over n0 < n, nooit formuleren als T (n) = O(n); min 1/2.
R = Rekenwerk fout, aftrek naar ernst van het vergrijp.
S = Geen Substitutiemethode gebruikt, max 1pt.
V = Vage stap (waarvan geen motivatie is gegeven of deze onterecht is), aftrek naar ernst (bij
bluffen geen punten).
2. Master Theorem: Geef de asymptotische oplossing voor de recurrentie T (n) = 3.T (n/2)+n
en de oplossing voor de recurrentie U (n) = 2.U (n/2) + n.
b
Oplossing: Voor T kom je, met a = 3 en b = 2 voor n log a op n1,585 . De term n is polynomiaal
minder (want exponent 1 is kleiner dan 1,585), de oplossing is dus T (n) = O(n1,585 ).
b
Voor U kom je, met a = 2 en b = 2 voor n log a op n1 . De term n is gelijk, de oplossing is dus
U (n) = O(n lg n)
Beoordeling: Voor goed antwoord met uitleg over toepassing MT 2pt. Beordeling verdere
antwoorden:
F = Fout antwoord, 0pt.
S = De uitkomst kwadratisch wordt bewezen met Substitutiemethode, is ook goed: 2pt mits
substitutie goed toegepast.
Z = Alleen “het is O(n1,585 )” Zonder uitleg 0,5pt.
3. Karatsuba Integer Vermenigvuldigen: Je kunt n-bits integers A en B vermenigvuldigen
door (1) ze te verdelen in n/2-bits getallen A1 A0 en B1 B0 , (2) de deelresultaten R0 = A0 · B0
en R1 = A1 · B0 + A0 · B1 en R2 = A1 · B1 te berekenen, en (3) de deelresultaten met goede
verschuiving weer op te tellen.
(a) Laat zien hoe je de drie benodigde deelresultaten kunt berekenen met drie n/2-bits vermenigvuldigingen.
(b) Analyseer de asymptotische rekentijd V (n).
(c) Je overweegt of het nog beter kan, door de getallen in drie stukjes A = A2 A1 A0 te verdelen,
en deelresultaten te vinden door een aantal n/3-bits vermenigvuldigingen te doen. Hoeveel
vermenigvuldigingen kun je je veroorloven om toch een beter algoritme te krijgen dan met
verdelen in twee?
Oplossing: (a) Neem R0 = A0 · B0 , R2 = A1 · B1 als benodigd, en bereken R1 = (A0 + A1 ) ·
(B0 + B1 ) − R0 − R2 .
(b) Je hebt drie sub-vermenigvuldigingen van lengte n/2 en lineair werk voor het optellen
en aftrekken, dus V (n) = 3V (n/2) + O(n). Master Theorem met b = 2 en a = 3 geeft
b
n log a = n1,585.. , wat polynomiaal meer is dan O(n), dus uitkomst O(n1,585 ).
3
(c) Als je a vermenigvuldigingen moet doen, kost het n log a (mits a > 3). 3 log 6 = 1, 63 en
3 log 5 = 1, 465, dus je zult het met vijf vermenigvuldigingen moeten doen om onder de n1,585
uit te komen. Succes (en zoek eens op Toom-Cook multiplication)!
Beoordeling: Voor de gezochte vermenigvuldiging in (a), 1pt; voor de juist berekende rekentijd (inc. de waarde 1,585 van lg 3) in (b) 2pt; voor het bepalen dat zes vermenigvuldigingen
niet snel genoeg is en vijf wel in (c), 1pt.
4. Aliens: Van een straat met n huizen genummerd van 0 t/m n − 1 is bekend dat er op nr
0 een Slowaak woont en op nr n − 1 een Tsjech. Geef een algoritme dat, na het vragen van
hoogstens dlg(n − 1)e nationaliteiten, twee buren (personen met huisnummerverschil 1) vindt
van verschillende nationaliteit. Geef een invariant van je algoritme en leg met een variant uit,
waarom je de complexiteit haalt.
Oplossing: Dat er Alien Neighbors zijn in een deel i..j van de straat volgt uit land(i) 6=
land(j). Dit is gegeven voor (i, j) = (0, n − 1) en geeft direct het antwoord als j = i + 1. Je
kunt dus dit algoritme maken met invariant land(i) 6= land(j):
i = 0; j= n-1
while (j > i+1)
{ m = (i+j)/2
if (land(m) != land(i)) j=m else i=m
}
return i
Het verschil j − i halveert per stap, dit is je variant. Die begint met waarde n − 1, dus zijn
er hoogstens dlg(n − 1)e ronden. In elke ronde vraag je ´e´en nationaliteit (want land(0) weet
je al).
Beoordeling: Voor een goed geformuleerde invariant 1pt, voor het noemen van de variant
1pt, voor een kort en goed algoritme 1pt (dat past bij de invariant). Totaal dan 3pt.
A = Er kunnen Andere nationaliteiten dan Sk en Cz zijn; als oplossing dan fout gaat half
eraf.
E = Een Early Stopper, dwz kijkt naar succes in de loop. Early Stoppers zijn nodeloos
complex en halen het ge¨eiste aantal navragen niet omdat je twee keer per ronde vraagt.
L = Voor een Lineair algoritme geen punt.
M = Midpointformule m = i + (j-i)/2 is nodeloos complex.
N = Variant is een Numerieke, geen booleaanse waarde.
P = Midpointformule op verkeerde plek (voor ipv in loop).
R = Tail Recursie, niet perse fout maar een loop is handiger. Vergeet de initiele aanroep niet!
T = Met Test while (i<j) geen Terminatie!
V = Neemt Verschil van nationaliteiten (A[j] − A[i]), ik wist niet dat dat kon ... .
Z = Te Zwakke invariant. Predicaat P geldt wel steeds, maar { P } Body { P } is niet
bewijsbaar.
5. Records met Begrensde Som: Je hebt (ongesorteerde) records over zieke kinderen, waarbij
kind i kan worden genezen met een investering ki . Je hebt D euro aan donaties ontvangen,
waarmee je zoveel mogelijk kinderen wilt genezen. Beschrijf een algoritme dat een zo groot
mogelijke set kinderen kiest zodat de totale k is begrensd door D. Geef de looptijd; het kan
in lineaire tijd!
Oplossing: Een Greedy aanpak die steeds het goedkoopste kind kiest, geeft een optimale
oplossing. De GCP is: elke set die het goedkoopste kind niet bevat, kun je veranderen in een
set die dat kind wel bevat, namelijk door een willekeurige door de goedkoopste te vervangen.
Je kunt dus sorteren en dan van vooraf elementen in de set nemen, het totaal van ki bijhouden
en stoppen als D wordt overschreden. Maar dat kost (vanwege het sorteren) O(n lg n).
Pas QuickSelect aan om niet te kijken naar een gegeven rang, maar naar een gegeven som.
QuickSum(p,q,d) sorteert de rij gedeeltelijk, waarbij in ieder geval dat kind op de juiste plek
komt, dat als eerste het totaal D zou overschrijden. De uitgebreide versie van Split(p,q,piv)
geeft ook de som s van elementen kleiner dan de Pivot:
QuickSum(p,q,d)
piv = Rand(p,q);
s,r = Split(p,q,piv);
if (d<s) QuickSum(p,r,d);
if (d>s+k[r]) QuickSum(r+1,q,d-s-k[r]);
Voor een worst case lineair algoritme kun je dit natuurlijk met Mediaan-der-Medianen doen.
Beoordeling: Voor een compleet lineair algoritme met goede uitleg 3pt. Onderverdeling:
1 voor het idee van steeds de kleinste, 1 voor onderbouwing (bv met GCP), 1 voor lineair
maken met selectie-idee.
G = Geen Greedy Choice argumentatie; -1.
K = Een Kwadratisch of nog hoger algoritme (bv. herhaalde minimumselectie) levert geen
punten.
P = Dynamisch Programmeren met tabel n × D, Pseudopolynomiaal in D, max 1/2.
S = Sorteren en beginstuk nemen; niet lineair, 1pt voor algo. Ook bijhouden van een een lijst
en max verwijderen als het te duur wordt, kost (minstens!) n lg n.
6. The Poor Pilgrim: Een pelgrim maakt een voettocht naar Rome, K km ver. Op een dag
kan hij maximaal L km lopen, en gelukkig zijn er onderweg n herbergen, waar herberg i op
di km van het begin ligt. De eerste ligt in zijn woonplaats dus s0 = 0, de laatste ligt in
Rome dus sn = K, en de afstand tussen opeenvolgende is nooit groter dan L. Overnachten
in herberg i kost pi goudstukken.
Beschrijf hoe je kunt berekenen hoeveel goudstukken de pelgrim minimaal nodig heeft om de
reis te volbrengen; geef de rekentijd.
Oplossing: Het gezochte bedrag is B(n), als we B(j) definieren als het bedrag, nodig om tot
locatie j te geraken, exclusief overnachten in j. Neem als topkeuze: a is de laatste herberg
voor j. Alternatieven zijn dan die waarden a < j met sa >≥ sj − L. De kosten bij keuze a
zijn B(a) + pa . Dus B(j) = mina pa + B(a). Een DP rekent dit voor elke j eenmaal uit.
Per j is er minstens 1 alternatief, maar het kunnen er tot j zijn, wat een worst-case complexiteit O(n2 ) geeft.
Beoordeling: Voor een werkend algoritme 2pt, voor enige beschouwing over de looptijd 1pt.
Beoordelingscodes:
A = Indexeert deelproblemen aan Afstand ipv nummer (bv door B(si ) uit te drukken in
B(si − L)). Dit geeft teveel deelproblemen (pseudoploynomiaal), max 1pt voor algoritme.
F = Feasibility van oplossing (afstand L tussen herbergen) is niet verwerkt in de karakterisering, 0 of 1 pt.
L = Lineaire tijd (ik denk dat dit kan maar weet nog niet hoe), bonus +1pt mits voldoende
onderbouwd.
7. The Hasty Pilgrim: Een pelgrim maakt een voettocht naar Rome, K km ver. Op een dag
kan hij maximaal L km lopen, en gelukkig zijn er onderweg n herbergen, waar herberg i op
di km van het begin ligt. De eerste ligt in zijn woonplaats dus s0 = 0, de laatste ligt in Rome
dus sn = K, en de afstand tussen opeenvolgende is nooit groter dan L.
Beschrijf hoe je kunt berekenen hoeveel dagen de pelgrim minimaal nodig heeft om de reis te
volbrengen; geef de rekentijd.
Oplossing: Als de pelgrim zo snel mogelijk in Rome wil zijn, kan hij het beste elke dag zover
mogelijk lopen, dus tot de verst haalbare overnachtingsplaats. Neem a de grootste index
waarvoor nog sa ≤ L en neem als GCP: Voor elke feasible lijst herbergen R is er een lijst R0
die met a begint, en niet langer is dan R. Bewijs hiervan: je kunt van R de eerste vervangen
door a, deze is binnen bereik op de eerste dag, en de tweede van R is zeker haalbaar vanaf a
omdat a minstens zo ver ligt als de eerste van R. Dit leidt tot het volgende Greedy Algoritme:
Neem a0 = 0, neem achtereenvolgens ai+1 de grootste index waarvoor sai+1 ≤ sai . Dit kost
O(n) tijd omdat je elke herberg maar 1x bekijkt.
Beoordeling: Voor een werkend algoritme 2pt, voor enige beschouwing over de looptijd 1pt.

Download Report