Algorithms, Part I на Coursera

О курсе

На Сoursera есть хороший курс по алгоритмам и структурам данных для начинающих и повторяющих. Он на английском языке, но это не должно быть большой проблемой, так как лекции технические и основная часть слов будет знакома любому программисту.

Авторы курса Кевин Уэйн (Kevin Wayne) и Роберт Седжвик (Robert Sedgewick).

Плюсы

• Курс бесплатен и постоянно перезапускается (его можно проходить снова и снова);
• Все лекции можно найти также и на Youtube;
• Много интересных практических заданий;
• Замечательная система проверки, требующая сдавать довольно хорошо отлаженный код;
• Для углубленного изучения материала можно взять книгу авторов.

Минусы

• Проблемы со звуком в лекциях. Лектор часто и сильно кашляет в микрофон. Берегите уши;
• Довольно поверхностное покрытие материала в лекциях (можно компенсировать книгой авторов);
• Несоответствие лекций и заданий. В лекциях описываются алгоритмы и структуры данных;
• Обещается, что мы будем реализовывать их сами. Вместо этого же приходится использовать структуры данных, написанные авторами курса для решения прикладных задач.

Вывод

Хороший курс. Рекомендую всем интересующимся программированием, алгоритмами и структурами данных.

Стандартная модель хэш-функций

Хэш-функции имеют некоторое внутреннее состояние, и функция mix используется для перемешивания внутреннего состояния. Другая функция, combine, используется для комбинации входных блоков с внутренним состоянием. Иногда эти функции объединяют в одну, что не меняет их сути. Потом состояние проходит постобработку (например, обрезается до нужной длины хэша). И все, хэш готов.

initialize the internal state;
for (each block in input)
{
  combine (the internal state, the current input block);
  mix (the internal state);
}
value = postprocess (the internal state);
return value;

Почти все известные хэш-функции построены по этой модели за исключением MD4 и некоторых других.