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

Версия 15:34, 4 февраля 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; 
 }

Семинар 3.02

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

Решить задачу: Алфавит из всех маленьких латинских букв и пробела закодирован числами следующим способом:

 'a' -> 1
 'b' -> 2
 'c' -> 3
 ...
 'z' -> 26
 ' ' -> 27

На вход программы подается строка из цифр. Нужно посчитать, сколькими способами можно раскодировать эту строку. Решить программу нужно при помощи динамического программирования. К решению нужно написать стресс тест, в котором ответ программы, посчитанный при помощи динамического программирования сравнивается с ответом, полученным при помощи рекурсивного brute force решения. Для этого также нужно реализовать рекурсивное решение. Решенную задачу нужно отправить на ревью на адрес a.v.dorogush@gmail.com