Привет, Codeforces!
Это не совсем обычный пост от меня. Это не анонс новых фич или чемпионата, но воодушевлен я ничуть не меньше.
Рад сообщить, что с 29 января по 16 февраля 2018 г. буду читать курс "Advanced Algorithms and Data Structures" в Harbour.Space University (Испания, Барселона). Курс будет прочитан на английском языке. Слушателями этого курса будут не только студенты Harbour.Space. Курс открыт для всех желающих! Кто хочет присоединиться?
Обычно курсы приглашенных преподавателей в Harbour.Space предназначены исключительно для студентов университета. Я очень рад, что Harbour.Space в случае моего курса пошел на эксперимент, сделав курс открытым для желающих попасть именно на него. Стоимость обучения составит 1000 евро. Подать заявку можно по ссылке. В стоимость обучения не входит проживание в Барселоне и питание.
В моих планах — подробный рассказ о некоторых алгоритмах и структурах данных, много практических занятий и акцент не только на правильность, но и красоту и структура кода. Моя цель — сделать полезные и интересные занятия для как для всех кто хочет разбираться в фундаментальном CS, так и для интересующихся соревнованиями по программированию. Наверняка, у нас будет возможность познакомиться и пообщаться. Я с удовольствием поделюсь рассказами об истории Codeforces и планами по развитию.
Курс будет состоять из трёх недель обучения, по 5 учебных дней в каждой неделе. В программе — ежедневные лекции и практические занятия. Скучно точно не будет!
Вот предполагаемый план курса:
| Неделя | День | Тема |
|---|---|---|
| 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. |
Университет Harbour.Space расположен в Барселоне (Испания). Пользователям Codeforces университет Harbour.Space известен по активному участию в жизни сообщества спортивного программирования (сборы и партнерство с Codeforces в рамках образовательных раундов). Основная же деятельность университета — обучение (есть бакалаврские и магистерские программы) по направлениям:
- Maths as a Second Language
- Computer Science
- Data Science
- Cyber Security
- Interaction Design
- Digital Marketing
- High Tech Entrepreneurship
- FinTech
- BioTech
- Aerospace Engineering
- SuperCities UrbanTech
Mike Mirzayanov
