Sziasztok! A mai órán az alább következő feladatokat oldották meg azok, akik ott voltak az órán. Kivétel a harmadik feladat, az tipikusan olyan, amit otthon a könyv mellett ülve lehet legjobban végiggondolni. Tegyétek ezt! Az utolsó feladathoz annyi megjegyzést fűznék, hogy ha ilyet láttok, akkor mindig gondoljatok arra, hogy milyen tételt ismerünk, ami azt mondja, hogy valamit (jelen esetben a rendezést) nem lehet valaminél kevesebb dologgal (most lényegében n log n -nél kevesebb összehasonlítással) megcsinálni. A példák: Algoritmuselmélet pótgyakorlat a harmadik gyakorlathoz 1. A következőket tudjuk egy fa m,n elemeiről: m megelőzi n-t a fa X-order szerinti bejárásában, viszont m az n után jön a fa Y-order szerinti bejárásában (X,Y $=\{ pre, post,in\}$). Melyik eset(ek)ben tudjuk eldönteni, hogy m őse-e n-nek? 2. Az S1 és S2 kulcshalmazokat kiegészített 2-3-fákban tároljuk. Ezek az eredeti 2-3-fától abban különböznek csak, hogy minden csúcsban fel van jegyezve az onnan induló részfa magassága (szintjeinek száma). Tegyük még fel, hogy az S1-beli kulcsok mind kisebbek az S2-belieknél. Javasoljunk hatékony algoritmust a két fa egyesítésére. A cél tehát egy olyan kiegészített 2-3-fa, amelyben a kulcsok $S_1\cup S_2$ elemei. 3. Egy AVL-fába egy új elemet illesztettünk be az előadáson tanult módszerrel. Az eredményképpen kapott AVL-fa magassága nagyobb, mint az eredetié. Milyen forgatást alkalmazhattunk? 4. Adott egy n=2k-1 pontú teljes bináris keresőfa. A fában tárolt elemek egészek az I=[1,2k] intervallumból és egy szám legfeljebb egyszer fodul elő a fában. Utóbbi feltétel szerint pontosan egy olyan $i\in I$ egész van, amely nincs a fában. Adjunk egy hatékony módszert i meghatározására. 5. Adottak a sík egész koordinátájú $P_1=(x_1,y_1),P_2=(x_2,y_2),\ldots , P_n=(x_n,y_n)$ pontjai. Javasoljunk $O(n\log n)$ költségű módszert annak eldöntésére, hogy vannak-e olyan Pi,Pj pontok ($i\not= j$), melyek távolsága nem több mint 2. 6. Egy rendezett halmaz adott n eleméből kupacot szeretnénk építeni, melyre (a kupac tulajdonság mellett) teljesül, hogy minden x csúcs bal részfájának az elemei kisebbek mint az x jobb részfájának az elemei. Igazoljuk, hogy ehhez legalább $\Omega (n\log n)$ összehasonlítás szükséges! Megoldások