Algoritmuselmélet gyakorlat (2)

1. Legyen adott egy egészekből álló A[1:n] tömb valamint egy b egész szám. Szeretnénk hatékonyan eldönteni, hogy van-e két olyan $i,j\in\{1,\ldots,n\}$ index, melyekre A[i]+A[j]=b. Oldjuk meg ezt a feladatot $O(n\log n)$ időben!

2. A (növekvően) rendezett A[1:n] tömb k darab elemét valaki megváltoztatta. A változtatások helyeit nem ismerjük. Javasoljunk $O(n+k\log k)$ uniform költségű algoritmust az így módosított tömb rendezésére!

3. Adott egy rendezett univerzum n különböző eleméből álló S halmaz. Legyen $l:=\lfloor\log_2 n\rfloor$. Felosztandó az S halmaz olyan nem üres $S_1,S_2,\ldots,S_l$ részhalmazokra, hogy tetszőleges $1\leq i< j \leq l$ számpárra az S_i halmaz minden eleme kisebb legyen az S_j halmaz minden eleménél. Adjunk meg egy $O(n\log\log n)$ összehasonlítást használó módszert a fenti feladatra!

4. Adott egy egész számokat tartalmazó A[1:n] tömb, amelyben legfeljebb n elempár áll inverzióban egymással. (Két elem akkor áll inverzióban, ha a nagyobb megelőzi a kisebbet.) Igaz-e, hogy a buborékrendezés rendezi a tömböt
(a) legfeljebb n összehasonlítással?
(b) legfeljebb n cserével?

5. Adjunk konstans szorzó erejéig optimális számú összehasonlítást használó módszert az $A_1,A_2,\ldots,A_m$ egyenként k elemű rendezett tömbök összefésülésére!

6. Adjunk hatékony algoritmust egy kupac tizedik legkisebb elemének a megtalálására. Elemezzük a módszer költségét.

7. Egy rendezett halmazból n elem kupacban van elhelyezve. Bizonyítsuk be, hogy a legnagyobb elem megkereséséhez $\Omega(n)$ összehasonlítás szükséges!

8. Adott egy dobozban n különböző méretű anyacsavar, valamint egy másik dobozban a hozzájuk illő apacsavarok. Kizárólag a következő összehasonlítási lehetőségünk van: Egy apacsavarhoz hozzápróbálunk egy anyacsavart. A próbának háromféle kimenete lehet: $\mbox{apa}<\mbox{anya}$, $\mbox{apa}=\mbox{anya}$, vagy $\mbox{apa}>\mbox{anya}$; annak megfelelően, hogy az apacsavar külső átmérője hogyan viszonyul az anyacsavar belső átmérőjéhez. Szeretnénk az anyacsavarokhoz megtalálni a megfelelő apacsavarokat. Adjunk erre a feladatra átlagosan $O(n\log n)$ összehasonlítást felhasználó módszert!

9. Vázoljunk egy O(n) időigényű algoritmust (az időkorlát bizonyításával együtt) n olyan egész számból álló sorozat rendezésére, melynek elemei az
(a) $\{1,\ldots ,3n\}$ tartományba esnek!
(b)(*) $\{1,\ldots ,n^7-1\}$ tartományba esnek!

10. 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) uniform költségű módszert olyan $P_i\not=P_j$ pontok kiválasztására, amelyeken átmenő egyenes által meghatározott félsíkok közül az egyik tartalmazza az összes input pontot.

11. Valaki egy összehasonlításon alapuló állítólagos rendezési algoritmusról azt mondja, hogy mivel az eljárás minden olyan sorozatot jól rendez, amelyben a rendezett sorrendhez képest csak egyetlen pár van felcserélve, ezért az algoritmus tetszőleges soroztot rendez. Helyes-e ez a következtés?

Gondolkozni való feladat
12. Hány összehasonlítással lehet rendezni öt elemet?

13. Egy n-szer n-es táblázatban úgy van elhelyezve n² db különböző szám, hogy mind a sorok mind az oszlopok monoton növekvőek. Mutassuk meg, hogy ekkor a keresés lépésszáma $\Theta(n)$.