План лекции:

1) Числа Фибоначчи

2) Как оценивать скорость работы программы, O-нотация

3) O(наивного рассчета чисел Фибоначчи) и O(быстрого алгоритма)

4) Поиск наибольшего общего знаменателя, алгоритм Евклида

5) Метод разделяй и властвуй (двоичный поиск, сортировка слиянием)

6) Графы (клубок ниток - поиск в глубину, распространяем волны - поиск в ширину)

7) Динамическое программирование (сумма на подотрезке, максимум на подотрезке, наибольшая возрастающая подпоследовательность)

Хорошая книга по алгоритмам - Алгоритмы (С. Дасгупта, Х. Пападимитриу, У. Вазирани).

Часть алгоритмов представлена ввиде проверяемых онлайн задач здесь - https://informatics.msk.ru/moodle/.

Большой архив онлайн задач доступен на CodeForces (справа есть фильтр задач по тематическим тегам и сложности).