courses:a4b36acm2:2017_ls:links

Zájemcům mohu zapůjčit/dodat v elektronické podobě:

[Sedgewick] Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching, Third Edition

[CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009,

Text processing trees

.

2.3.

Trie

MIT Advanced Data Structures, Lecture 16 Watch the video
http://javabypatel.blogspot.cz/2015/07/trie-datastructure-explanation-and-applications.html
[Sedgewick], kap. 15.2.;
https://www.cs.umd.edu/class/fall2005/cmsc132/lecs/lec29.ppt
www.cs.nyu.edu/~melamed/courses/102/lectures/Tries.ppt

Suffix trie

MIT Advanced Data Structures, Lecture 16 Watch the video
http://www.allisons.org/ll/AlgDS/Tree/Suffix/ + Interactive
https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/suffixtrees.pdf

16.3.

binary trie

http://opendatastructures.org/ods-java/13_1_BinaryTrie_digital_sea.html
http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec15/lec15-12.html#pgfId-969225
R. Sedgewick: Algorithms in C + +, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, 3rd Edition, Chapter 15.2. (Zdroj viz výše)
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

radix trie

‘Radix tree’ = ‘radix trie’ = ‘patricia trie’: compressed trie, every internal node has at least two leaves.

http://cglab.ca/~morin/teaching/5408/notes/strings.pdf
https://maitesin.github.io/Prefix_trees/
R. Sedgewick: Algorithms in C + +, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, 3rd Edition, Chapter 15.3. (Zdroj viz výše)
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Pattern Matching

Aho-Corasick

Slides step-by-step https://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf
Geeks for Geeks: http://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/
Wikipedia https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
Original paper http://cr.yp.to/bib/1975/aho.pdf

Knuth-Morris-Pratt

Wing-Kai Hon: http://www.cs.nthu.edu.tw/~wkhon/algo08-tutorials/tutorial-kmp.pdf
David Eppstein: http://www.ics.uci.edu/~eppstein/161/960227.html
Check online: http://whocouldthat.be/visualizing-string-matching/
FH Flensburg: http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm

Boyer-Moore

Rabin-Karp

Finite automata (many variants)

More trees

Segment tree (geometry)

Treap

To implement

cycle detection ( hare and tortoise )

maximum matching in bipartite graphs (weighted and unweighted)

maximum flow (Ford-Fulkerson, Dinic )

convex hull

sweep line

Even more?

Huffman coding (static and dynamic )

Minimax, Alpha-beta pruning

Google Page rank

Other sources

http://cseweb.ucsd.edu/~kube/cls/100/lectures.html