Due date: Wednesday, November 19, 2020.

In this homework we'll implement an algorithm that generates an ideal playlist of songs. The idea is that given a list of songs, we would like to produce a shuffle for this list such that songs that are played one after another present some similarities. We would also like to optimize the playlist in this respect.

Let's assume that we have some attributes for the songs, such as tempo, the key, the genre, the low/high frequency balance, etc. If each attribute is a numerical value, then each song is represented by a vector. We can compute the similarity between the songs as the Euclidian distance between the two vectors, smaller values making the songs more similar. Then we would like to find a shuffle of the list of songs such that minimizes the sum of distances between each song in the list and the next.

Download the following files:
Makefile
main.cc
process.cc
process.h
songs.cc
songs.h

Compile the program with the command make and run it with
mpirun -np # genius
where # is the number of processes, which should be equal to the number of songs.

The songs will be represented as points in a two-dimensional space where the coordinates represent some fictional attributes. The songs will be generated randomly with a title composed of 4 random words selected from some global arrays. A title will contain a starting word, a verb, a preposition and a noun. The attributes are random values between 0 and 1.

The goal is to come up with a shuffling of the songs such that the distance between each song and the next in the list is minimal. We will solve this problem with a brute force algorithm that goes through all the permutations of the list of songs and for each of them, it adds the distances between each song and the next. Then it compares this value with a minimum, which is updated if the list at hand is better.

The list of songs is generated randomly as described above. The number of songs will be assumed to be the same as the number of processes.

We will implement this as a nearly embarrassingly parallel application. The master will generate the list of songs and communicate their number and the coordinates to the workers. Each process will generate a subset of the total number of permutations independently, and send the one minimizing the total distance to the master at the end. The master will output the permutation it receives minimizing the distance.

Note that this problem is equivalent to the Traveling Salesman Problem.

Implement the following four functions in the file process.cc:

• Worker function. This function must first call the function creating the data structure that can be used to receive data of type Song. Then it should receive the number of songs and the array of songs from the master.
  
  After that, it must generate the initial permutation based on the id. We will assume that we'll run the program with a number of processes equal to the number of songs, so that the process i will generate all the permutations starting with the value i.
  
  After that, the worker should call the function that generates permutations in a similar way to the master. At the end it should send the minimal shuffle to the master.
  
  
• generate_permutations. This should generate all the permutations allocated to this process. The function should evaluate the total distance between songs in the starting permutation and store it in a local variable. Then it should generate new permutations until the first element (a[0]) has changed. For each of them, it should compare the sum of the distances between songs to the stored one, and if the new one is smaller, copy the permutation into the mina array. At the end it should also return the minimal distance.
  
  
• collect_results. This function should receive the minimum permutation and the distance between songs in it from each worker and compute the minimum of shuffle of all the received ones. A local array will be needed to receive the permutations.
  
  
• distance_songs. This function should compute the distance between adjacent songs in a playlist.

Explanations for each of them are also given in the comments in the source file.

Upload: to Canvas, Assignments, Homework 11, all the files that you modify, add, create.