Hi, Codeforces!
I am glad to announce and invite you to the second launch of my course on algorithms and data structures.
On 7-25 of January, 2019, I will be giving the course "Advanced Algorithms and Data Structures" at Harbour.Space University (Barcelona, Spain). It will be in English, and is not limited to Harbour.Space students — anyone is welcome! Who wants to join?
This course isn't just for Harbour.Space students, it is also open to Codeforces participants, who will be offered a special price, 1000 EUR. The cost does not include travel or accommodation.
The curriculum will include a breakdown of algorithms and data structures, a lot of practical exercises, and emphasis not only on the correctness, but also the beauty and structure of the code. My goal is to make classes that are useful and interesting for both those who want to understand the fundamental CS, and for those interested in programming competitions. And of course, we will have the opportunity to meet and talk. I look forward to share stories about the history of Codeforces and future development plans.
The course will consist of three weeks of intensive training, 5 days in each week, 3 hours per day. The program includes daily lectures and practical exercises. It will not be boring for sure!
Here is the expected course outline:
| Week | Day | Topics |
|---|---|---|
| 1 | 1 | Heap data structure, heap properties and operations. HeapSort. Priority queue. Other heap applications. Mergeable heaps: binomial heap, pairing heap, randomised meldable heap. |
| 1 | 2 | Fenwick tree. Description and motivation. Implementation of Fenwick tree. Generalisation for higher dimensions. Skip list data structure. Implementation details. Indexable skiplist. |
| 1 | 3 | Segment trees. Top-down implementation. Bottom-up implementation. Segment trees applications. Persistent data structures. Persistent stack, persistent array. Persistent Fenwick and segment trees. |
| 1 | 4 | Cartesian trees, treap data structure. Merge and split operations. Treap implementation in detail. Treap applications. |
| 1 | 5 | Treaps with implicit keys. Ropes. Segment reverse operation. Examples of problems. |
| 2 | 6 | Introduction to strings. String searching (matching) problem. Pattern pre processings. Z-function, prefix-function. Their applications. Knuth–Morris–Pratt algorithm. Matching finite state machine. |
| 2 | 7 | Multiple pattern matching. Trie data structure. Aho-Corasick algorithm. Implementation details. Dynamic programming on a trie. |
| 2 | 8 | String hashing. Rabin-Karp algorithm. Fast substrings comparison with hashes. Suffix array. LCP array. Efficient construction algorithm. Applications. |
| 2 | 9 | Suffix tree. Ukkonen's algorithm. Suffix tree construction from LCP array. Suffix tree applications. |
| 2 | 10 | Suffix automaton. Size bounds. Linear Algorithm. Using suffix automata as an index for approximate string searches. |
| 3 | 11 | Introduction to automata theory. Formal languages. Context-free languages. Formal grammars. Context-free grammars. NFA, DFA, convert NFA to DFA. Build automaton by regular expression. |
| 3 | 12 | LL(1) parser. Arithmetic expressions parsing. Shunting-yard algorithm. Simplified Pascal language parsing and interpretation. |
| 3 | 13 | Algorithms for traversing a graph. DFS. Properties. DFS search tree. Edges classification. Linear bridge-finding algorithm. Linear articulation points finding algorithm. Strongly connected components. Tarjan's strongly connected components algorithm. |
| 3 | 14 | Tree problems. Bottom-up approach. LCA problem. LCA algorithms. |
| 3 | 15 | Bipartite graphs. König’s criterion. Problems: maximum matching, minimum edge cover, maximum independent vertex set, minimum vertex cover. Connection of the problems. Berge's lemma. Kuhn algorithm. Kuhn algorithm properties. Minimal vertex cover by maximum matching. Cover DAG by minimal number of paths. |
Harbor.Space University is located in Barcelona (Spain). For users of Codeforces, Harbour.Space is known for active participation in the life of the community of sports programming (partnership with Codeforces in the framework of Educational Rounds). The main activity of the university is teaching (there are bachelor's and master's programs) in the following areas:
- Maths as a Second Language
- Computer Science
- Data Science
- Cyber Security
- Interaction Design
- Digital Marketing
- High Tech Entrepreneurship
- FinTech
- BioTech
- Aerospace Engineering
- SuperCities UrbanTech
Harbour.Space is also proud to announce the Scholarships to study Msc in Robotics in Barcelona. Follow this link for more information about the opportunity and application process.
Register for my upcoming course via this link.
i always wanted to attend such educative sessions .... is it possible to do a live streaming of lectures (or recording ) ?? many of us cannot make it to be present at the spot ...and i think main motive of such programmes is to spread cp enthusiasm...
It would be slightly feasible if you are willing to pay for everybody who is interested (1000euro/person).
being poor is sad xD
Mike, this sounds great! I can't make it this time, but can I somehow subscribe so I woulnd't miss the next one?