Advance_Algorithm_HomeWork

A Homework repository of Advance Algorithm course at University of Padova (Unipd)

There are 3 homeworks, each homework discussed some problems or algorithms that we have to solve.

1. MST:

We were to implement 3 algo; Prims,Kruskal Naive, Kruskal Union Find on a given dataset(list of graphs with increasing number of vertex), and at the end we had to compare them and compute their complexities,

2. TSP:

For TSP, we were given GEO, EUC-2D based data, for which we had to implement 2 Constructive Heuristics(Random Insrtion and Nearest Neighbour) and a 2-Approx algo. And we had to compute error by calculating this equation approxSol-optimalSol/optimalSol

3. Min-Cut:

For min-cut, we implemented 2 algorithm's 1. Stoer and Wagner's deterministic algorithm. 2. Karger and Stein's randomized algorithm. and compared the result and visualzied