Mediáns keresés, gyorsrendezés.
Mintaillesztés. I. Kimerítő keresés (Brute Force).
II. Quick Search (Horspool).
III. Knuth-Morris-Pratt
[RISz, CLRS].
Mit tegyünk, ha NP-nehéz feladatokat kell megoldani?
I. Exponenciális algoritmusok, heurisztikák.
I a) brute force
I b) heurisztika + brute force
I c) backtrack
I d) elágazás és korlátozás (branch-and-bound).
II. Speciális input/output.
III. Közelítő algoritmusok, definíciók, egyszerű példák.
Metrikus utazó-ügynök, 2-közelítés.
Approximációs sémák.
FPTAS a hátizsák-feladatra.
2-közelítés a minimális súlyú lefogó csúcshalmaz feladatra, mese ILP-ről és a tört relaxált optimális megoldásának kikerekítéséről általában.
Paraméteres problémák, fix paraméteres feladatok. XP és FPT.
A minimális lefogó csúcshalmaz:
Döntési fa alapú FPT a minimális lefogó csúcshalmazra maximális fokú
csúcs kiválasztásával.
Kernel, korona-redukció. 2k méretű kernel készítése.
On-line algoritmusok. Síbérlés vagy vásárlás. Versenyképességi hányados.
A Lapozási feladat:
a versenyképesség minimum k, minden jelölő algoritmus k-versenyképes.
A k-robot probléma, tételek bizonyítás nélkül.
Röviden volt: A ládapakolási probléma, a First Fit algoritmus;
on-line gráfszínezés, kapcsolat adatstruktúrákkal.
A párhuzamos számítások alapjai. Brent tételei. Nagy számok összeadása és szorzása. Mátrix-szorzás alkalmazásai.
Alapvető geometriai algoritmusok.
I. Konvex burok keresése a síkon [Adat, CLRS].
II. Legközelebbi pontpár keresése a síkon [CLRS].
III. Téglalapba eső pontok lekérdezése. Tartomány-fa felépítése/I.
[Adat].
Tartományfa használata. Tartományfa javítása kaszkádolással, d dimenziós tartományfa [Adat]. Felépítés O(n\log n)-ben.
Legrövidebb utak keresése világméretű úthálózatokban.
Kétirányú Dijkstra, A^* algoritmus.
Legrövidebb utak keresése világméretű úthálózatokban előfeldolgozással. Autópálya hierarchiák (HH), tranzit csúcsok (TNR), összehúzási hierarchiák (CH).
Konzultáció.