ANSWER Q no1

1. (max 2 points) Prove that for any positive integer n, the permutation (n, n-1, reachable from (1,2,... ,n) ,1) is (1, In/2])- 2. (max 3 points) To find out whether T is (d')-reachable from , one may apply bidirected search as follows: First generate all permutations that are (d,L1/2)-reachable from . Next generate all permutations that are (d,1/21)-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. (max 3 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 1 = 1, 2, ,9, whether (9,8,...,1) is (d, l)-reachable from (1,2,...,9). Show the results as a 4 x 9 matrix. 1. (max 2 points) Prove that for any positive integer n, the permutation (n, n-1, reachable from (1,2,... ,n) ,1) is (1, In/2])- 2. (max 3 points) To find out whether T is (d')-reachable from , one may apply bidirected search as follows: First generate all permutations that are (d,L1/2)-reachable from . Next generate all permutations that are (d,1/21)-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. (max 3 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 1 = 1, 2, ,9, whether (9,8,...,1) is (d, l)-reachable from (1,2,...,9). Show the results as a 4 x 9 matrix