I think the most common thing to implement is the perceptron algorithm from scratch.

I would recommend Pattern Recognition and Machine Learning by Christopher M. Bishop. It assumes no previous knowledge of pattern recognition or machine learning.