Разделяй и властвуй. Задачи на прямой
Алгоритмы и структуры данных, часть 1


Что: Семинар
Когда: Пятница, 30 сентября 2016, 18:30–20:00
Где: Таймс, 4 этаж

Описание

Для более полного понимания происходящего можно (но не обязательно!) пройти 5.2.Умножение чисел

  • Подотрезок максимальной суммы
  • Экстремальные точки на прямой (например, минимизируем сумму расстояний до остальных, сумму квадратов расстояний до остальных)
  • Две ближайшие точки в 2D, в 3D за \(O(n \log n)\)

Материалы

Подробный план и код, написанный на лекции

http://acm.math.spbu.ru/~sk1/courses/1617f_cscenter/plans/2016-09-30.html

Разбор задач про экстремальные точки с пар Академического Университета

http://acm.math.spbu.ru/~sk1/courses/1617f_cscenter/plans/2016-09-30/151005.pdf