–> Sekce začíná v pondělí odpoledne ve 12.30, trvání 12.30 - 14.30, 14.45 - 16.00.
–> Rozvrh úterý a středa - dopoledne 9.00 - 11.45, odpoledne 12.30 - 14.30, 14.45 - 16.00.
. Úpravy možné po dohodě s lektorem.

–> Učebna KN:E-230, budova E v areálu FEL ČVUT na Karlově náměstí.

Orientovaný acyklický graf (DAG), optimální cesty v DAG. Bellman-Ford

Prezentace:

1. Cesty v acyklickém grafu , ( pdf), Slidy

Úlohy (DAG):

1. https://projecteuler.net/problem=15
2. https://projecteuler.net/problem=18
3. https://projecteuler.net/problem=67
4. 10305 - Ordering Tasks
5. 926 - Walking Around Wisely
6. 11137 - Ingenuous Cubrency
7. COINS - Bytelandian gold coins
8. https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=longslopes2
9. https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=increasingload

Úlohy (Bellman-Ford):

1. 558 - Wormholes
2. 436 - Arbitrage (II)

Postupy založené na DFS, artikulace (cutvertices), mosty, silně souvislé komponenty.

Animace: https://visualgo.net/en/dfsbfs

DFS: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3057

Floyd-Warshall, párování v bipartitních grafech.

Prezentace:

1. Floyd-Warshall, Bipartitní párování

Úlohy (Floyd-Warshall):

1. 423 - MPI Maelstrom
2. 186 - Trip routing

Úlohy (Bipartitní párování):

1. 11045 - My T-shirt suits me
2. 10092 - The Problem with the Problem Setter
3. 10080 - Gopher II

Jádro grafu a hry.

Minimální kostry, Prim, Borůvka, Kruskal.

https://www.spoj.com/problems/ULM09/ https://www.urionlinejudge.com.br/judge/en/problems/view/2683 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=975 http://codeforces.com/problemset/problem/32/C https://www.spoj.com/problems/IITKWPCG/