M1 Artificial Intelligence · semester 7 · APP

Algorithmic Problem Solving

Taught by apprentissage par problème: four projects, each worked by a group across several sessions. Implementing one is optional, which is why all four have a folder waiting, and why not all of them hold code yet.

Four projects, four techniques

APP1 A maze, generated and solved A random maze built by recursive division is a binary tree in disguise: generating it is divide and conquer, solving it is a traversal to the one path out. APP2 Candy Crush Where a greedy match runs out of good moves, and dynamic programming has to take its place. APP3 School scheduling Turning a timetable into a maximum-flow problem, and reading the answer back off its minimum cut. APP4 Hole drilling A minimum spanning tree standing in for the shortest tour, with a proven 2-approximation on how far it can land from optimal.

Reading it

Source The folder on GitHub Four project folders, each holding its own record once the work is done. README The course README The full table of projects, the technique each is solved with, and what ships as code.

The project subjects, and the C skeleton provided with the maze project, are not redistributed here. Each project keeps its handout on disk, out of the repository; what is committed is my own work.