Zápočtové úlohy na IPS II
Pokud se vám nepodařilo získat zápočet za předvádění řešení u tabule, můžeme si jej vysloužit vyřešením libovolného z následujících příkladů:
- Spočítejte průměrnou délku náhodné procházky z kořene úplného binárního stromu do jeho určitého listu.
- Vymyslete paralelní algoritmus na rozklad grafu na komponenty souvislosti, který bude běžet v čase O(logk n) pro nějaké k. Vstupem nechť je matice sousednosti grafu, výstupem pole, které pro každý vrchol obsahuje číslo komponenty, do které vrchol patří.