Семинар 10.02 Подгруппа 106-2

Домашнее задание на следующий семинар.

(*) Реализовать алгоритм поиска расстояния Левенштейна за N * M с использованием O(N + M) памяти, как было рассказано на семинаре. Здесь N, M - длины строк. Реализовать стресс тест для данного решения с использованием рекурсивного алгоритма без запоминания.

(*) Запрограммировать решение задачи, разобранной на семинаре. Дан вектор натуральных чисел s1, s2, ..., sn, где si <= K для любого i. n = 1000, K = 100. Найти разбиение этих чисел на две части, что |S1 - S2| будет минимально, где S1 - сумма элементов в первой части, S2 - сумма элементов во второй части. Каждый элемент должен быть отнесен к ровно одной из частей.

Каждую решенную задачу нужно отправить на ревью. В тексте письма нужно написать Review needed, если хотите, чтобы я сделала ревью кода.

Также будет обязательное домашнее задание на всю неделю. Оно будет опубликовано позже.