For CSC 549: Advanced Algorithms, we chose one of the NP complete problems discussed in class to write a paper on and give a presentation about. I have always been interested in the Traveling Salesperson Problem, so I chose Undirected Hamiltonian Circuit and focused my research on TSP (which is basically a weighted optimization version of UHC).

I wanted to learn more about approximation algorithms for TSP, so I chose to learn about the Christofides Algorithm. I had trouble understanding the algorithm, so I decided to implement it a visualizer in Python that runs the algorithm step by step, using NetworkX for graph operations and Pygame for visuals. Since I was giving a presentation, I figured this would be a great way to explain the algorithm and hopefully give people an intuition behind how it works in the limited time I had to present.

I've linked the paper I wrote for the class below. It goes into more detail about the algorithm itself, and also provides a proof that UHC is NP complete.