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

1. [5 минут] Реализация очереди, дека на циклическом динамическом массиве. Циклический список.
2. [10 минут] Разбор выражений. Пишем код для левой ассоциативности.


3. [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. Амортизация монетками, определение и равносильность.


4. [20 минут] Бинпоиск
1. Сортированный массив: sort(a, a+n)
2. Поиск позиции x в сортированном массиве. 3 ветки: x.
3. lower_bound (первый >= x) и upper_bound (первый >x),
4. Правильный бинпоиск: по инварианту. В l выполняется, в r не выполняется, r-l>1.
5. Вещественный бинпоиск. Поиск корня многочлена нечётной степени.

1. [15 минут] Два указателя + сортированный массив
1. Online решение : sort + bs (задача: поиск всех элементов массива B в массиве A)
2. Offline решение : sort + sort + два указателя
3. Пересечение множеств (и мультимножеств!), C++ set_intersection. Две версии кода: while и for.
4. Ещё задачи на два указателя и множества: merge, union, set_difference.


2. [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 ); }
3. [15 минут] Хеш-таблица
1. Чем хеш-таблица лучше масива? поиск и удаление за O(1).
2. Умеем Add, Del, Find. Интерфейсы HashSet, HashMap. Решение задачи про два указателя хеш-таблицей.
3. Открытая адресация: i = hash(x), while (h[i] && h[i] != x) i++;
4. Сравнение открытой и списков: открытая быстрее, из списков проще удалять. Удаление из открытой: просто помечаем, когда помеченных слишком много, перестроим таблицу.