3. Átlagos futási idő elemzése: hash lineáris próbával,
gyorsrendezés randomizált változata, k. elem keresése, ennek
randomizált és determinizált változata is, Karger algoritmusa
minimális vágás keresésére.
4. Algoritmusok véletlen gráfon, pl. 3 színnel színezés O(1)-ben,
különböző véletlen gráf modellek: Erdős-Rényi modell, Barabási féle
modell, összehasonlításuk.
5-6. Haladó adatszerkezetek és elemzésük: skip list, treap, S-fa
(splay tree), szófa, szuffix-fa (ennek alkalmazásai bioinformatikai
problémákra: átfedések keresése, leghosszabb közös részszó), trie
7. Binomiális kupac, Fibonacci-kupac. Amortizált elemzés módszere
(bankár módszer és potenciált használó módszer), alkalmazás
Fibonacci-kupacra.
8. Adatszerkezetek diszjunkt halmazokra (unió-holvan adatszerkezet
útösszenyomással és ennek elemzése). Megmaradó (persistent)
adatszerkezetek, lusta kiértékelés.
9. Homogén és nem homogén lineáris rekurziók megoldása, az
Akra-Bazzi formula, mester tétel. Példák rekurzív algoritmusok
lépésszámának becslésére.
10. Nehéz problémák egy kezelési módja: paraméteres bonyolultság
alapvető technikái: a keresési fa korlátozása, kernel technika,
néhány alapvető példa.
11. Triviálisnál jobb exponenciális algoritmusok nehéz problémákra,
gyors mátrixszorzás, maximális független ponthalmaz, utazó ügynök
probléma, kromatikus szám, részletösszeg probléma, lokális keresés.
12. Worst-case és average-case analízis közötti hibrid megoldások.
Simított analízis, simított lokális keresés. A 2-OPT alapú lokális
kereső algoritmus simított polinomiális futásidejének bizonyítása.
13. Tömörített érzékelés, alulhatározott lineáris egyenletrendszer
ritka megoldásai, L_1-minimalizálás lineáris programozással.
Alkalmazás: útban az egy pixeles fényképezőgép felé.