Algoritmuselmélet pótgyakorlat a második gyakorlathoz - 1999. október 6., szerda

Könnyű feladatocskák
1. Rendezzük a következő listát kupacos rendezés, gyorsrendezés, és az összefésüléses rendezés segítségével: 4,11,9,10,5,6,8,1,2,16.

2. Egy csupa különböző egészekből álló sorozat bitonikus, ha először nő, utána pedig fogy, vagy fordítva: először fogy, utána nő. Például az (1,3,7, 21, 12,9,5), (9,7,5,4,6,8) és (1,2,3,4,5) sorozatok bitonikusak. Adjunk O(n) összehasonlítást használó rendező algoritmust n elemű bitonikus sorozatok rendezésére!

Középhaladóknak való feladatok
3. Az A[1:n] tömbben egész számokat tárolunk. Tudjuk, hogy van olyan i index, amellyel

$$A[i]<A[i+1]<\ldots <A[n]<A[1]<\ldots <A[i-1]$$

teljesül. Adjunk minél kevesebb összehasonlítást használó módszert ennek az (egyértelműen meghatározott) i indexnek a megkeresésére. Elemezzük a módszer költségét!

4. Igazoljuk, hogy egy n elemből álló bináris kupac felépítése $\Omega(n)$ összehasonlítást igényel!

Nem egyszerű feladatok
5. Az A[1:n] tömb piros és zöld elemeket tartalmaz. Szeretnénk átrendezni úgy, hogy az egyszínű elemek folytonosan helyezkedjenek el (elöl az összes piros, utána a zöldek vagy fordítva). Egy megengedett lépés két szomszédos tömbelem cseréje. Javasoljunk konstans szorzó erejéig optimális lépésszámú algoritmust.

6. Pontosan hány összehasonlítás kell ahhoz, hogy egy n elemű tömbből egy olyan tagot keressünk, ami a tömb legkisebb 10 eleme közé tartozik? (A tömb egy rendezett univerzum n különböző eleméből áll, de maga nem feltétlenül rendezett. Az eredmény bármelyik lehet a legkisebb tíz közül: tehát pl. az első éppúgy megfelel, mint a tizedik.)

Algoritmuselmélet pótgyakorlat a második gyakorlathoz - 1999. október 6., szerda

Könnyű feladatocskák
1. Rendezzük a következő listát kupacos rendezés, gyorsrendezés, és az összefésüléses rendezés segítségével: 4,11,9,10,5,6,8,1,2,16.

2. Egy csupa különböző egészekből álló sorozat bitonikus, ha először nő, utána pedig fogy, vagy fordítva: először fogy, utána nő. Például az (1,3,7, 21, 12,9,5), (9,7,5,4,6,8) és (1,2,3,4,5) sorozatok bitonikusak. Adjunk O(n) összehasonlítást használó rendező algoritmust n elemű bitonikus sorozatok rendezésére!

Középhaladóknak való feladatok
3. Az A[1:n] tömbben egész számokat tárolunk. Tudjuk, hogy van olyan i index, amellyel

$$A[i]<A[i+1]<\ldots <A[n]<A[1]<\ldots <A[i-1]$$

teljesül. Adjunk minél kevesebb összehasonlítást használó módszert ennek az (egyértelműen meghatározott) i indexnek a megkeresésére. Elemezzük a módszer költségét!

4. Igazoljuk, hogy egy n elemből álló bináris kupac felépítése $\Omega(n)$ összehasonlítást igényel!

Nem egyszerű feladatok
5. Az A[1:n] tömb piros és zöld elemeket tartalmaz. Szeretnénk átrendezni úgy, hogy az egyszínű elemek folytonosan helyezkedjenek el (elöl az összes piros, utána a zöldek vagy fordítva). Egy megengedett lépés két szomszédos tömbelem cseréje. Javasoljunk konstans szorzó erejéig optimális lépésszámú algoritmust.

6. Pontosan hány összehasonlítás kell ahhoz, hogy egy n elemű tömbből egy olyan tagot keressünk, ami a tömb legkisebb 10 eleme közé tartozik? (A tömb egy rendezett univerzum n különböző eleméből áll, de maga nem feltétlenül rendezett. Az eredmény bármelyik lehet a legkisebb tíz közül: tehát pl. az első éppúgy megfelel, mint a tizedik.)