Algorithms and data structures III — различия между версиями
VeLKerr (обсуждение | вклад) (Новая страница: «Test») |
Ariel (обсуждение | вклад) (Page creation) |
||
| Строка 1: | Строка 1: | ||
| − | + | ||
| + | |||
| + | <h3> | ||
| + | Feb, 18. | ||
| + | Recalling [http://judge2.vdi.mipt.ru/yudaev/english/1-bfs.pptx bfs] and [http://judge2.vdi.mipt.ru/yudaev/english/2-DFS.pdf dfs]. | ||
| + | </h3> | ||
| + | [http://judge2.vdi.mipt.ru/yudaev/english/3-shortest-paths.pdf Shortest paths], [http://judge2.vdi.mipt.ru/yudaev/english/4-dijkstra.pdf Dijkstra algorithm]. | ||
| + | |||
| + | [https://contest.yandex.ru/contest/21550/enter/ Contest on Dijkstra] | ||
| + | |||
| + | <h3> | ||
| + | Feb, 25. | ||
| + | Balanced binary trees, heaps. | ||
| + | </h3> Cormen et al: ch 6, 12 | ||
| + | [http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410404 Contest on binary trees and heaps] | ||
| + | |||
| + | <h3> | ||
| + | Mar, 4. | ||
| + | [http://judge2.vdi.mipt.ru/yudaev/english/hashing.ppt Hash-tables] , [http://judge2.vdi.mipt.ru/yudaev/english/Rabin-Karp.ppt Rabin-Carpe algorithm] | ||
| + | </h3> Cormen et al.: ch 10.3, 11, 32.2 | ||
| + | |||
| + | [http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410405 Contest on hash tables] | ||
| + | |||
| + | <h3> | ||
| + | Mar, 9. [http://judge2.vdi.mipt.ru/yudaev/english/FiniteAutomata.ppt Finite-state automata]. | ||
| + | </h3> | ||
| + | Cormen et al: ch 32.3, | ||
| + | |||
| + | [https://www.gatevidyalay.com/minimization-of-dfa-minimize-dfa-example/ Dramatic how-to about DFA minimisation] | ||
| + | Also see <br/> | ||
| + | Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: principles, techniques, and tools, ch 3.9 | ||
| + | <br/>John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, ch 4.4.3 | ||
| + | |||
| + | [http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410406 Contest on automata] | ||
| + | |||
| + | <h3> | ||
| + | Mar,16. Dynamic programming. | ||
| + | </h3> | ||
| + | [http://olymp3.vdi.mipt.ru/cgi-bin/new-register?contest_id=410407 Contest on dynamic programming] | ||
| + | |||
| + | <h3> | ||
| + | Mar,23. [http://judge2.vdi.mipt.ru/yudaev/english/fenwick.ppt Segment trees]. | ||
| + | </h3> | ||
| + | [http://olymp3.vdi.mipt.ru/cgi-bin/new-register?contest_id=410408 Contest on segment and Fenwick trees] | ||
| + | |||
| + | <h3> | ||
| + | Mar,30. Semiterm control work. | ||
| + | </h3> | ||
| + | |||
| + | Topics: hash tables, Fenwick trees, compound data structures, word correctness check. | ||
| + | |||
| + | |||
| + | |||
| + | <h3> | ||
| + | Apr,6. Graph algorithms recalling. | ||
| + | </h3> | ||
| + | [http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410403 Contest on basic graph algorithms] | ||
| + | |||
| + | <h3> | ||
| + | Apr,13. [http://judge2.vdi.mipt.ru/yudaev/english/8-dynamic-programing-shortest-paths.pdf Bellman-Ford] and other shortest paths. | ||
| + | </h3> | ||
| + | Cormen et al, ch 24-25. | ||
| + | <br/> | ||
| + | [http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410410 Contest on shortest paths] | ||
| + | |||
| + | <h3> | ||
| + | Apr,20. [http://judge2.vdi.mipt.ru/yudaev/english/flowcut.pdf Maximal flow]/minimal cut. | ||
| + | </h3> | ||
| + | Cormen et al, ch 26. | ||
| + | <br/> | ||
| + | [http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410411 Contest on maximal flows] | ||
| + | |||
| + | <h3> | ||
| + | Apr,27. [http://judge2.vdi.mipt.ru/yudaev/english/MinSpanningTrees.pdf Spanning trees]. | ||
| + | </h3> | ||
| + | Cormen et al, ch 23.2 | ||
| + | <br/> | ||
| + | [http://olymp3.vdi.mipt.ru/cgi-bin/new-register?contest_id=410412 Contest on spanning trees] | ||
| + | |||
| + | <h3> | ||
| + | May, 4th. [http://judge2.vdi.mipt.ru/yudaev/english/grGames.pdf Games on graphs]. | ||
| + | </h3> | ||
| + | [http://olymp3.vdi.mipt.ru/cgi-bin/new-register?contest_id=410413 Contest on games] | ||
| + | |||
| + | <h3> | ||
| + | May, 11th. End of term contest. | ||
| + | </h3> | ||
| + | <p> | ||
| + | Topics: least-weight cycles, maximal flows, least weight trees, last common ancestor in a tree. | ||
| + | </p> | ||
Текущая версия на 15:16, 1 июня 2023
Содержание
- 1 Feb, 18. Recalling bfs and dfs.
- 2 Feb, 25. Balanced binary trees, heaps.
- 3 Mar, 4. Hash-tables , Rabin-Carpe algorithm
- 4 Mar, 9. Finite-state automata.
- 5 Mar,16. Dynamic programming.
- 6 Mar,23. Segment trees.
- 7 Mar,30. Semiterm control work.
- 8 Apr,6. Graph algorithms recalling.
- 9 Apr,13. Bellman-Ford and other shortest paths.
- 10 Apr,20. Maximal flow/minimal cut.
- 11 Apr,27. Spanning trees.
- 12 May, 4th. Games on graphs.
- 13 May, 11th. End of term contest.
Feb, 18. Recalling bfs and dfs.
Shortest paths, Dijkstra algorithm.
Feb, 25. Balanced binary trees, heaps.
Cormen et al: ch 6, 12Contest on binary trees and heaps
Mar, 4. Hash-tables , Rabin-Carpe algorithm
Cormen et al.: ch 10.3, 11, 32.2Mar, 9. Finite-state automata.
Cormen et al: ch 32.3,
Dramatic how-to about DFA minimisation
Also see
Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: principles, techniques, and tools, ch 3.9
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, ch 4.4.3
Mar,16. Dynamic programming.
Contest on dynamic programming
Mar,23. Segment trees.
Contest on segment and Fenwick trees
Mar,30. Semiterm control work.
Topics: hash tables, Fenwick trees, compound data structures, word correctness check.
Apr,6. Graph algorithms recalling.
Contest on basic graph algorithms
Apr,13. Bellman-Ford and other shortest paths.
Cormen et al, ch 24-25.
Contest on shortest paths
Apr,20. Maximal flow/minimal cut.
Cormen et al, ch 26.
Contest on maximal flows
Apr,27. Spanning trees.
Cormen et al, ch 23.2
Contest on spanning trees
May, 4th. Games on graphs.
May, 11th. End of term contest.
Topics: least-weight cycles, maximal flows, least weight trees, last common ancestor in a tree.
