8. 6. 2017 Mareš
Napsal: 8. 6. 2017 21:36
1) Výběr k-tého z n prvků
2) (a,b)-stromy (co to je, důkaz logaritmické hloubky, insert nebo delete)
3) Zjistit počet cest v DAGu mezi vrcholy s a t, co mají sudý počet hran
4) Ze vstupní posloupnosti velikosti n vybrat v posuvném okně velikosti k minimum (minimum pro každou sousedící k-tici) - prý to jde lineárně, uznal i řešení v O(n log k)
K algoritmům důkazy, časové i prostorové složitosti.
Úplně pohodová zkouška, jen prolétl papír, do ničeho moc nešťoural.
2) (a,b)-stromy (co to je, důkaz logaritmické hloubky, insert nebo delete)
3) Zjistit počet cest v DAGu mezi vrcholy s a t, co mají sudý počet hran
4) Ze vstupní posloupnosti velikosti n vybrat v posuvném okně velikosti k minimum (minimum pro každou sousedící k-tici) - prý to jde lineárně, uznal i řešení v O(n log k)
K algoritmům důkazy, časové i prostorové složitosti.
Úplně pohodová zkouška, jen prolétl papír, do ničeho moc nešťoural.