Algorithm Curriculum

Collection of the most useful and well-known algorithms

Recursion

• All permutations of the set
• Queen placement on the chessboard

Dynamic programming

• Max sum subarray (1D DP)

Graphs

Book list

• A Laaksonen "Competitive Programmer's Handbook" https://cses.fi/book.pdf, 2018
• А. Шень "Программирование: теоремы и задачи", 2004
• Gayle McDonell "Cracking Code Interview", 2009

To Do

Backtracking

- queen placement puzzle

Numeric algorithms

- permutation generations without extra memory

Graphs

1. Shortest path

• Bellman-Ford's algorithm
• Dijkstra's
• Floyd-Warshell's

1. Minimal Spanning Tree

• Prim's algoritm
• Kruskal's algorithm

Graphs Extended

• Поиск всех путей
• Построить дополнение
• Компоненты слабой связности
• Компоненты сильной связности
• Проверка изоморфизма
• Максимальный поток (preflow push)
• Максимальный поток dinic
• Эйлеров путь
• Эйлеров цикл
• Гамильтонов цикл
• Разбиение на доли
• Центр, радиус, диаметр
• Поиск цикла
• Мосты
• Точки сочленения
• Степени вершин
• Топологическая сортировка
• Раскраска (dsatur)

Strings

Editing distance

Substring finding

• Knut

Parallel bit lookup

1. Hamming distance
2. Black sub-grids
3. Number or reachable vertices in a graphs