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.
- 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,
- 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
- 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