This repository contains three challenges from the Advanced Algorithms and Parallel Programming (095946) course at Politecnico di Milano.
- Analyze the asymptotic complexity of karger_union_find and of karger_stein_union_find with Google benchmarking library. ✅
- Reimplement/optimize the two MinCut procedures with a running time better than the reference code. ✅
- Implement a general approach for distributing the work of merge sort over multiple processes. ✅
- The provided merging algorithm must not be modified, nor should the vector generators. ✅
- Test the correctness of your algorithm against all three provided vectors (1024, 729, 997 elements). ✅
- Test the correctness of your algorithm when run with 2, 3, 5 processes. ✅
- Evaluate the load balance on the processes in the different configurations, as well as the overall computation time of the program. ✅
- Implement a scan function that adds to each element of the input vector all the previous elements in the same vector. ✅
- The implementation should use an upsweep + downsweep approach in order to efficiently compute the results in a parallel execution. ✅
- Implement a second function for checking the correctness of the result if the original vector of size n contained, in order, all the values from 0 to n-1. ✅
- After obtaining a working parallel implementation, evaluate the speedup offered by each parallel construct in your solution (tip: perform evaluation on a reasonably large vector). ✅