Algoritmusok és adatszerkezetek gyakorlat
2012
Kurzusleírás és a kurzus teljesítésének feltételei a tanszékcsoport honlapján.
Kisdolgozatok és ZH-k eredményei: az előadáshoz tartozó regisztrációs felületen.
A Hoare- és a Lomuto-féle felosztás sematikus ábrája.
Kiegészítő anyag a tehetséggondozó kurzushoz:
-
a) Egy véletlenszám generátor egyenletes eloszlással dob ki mindig egy 1 és 5 közötti egészet. Ennek segítségével generálj egyeneletes valószínűséggel 1 és 7 közötti egészeket úgy!
b) Adott egy hamis érme. (Ismert, mennyit csal) Szimulálj a segítségével tökéletes pénzfeldobást!
-
Inputként megkapsz egy A és egy B stringet.
(Mindkettő N hosszúságú.)
Írd ki A-t úgy, hogy a B-ben NEM előforduló karaktereket kihagyod!
Konstruálj négyzetes, (N * log N)-es és lineáris algoritmust!
-
100 (különböző értékű) érme van lerakva egy sorba.
A és B felváltva vesz el egy-egy érmét, mindig a
széléről.
a) Van-e valamelyiküknek olyan stratégiája, amivel mindig legalább
annyi pénzt gyűjt össze, mint az ellenfele?
(Ötlet: csoportosítsd a pozíciókat paritás szerint!)
b) Milyen stratégiával maximalizálható az
össznyeremény A illetve B esetén?
(Ötlet: a paritáson alapuló csoportosítás nem mindig optimális, pl. 1, 3, 10, 1, 1, 8. Helyette lehet mondjuk dinamikus programozással:
C(i,j) = max{x_i - C(i+1,j), x_j - C(i,j-1)}.)
-
Adott két rendezett lista, keresd meg azt az elemet, mely kettejük összesítésének lenne a k-adik legnagyobb eleme!
(Ötlet: a 2 listán párhuzamosan végrehajtott bináris kereséssel, mindkét listában egyszerre felezve a keresett elem potenciális helyét.)
-
Adott egy N hosszúságú tömb, A.
Készíts ebből egy D tömböt O(N) idő alatt, melynek i-edik eleme megegyezik az A-nak az i-ediken kívüli összes elemének a szorzata!
Osztás használata nem engedélyezett!
-
Nyolc, kívülről teljesen egyforma golyóból 2 méréssel válaszd ki azt az egyet, amelyik könnyebb a többinél.
Működik-e kilencre is?
-
Ismeretlen hosszúságú listából k db. véletlen elem kiválasztása egyszeri végigolvasás során.
-
Mohó algoritmus a Halmazlefedés problémára, és annak tulajdonságai.
(Legalább és legfeljebb log n közelítés.)
-
Szerkesztési távolság és a Smith-Waterman algoritmus.
(Ehhez kapcsolódóan: BLAST algoritmus.)
-
r-reguláris gráfok, sajátértékeik és
sajátvektoraik
-
k-adik legnagyobb elemmegkeresése O(n \log k) időben illetve O(n) időben.