Просмотр исходного текста страницы Algo 2014 2

== Преподаватели ==

* Копелиович Сергей (burunduk30@gmail.com, vk.com/burunduk1)

* Колганов Роман (roman.kolganov@gmail.com, vk.com/rokolgan)

* Мишунин Александр (alexander.mishunin@gmail.com, vk.com/amishunin)

== Информация ==

[[algo_2014_2_groups | Деление на группы]]

[https://docs.google.com/spreadsheets/d/1rbAYiYp0UCttghJrG38PtP44tdFoj3yQjPGaqgrPz80/edit#gid=0 Результаты практики]

Дедлайны:

* практика: 8 дней (дедлайн в среду в 23:59)
* теория: 6 дней (дедлайн в понедельник в 23:59), после этого можно до вторника 23:59 исправлять замечания.

== Лекции ==

[http://acm.math.spbu.ru/~sk1/mm/au-lections/questions-algo-2015s.pdf Билеты к коллоквиуму]

[http://acm.math.spbu.ru/~sk1/mm/au-lections/questions-algo-2015s-grouped.pdf Билеты к коллоквиуму] (новая версия)

[http://yeputons.net/spbau/term2-algorithms-lectures.pdf Конспект] (набранный силами студентов)

* 02.10 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-02-10-BST.html BST]
* 02.17 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-02-17-BST.html BST]
* 02.21 (суббота) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-02-21-SegmentTree.html Дерево отрезков]
* 02.24 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-02-24-RMQ.html Двухмерные деревья, ScanLine]
* 03.03 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-03-03-RMQ-LCA.html RMQ & LCA]
* 03.04 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-03-04-RMQ-LCA.html Функции на путях дерева, MST за O(E)]
* 03.10 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-03-10-HLD.html Heavy-Light-Decomposition, Euler-Tour-Trees, LA]
* 03.18 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-03-18-Matching.html Паросочетания-1]
* 03.24 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-03-24-Flow.html Потоки-1]
* 03.25 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-03-25-Matching.html Паросочетания-2 и раскраски]
* 03.26 (четверг) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-03-26-Flow.html Потоки-2 (LR, Диниц)]
* 04.07 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-04-07-FlowMinCost.html Потоки-3 (mincost, Венгерка)] [http://acm.math.spbu.ru/~sk1/mm/lections/Goldberg_lections.pdf Конспект от Andrew Goldberg по потокам и mincost тоже]
* 04.08 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-04-08-Flow.html Потоки-4 (preflow-push, global cut)] [http://acm.math.spbu.ru/~sk1/mm/lections/2013-03-13-preflow-push.pdf Конспект от Burunduk1 про preflow-push] [http://acm.math.spbu.ru/~sk1/mm/lections/2015-04-08-preflow-push-2.pdf дополненная версия]
* 04.14 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-04-14-Strings.html Строки-1 (КМП, Z, Боер-Мур, Хеши, LCP)]
* 04.15 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-04-15-Strings.html Строки-2 (алгоритм Манакера, дерево палиндромов)] [http://arxiv.org/pdf/1404.5244v4.pdf (ещё про палиндромы)]
* 04.21 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-04-21-Trie.html Строки-3 (бор, суффиксное дерево, Ахо-Корасик)]
* 04.22 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-04-22-Ukkonen.html Строки-4 (Укконен)]
* 04.28 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-04-28-SufArray.html Строки-5 (Cуффиксный массив)]
* 04.29 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-04-29-Hashing.html Хеширование] [[Медиа:Algorithms-26-03-2015.pdf|(5-й курс Hash1)]][[Медиа:Algorithms-02-04-2015.pdf| (5-й курс Hash2)]] [http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf (Совершенное хеширование)]
* 05.05 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-05-05-Games.html Игры и битовое сжатие]
* 05.06 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-05-06-Bits.html Битовое сжатие и игры]
* 05.12 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-05-12-Gauss.html Гаусс и линейная алгебра]
* 05.13 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-05-13-mix.html Автоматы и изоморфизмы]
* 05.18 (вторник) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-05-19-FFT.pdf Фурье и BigInteger]
* 05.19 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-05-19-FFT.pdf Фурье и BigInteger]
* 05.27 (среда) [http://acm.math.spbu.ru/~sk1/mm/au-lections/2015-05-27-NumberTheory.html Теория чисел]

== Домашние задания ==


[http://acm.math.spbu.ru/~sk1/algo/input-output/fread_write.cpp.html Быстрое считывание в c++]

[http://acm.math.spbu.ru/~sk1/algo/memory.cpp.html Быстрая аллокация памяти в c++]

[https://www.dropbox.com/sh/j8ntjdb4cs7wyil/AABxbY5LzJilZ9q_sdPBJ09qa?dl=0 Решения и условия контестов]

* '''11 февраля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150211_au.dat результаты] [http://acm.math.spbu.ru/trains/150211_au.pdf условия]. Теор задачи: [[Медиа:15s_x1.pdf|AVL, treap, неявный ключ]].

* '''18 февраля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150218_au.dat результаты] [http://acm.math.spbu.ru/trains/150218_au.pdf условия]. Теор задачи: [[Медиа:15s_x2.pdf|STL, BST, RB, B, AA, Persistent]].

* '''25 февраля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150225_au.dat результаты] [http://acm.math.spbu.ru/trains/150225_au.pdf условия]. Теор задачи: [[Медиа:15s_x3.pdf|Дерево отрезков, ScanLine, 2D-деревья]].

* '''2 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150302_au.dat результаты] [http://acm.math.spbu.ru/trains/150302_au.pdf условия]. Специальный контест про 2D деревья.

* '''4 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150304_au.dat результаты] [http://acm.math.spbu.ru/trains/150304_au.pdf условия]. Теор задачи: [[Медиа:15s_x4.pdf|LCA, RMQ, Euler Tours]].

* '''11 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150311_au.dat результаты] [http://acm.math.spbu.ru/trains/150311_au.pdf условия]. Теор задачи: [[Медиа:15s_x5.pdf|Heavy-Light, Euler Tour Trees, задачи на деревьях]].

* '''18 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150318_au.dat результаты] [http://acm.math.spbu.ru/trains/150318_au.pdf условия]. Теор задачи: [[Медиа:15s_x6.pdf|Паросочетания]].

* '''25 марта''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150325_au.dat результаты] [http://acm.math.spbu.ru/trains/150325_au.pdf условия]. Теор задачи: [[Медиа:15s_x7.pdf|Потоки]].

* '''8 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150408_au.dat результаты] [http://acm.math.spbu.ru/trains/150408_au.pdf условия]. Теор задачи: [[Медиа:15s_x8.pdf|Mincost Потоки]].

* '''15 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150415_au.dat результаты] [http://acm.math.spbu.ru/trains/150415_au.pdf условия]. Теор задачи: [[Медиа:15s_x9.pdf|Строки: база]].

* '''22 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150422_au.dat результаты] [http://acm.math.spbu.ru/trains/150422_au.pdf условия]. Теор задачи: [[Медиа:15s_xA.pdf|Строки: бор и палниндромы]].

* '''29 апреля''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150429_au.dat результаты] [http://acm.math.spbu.ru/trains/150429_au.pdf условия]. Теор задачи: [[Медиа:15s_xB.pdf|Строки: суффиксные структуры]].

* '''6 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150506_au.dat результаты] [http://acm.math.spbu.ru/trains/150506_au.pdf условия]. Теор задачи: [[Медиа:15s_xC.pdf|битовое сжатие + ретроанализ + Гранди]].

* '''13 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150513_au.dat результаты] [http://acm.math.spbu.ru/trains/150513_au.pdf условия]. Теор задачи: [[Медиа:15s_xD.pdf|Гаусс]].

* '''20 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150520_au.dat результаты] [http://acm.math.spbu.ru/trains/150520_au.pdf условия]. Теор задачи: [[Медиа:15s_xE.pdf|Фурье]].

* '''27 мая''' Контест: [http://acm.math.spbu.ru/cgi-bin/monitor.pl/m150527_au.dat результаты] [http://acm.math.spbu.ru/trains/150527_au.pdf условия]. Теор задачи: [[Медиа:15s_xF.pdf|Теория чисел]].

[[Category:1 курс. Весна 2015]]