Algorithms and data structures III

Feb, 18. Recalling bfs and dfs.

Shortest paths, Dijkstra algorithm.

Contest on Dijkstra

Feb, 25. Balanced binary trees, heaps.

Cormen et al: ch 6, 12

Contest on binary trees and heaps

Mar, 4. Hash-tables , Rabin-Carpe algorithm

Cormen et al.: ch 10.3, 11, 32.2

Contest on hash tables

Mar, 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

Contest on automata

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.

Contest on games

May, 11th. End of term contest.

Topics: least-weight cycles, maximal flows, least weight trees, last common ancestor in a tree.