Zkouška 16.6. Čepek

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Návštěvník

Zkouška 16.6. Čepek

Příspěvek od Návštěvník »

Vím, že tady tohle zadání už bylo, ale nebylo u něj řešení, což by mohlo někomu pomoct. Takže přikládám odkazy.

1) BVS - komutativita delete
Pokud odstraníme x a poté y, bude to to samé, jako když odstraníme y a poté x? Dokázat nebo najít protipříklad.

https://stackoverflow.com/questions/299 ... earch-tree


2) vážený průměr v O(n)
Máme klíče x1.. x n a váhy k nim w1 .. wn. Obě dvě řady nesetřízené, přirozená čísla.
Vážený průměr: takové xi, že součet x1 .. xi-1 je nejvýše polovina součtu všech vah, xi+1 .. xn je je nejvýše polovina součtu všech vah. Spočítejte v O(n)

https://cs.stackexchange.com/questions/ ... inear-time


3) Nejkratší (co se týče POČTU hran) negativní cyklus v ohodnoceném grafu. (Pokud není, oznámí, že není).

Nejlepší řešení asi "násobení matic" ukázané na přednášce (při hledání nejkratších cest mezi všemi vrcholy). Kontrolovat diagonálu, jestli tam není záporné číslo. Složitost by měla být v nejhorším n4. (Doufám, že nekecám, řešil jsem to jinak a neměl jsem to správně).


U ustní např.: Definovat AVL strom a dokázat výšku, rozšířený Euklid, nějaké vlastnosti čč-stromu.
Hodně štěstí!!!
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“