# *********** University proejct in C++ ********************

Budget $250-750 USD

###############################

Sequential algorithm implementation

Read the task carefully. Study the algorithm description in the paper and read the recommended or available literature. Design a proper algorithm to solve the problem.

Note, you have to extend the sequential algorithm into the parallel one. So this algorithm should be the core of your parallel solution finally.

Parallel algorithm implementation

Extend your sequential solution of the given problem into the parallel one

Implement the parallel algorithm on the MPI (Message Passing Interface)

#####################################

:Magic square

Problem MAS: magic square

Input data:

n = integer number, n>3

M = set of numbers {1,..,n2}

p = number of processors

Definition

S=n(1+n2)/2

Task:

Find an arrangement of the numbers from set M in an n x n matrix, with each number occurring exactly once, and such that the sum of the entries of any row, any column, or any main diagonal is S. This arrangement is called a magic square.

Output of the algorithm:

Row-wise listing of a magic square arrangement.

Sequential algorithm:(this implementation need to be done in two weeks deadline is 12 october.)

The sequential algorithm is of type SB-DFS with the search depth bounded by n2. An internal state is a permutation of the numbers from set M in an n x n matrix. Possible final states are permutations of numbers from set M that satisfy the property of a magic square. A backtrack is taken if at least one row, column, or diagonal has sum not equal to S. The algorithm terminates after finding the first solution. It always exists.

Solution for n=3. Sums of all rows, columns, and diagonals are 15.

Parallel algorithm:

The parallel algorithm is of type Master-Slave. Starting configurations are squares with the first s numbers placed row-wise, 2 ⇐ s ⇐ max(2,upper(10/n)).

******************************************************

******************************************************

The tasks need to follow two implementation rule:sequential algorithm and [url removed, login to view] mean that the sequntinal need to get the parallel

#####################################################################################################

Sequential algorithms for depth-first-search (Depth-first search, DFS)

Algorithm DFS searchs state space and uses stack for it. Final state is state, which has no succesors. All othre states we call middle states. Aim of DFS is to find final state, which satisfies solution conditions, [url removed, login to view] final state.

DFS algorithms can differ by the following ideas:

conditions for finishing DFS

amount of searched space

depth of searched state tree is restricted

Conditions for finishing DFS

There are several conditions for finishing DFS.

In your semestral projects you will meet the following 3 examples: DFS terminates after finding

first any solution. We call it DFS with simple backtrack.

solution with minimal price. We call it Branch-and-bound DFS.

solution in minimal depth of state tree. This is special case of Branch-and-bound DFS.

1. DFS with simple backtrack (SB-DFS)

Task is to find first available final state (ie. first solution). In case that there are lot of solutions, SB-DFS must not find the optimal one. SB-DFS is useful if all solutions have the same price or length to them is same. Backtrack is done from wrong final state (state which has no successors and does not satisfy solution conditions) or from middle state which does not satisfy solution conditions and its expandion cannot go to right final state. This middle state we will call wrong middle state. If expansions of middle states can go to right final state, we call them them right middle states.

2. Branch-and-bound DFS (BB-DFS)

*************** Continue in attached file ***************

Please read it!