Skip to content

This repository contains three challenges presented on the course of Advanced Algorithms and Parallel Programming (095946) at Politecnico di Milano.

Notifications You must be signed in to change notification settings

Nexer8/Advanced_Algorithms_and_Parallel_Programming

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Advanced Algorithms and Parallel Programming Challenges

This repository contains three challenges from the Advanced Algorithms and Parallel Programming (095946) course at Politecnico di Milano.

Challenges

MinCut Karger + Karger&Stein

  • 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. ✅

Merge Sort Parallelization with MPI

  • 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. ✅

Parallel Scan Pattern with OpenMP

  • 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). ✅

About

This repository contains three challenges presented on the course of Advanced Algorithms and Parallel Programming (095946) at Politecnico di Milano.

Topics

Resources

Stars

Watchers

Forks