http://wiki.atp-fivt.org/api.php?action=feedcontributions&feedformat=atom&user=Ariel
Public ATP Wiki - Вклад участника [ru]
2026-04-11T02:30:32Z
Вклад участника
MediaWiki 1.30.0
http://wiki.atp-fivt.org/index.php?title=Algorithms_and_data_structures_III&diff=2023
Algorithms and data structures III
2023-06-01T12:16:55Z
<p>Ariel: Page creation</p>
<hr />
<div><br />
<br />
<h3><br />
Feb, 18. <br />
Recalling [http://judge2.vdi.mipt.ru/yudaev/english/1-bfs.pptx bfs] and [http://judge2.vdi.mipt.ru/yudaev/english/2-DFS.pdf dfs]. <br />
</h3><br />
[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]. <br />
<br />
[https://contest.yandex.ru/contest/21550/enter/ Contest on Dijkstra]<br />
<br />
<h3><br />
Feb, 25.<br />
Balanced binary trees, heaps.<br />
</h3> Cormen et al: ch 6, 12 <br />
[http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410404 Contest on binary trees and heaps] <br />
<br />
<h3><br />
Mar, 4.<br />
[http://judge2.vdi.mipt.ru/yudaev/english/hashing.ppt Hash-tables] , [http://judge2.vdi.mipt.ru/yudaev/english/Rabin-Karp.ppt Rabin-Carpe algorithm]<br />
</h3> Cormen et al.: ch 10.3, 11, 32.2<br />
<br />
[http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410405 Contest on hash tables]<br />
<br />
<h3><br />
Mar, 9. [http://judge2.vdi.mipt.ru/yudaev/english/FiniteAutomata.ppt Finite-state automata].<br />
</h3> <br />
Cormen et al: ch 32.3,<br />
<br />
[https://www.gatevidyalay.com/minimization-of-dfa-minimize-dfa-example/ Dramatic how-to about DFA minimisation]<br />
Also see <br/><br />
Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: principles, techniques, and tools, ch 3.9<br />
<br/>John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, ch 4.4.3<br />
<br />
[http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410406 Contest on automata]<br />
<br />
<h3><br />
Mar,16. Dynamic programming. <br />
</h3><br />
[http://olymp3.vdi.mipt.ru/cgi-bin/new-register?contest_id=410407 Contest on dynamic programming]<br />
<br />
<h3><br />
Mar,23. [http://judge2.vdi.mipt.ru/yudaev/english/fenwick.ppt Segment trees]. <br />
</h3><br />
[http://olymp3.vdi.mipt.ru/cgi-bin/new-register?contest_id=410408 Contest on segment and Fenwick trees]<br />
<br />
<h3><br />
Mar,30. Semiterm control work. <br />
</h3><br />
<br />
Topics: hash tables, Fenwick trees, compound data structures, word correctness check. <br />
<br />
<br />
<br />
<h3><br />
Apr,6. Graph algorithms recalling. <br />
</h3><br />
[http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410403 Contest on basic graph algorithms]<br />
<br />
<h3><br />
Apr,13. [http://judge2.vdi.mipt.ru/yudaev/english/8-dynamic-programing-shortest-paths.pdf Bellman-Ford] and other shortest paths. <br />
</h3><br />
Cormen et al, ch 24-25.<br />
<br/><br />
[http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410410 Contest on shortest paths]<br />
<br />
<h3><br />
Apr,20. [http://judge2.vdi.mipt.ru/yudaev/english/flowcut.pdf Maximal flow]/minimal cut. <br />
</h3><br />
Cormen et al, ch 26.<br />
<br/><br />
[http://judge2.vdi.mipt.ru/cgi-bin/new-register?contest_id=410411 Contest on maximal flows]<br />
<br />
<h3><br />
Apr,27. [http://judge2.vdi.mipt.ru/yudaev/english/MinSpanningTrees.pdf Spanning trees]. <br />
</h3><br />
Cormen et al, ch 23.2<br />
<br/><br />
[http://olymp3.vdi.mipt.ru/cgi-bin/new-register?contest_id=410412 Contest on spanning trees]<br />
<br />
<h3><br />
May, 4th. [http://judge2.vdi.mipt.ru/yudaev/english/grGames.pdf Games on graphs]. <br />
</h3><br />
[http://olymp3.vdi.mipt.ru/cgi-bin/new-register?contest_id=410413 Contest on games]<br />
<br />
<h3><br />
May, 11th. End of term contest. <br />
</h3><br />
<p><br />
Topics: least-weight cycles, maximal flows, least weight trees, last common ancestor in a tree. <br />
</p></div>
Ariel