Структуры данных (21 сентября 2016)

1. [5 минут] Объявления
1. Перекличка (47)
2. TeX: кладите TeX, не кладите pdf.
3. TeX: не нужно коммитить, как Crtl+S каждые 30 секунд, есть парень у которого за 5 минут 10 коммитов.
4. TeX: проблемы с кодировкой. То чего не нужно делать − когда кодировка отобразилась не верно, пытаться копировать/менять текст, сохранять файл можно.
5. TeX: орфография
2. [5 минут] Реализация очереди, дека на циклическом динамическом массиве. Циклический список.
3. [10 минут] Разбор выражений. Пишем код для левой ассоциативности.
4. [30 минут] Время работы
1. На операцию (real time) t_i, в среднем (average time) m_i = (sum t_i) / n, амортизированное a_i = t_i + Δφ
2. Теорема о связи амортизированного и среднего времени
3. Примеры на амортизированное время (amortized time)
1. Пример с вектором
2. Пример со стеком PUSH, POP_K
3. Пример a² + b² = N : правильный потенциал = b
4. Пример a² + b² = N : пример неправильного потенциала, b²
4. Амортизация монетками, определение и равносильность.

1. [20 минут] Бинпоиск
1. Сортированный массив: sort(a, a+n)
2. Поиск позиции x в сортированном массиве. 3 ветки: x.
3. lower_bound (первый >= x) и upper_bound (первый >x),
4. Правильный бинпоиск: по инварианту. В l выполняется, в r не выполняется, r-l>1.
5. Вещественный бинпоиск. Поиск корня многочлена нечётной степени.
2. [15 минут] Два указателя + сортированный массив
1. Online решение : sort + bs (задача: поиск всех элементов массива B в массиве A)
2. Offline решение : sort + sort + два указателя
3. Пересечение множеств (и мультимножеств!), C++ set_intersection. Две версии кода: while и for.
4. Ещё задачи на два указателя и множества: merge, union, set_difference.
3. [15 минут] Хеш-таблица
1. HashSet на списках: vector<int> h[M]; hash(x), vecor::push_back, vector::find
2. Как выбрать функцию hash? Самая простая hash(x) = x % M
3. C++ : unordered_set<int> s(N), unordered_map<int,int> m(N), MyHash { size_t operator() ( T t ); }