Алгоритмы 1MIT осень 2018

Материал из CSC Wiki
Перейти к:навигация, поиск

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

  • Копелиович Сергей Владимирович (burunduk30@gmail.com, vk.com/burunduk1)

Софт, примеры, справка

Информация

Результаты практики

Дедлайны:

  • практика, контест: воскресенье 23.59
  • теория в tex: среда 23:59, исправления (и доп задачи) до пятницы 23:59

Вопросы к экзамену.

Лекции

  • Конспект от Серёжи [1]
  • 29 сентября. Код стека с минимумом и очереди с минимумом за неамортизированное O(1) тут.
  • 6 октября. На лекции про QuickSort упоминалось, что функцию partition можно написать так, чтобы она работала с равными элементами. Видимо, для этого надо использовать другой алгоритм, код тут. Ещё можно почитать тут Dutch national flag problem. Видимо, на самом деле никто этого не делает, а вместо этого используют алгоритм, который неправильно работает с равными элементами, потому что на случайном тесте время работы оказывается лучше. Всё равно, если глубина рекурсии оказывается большой, мы переходим на HeapSort, так что это ни на что не влияет.
  • 3 ноября. На следующем занятии будут оптимизация Кнута и оптимизация Divide and Conquer. Можно почитать обсуждение на codeforces. Про оптимизацию Кнута можно почитать в конспекте Серёжи. Правда, обычно оптимизацию Кнута иллюстрируют на примере другой задачи, про это можно прочитать в этой статье.

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

  • 24 ноября. DFS