Алгоритмы и структуры данных. Подгруппа 106-2 — различия между версиями

Версия 10:44, 31 января 2015

Семинар 29.01

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

1. Реализовать вычисление полинома в точке при помощи схемы Горнера и без нее. Интерфейс алгоритма может быть, например, такой:

 int CalculatePolynomial(const vector<int>& coefficients, int value);

Написать тесты для обоих функций. В стресс тесте можно сравнивать значения полиномов, посчитанные двумя функциями. Сравнить быстродействие алгоритмов при помощи clock() из <ctime>.

2. Реализовать быстрое возведение в степень и написать тесты для него.

3. Реализовать подсчет k-ой статистики за гарантированное линейное время. Написать тесты. Сравнить быстродействие этого алгоритма с QuickSelect, который вы писали после прошлого семинара.

Для каждой задачки нужно создать ревью. Тесты и сравнение быстродействия нужно писать в одном ревью. Функция main() в этом случае будет выглядеть примерно так:

 void Test() {
   CheckManualTests();
   CheckCornerCases();
   RunStressTest();
 }

 void CompareSpeed() {
   // cout time to run each algorithm.
 }

 int main() {
   Test();
   CompareSpeed();
   return 0; 
 }