算法作业代写 Sorting algorithms代写

Sorting algorithms

算法作业代写 Please read the material carefully and then solve the three tasks given at the end of this document. Be clear and neat. Return…

Please read the material carefully and then solve the three tasks given at the end of this document. Be clear and neat. Return a single PDF file.

Grading. The total number of points earned from the tasks is divided by 2 and rounded upwards to get an integer between 0 and 4.

Bidirected search on permutations 算法作业代写

The concept of a permutation has numerous applications in computer science, for example, in the analysis of sorting algorithms and in implementations of distributed systems.

Formally, a permutation is a bijection from a set onto itself. For simplicity, let us restrict ourselves to the sets [n] := {1, 2, . . . , n} of the first n positive integers, and denote by S_n the set of all permutations on [n].  It is often convenient to represent a permutation σ  by the n-tuple (σ(1), σ(2), . . . , σ(n)).

Swapping two elements of a permutation yields another permutation. For i, j ∈ [n] let T_ij : S_n → S_n  be the mapping that swaps the images of i and j, that is, if σ  ∈ S_n, then τ  := T_ij(σ) is given by τ (i) = σ(j), τ (j) = σ(i), and τ (k) = σ(k) if i /= k /= j.

Example.   Let σ = (2, 4, 3, 1). Then T₁₃(σ) = (3, 4, 2, 1). 算法作业代写

Now, consider allowing only swaps with some pairs (i, j). For any integer d ≥ 0, let

P_d := (i, j) ∈ [n] × [n] : i = j or d ≤ j − i ≤ n − d   .

Say that a permutation τ is (d, l)-reachable from σ if there are (i₁, j₁), (i₂, j₂), . . . , (i_l, j_l) ∈ P_d such that the corresponding swaps transform σ  to τ , that is, τ  = T_iÆjÆ   ◦ · · · ◦ T_i2j2 ◦ T_i1j1 (σ).

Tasks

1. (max2 points)

Prove  that  for  any  positive  integer  n,  the  permutation  (n, n − 1, . . . , 1)  is  (1, [n/2♩)- reachable from (1, 2, . . . , n).

2. (max3 points)

To find out whether τ is (d, l)-reachable from σ, one may apply bidirected search as follows:   First  generate  all  permutations  that  are  (d, [l/2♩)-reachable  from  σ.   Next generate all permutations that are (d, [l/2|)-reachable from τ .  Finally, report “YES” if the two generated sets intersect, and otherwise report “NO”.

Describe the algorithm using pseudocode; in particular, describe how the sets of per- mutations are generated. (You may assume the given arguments are valid: you need not implement error handling.)

3. (max3 points) 算法作业代写

Implement the algorithm of the previous task using one of the following programming languages (using only standard libraries): C, C++, Java, Python. Show your code.

Use your implementation to solve, for all d = 1, 2, . . . , 4 and l = 1, 2, . . . , 9, whether (9, 8, . . . , 1) is (d, l) reachable from (1, 2, . . . , 9). Show the results as a 4 × 9 matrix.